Сортировка массива по свойству объекта в PHP?

Вопрос касался неэффективности использования usort из-за накладных расходов при вызове обратного вызова сравнения. В этом ответе рассматривается разница между использованием встроенных функций сортировки и нерекурсивной реализацией quicksort.

Ответ изменился с течением времени, поскольку PHP развился с 2009 года, поэтому я сохранил его обновление. Более старый материал, хотя и не актуальный, по-прежнему интересен!

TL; DR: с php 7.0.1, нерекурсивная quicksort не быстрее, чем использование usort с обратным вызовом. Это было не всегда так, поэтому приведенные ниже детали делают интересное чтение. Реальная выгода заключается в том, что если вы проверите свою проблему и попробуйте альтернативные подходы, вы можете придумать удивительные результаты.

Обновление за январь 2016 года

Ну вот мы с php 7.0 выпущены и 7.1 по пути! Наконец, для этого набора данных встроенный usort всегда немного быстрее!

 +-----------+------------+------------+------------+------------+------------+ | Operation | HHVM | php7.0.1 | php5.6.3 | 5.4.35 | 5.3.29 | +-----------+------------+------------+------------+------------+------------+ | usort | *0.0445 | *0.0139 | 0.1503 | 0.1388 | 0.2390 | | quicksort | 0.0467 | 0.0140 | *0.0912 | *0.1190 | *0.1854 | | | 5% slower | 1% slower | 40% faster | 15% faster | 23% faster | +-----------+------------+------------+------------+------------+------------+ 

Обновление в январе 2015 года

Когда я ответил на это в 2009 году, я сравнил использование usort с нерекурсивным быстродействием, чтобы увидеть, есть ли разница. Как оказалось, значительная разница была в том, что quicksort работает на 3 раза быстрее.

Как и сейчас, 2015 год, я подумал, что было бы полезно вернуться к этому, поэтому я взял код, который сортирует 15000 объектов, используя usort и quicksort, и запускал его на 3v4l.org, который запускает его на множестве разных версий PHP. Полные результаты приведены здесь: http://3v4l.org/WsEEQ

 +-----------+------------+------------+------------+------------+------------+ | Operation | HHVM | php7alpha1 | php5.6.3 | 5.4.35 | 5.3.29 | +-----------+------------+------------+------------+------------+------------+ | usort | *0.0678 | 0.0438 | 0.0934 | 0.1114 | 0.2330 | | quicksort | 0.0827 | *0.0310 | *0.0709 | *0.0771 | *0.1412 | | | 19% slower | 30% faster | 25% faster | 31% faster | 40% faster | +-----------+------------+------------+------------+------------+------------+ 

Оригинальные заметки за 2009 год

Я попробовал усортировать и отсортировал 15000 объектов Person примерно за 1,8 секунды.

Поскольку вас беспокоит неэффективность вызовов функции сравнения, я сравнил ее с нерекурсивной реализацией Quicksort . Это примерно на треть, примерно 0,5 секунды.

Вот мой код, который сравнивает два подхода

 // Non-recurive Quicksort for an array of Person objects // adapted from http://www.algorithmist.com/index.php/Quicksort_non-recursive.php function quickSort( &$array ) { $cur = 1; $stack[1]['l'] = 0; $stack[1]['r'] = count($array)-1; do { $l = $stack[$cur]['l']; $r = $stack[$cur]['r']; $cur--; do { $i = $l; $j = $r; $tmp = $array[(int)( ($l+$r)/2 )]; // partion the array in two parts. // left from $tmp are with smaller values, // right from $tmp are with bigger ones do { while( $array[$i]->age < $tmp->age ) $i++; while( $tmp->age < $array[$j]->age ) $j--; // swap elements from the two sides if( $i <= $j) { $w = $array[$i]; $array[$i] = $array[$j]; $array[$j] = $w; $i++; $j--; } }while( $i <= $j ); if( $i < $r ) { $cur++; $stack[$cur]['l'] = $i; $stack[$cur]['r'] = $r; } $r = $j; }while( $l < $r ); }while( $cur != 0 ); } // usort() comparison function for Person objects function personSort( $a, $b ) { return $a->age == $b->age ? 0 : ( $a->age > $b->age ) ? 1 : -1; } // simple person object class Person { var $age; function __construct($age) { $this->age = $age; } } //---------test internal usort() on 15000 Person objects------ srand(1); $people=array(); for ($x=0; $x<15000; $x++) { $people[]=new Person(rand(1,100)); } $start=microtime(true); usort( $people, 'personSort' ); $total=microtime(true)-$start; echo "usort took $total\n"; //---------test custom quicksort on 15000 Person objects------ srand(1); $people=array(); for ($x=0; $x<15000; $x++) { $people[]=new Person(rand(1,100)); } $start=microtime(true); quickSort( $people ); $total=microtime(true)-$start; echo "quickSort took $total\n"; 

Интересным предложением было добавить __toString в класс и использовать sort (), поэтому я тоже это пробовал. Проблема заключается в том, что вы должны передать SORT_STRING в качестве второго параметра для сортировки, чтобы заставить его фактически вызвать магический метод, который имеет побочный эффект от выполнения строковой, а не цифровой сортировки. Чтобы противостоять этому, вам нужно заполнить цифры нулями, чтобы они правильно сортировались. Чистый результат состоял в том, что это было медленнее, чем как usort, так и пользовательский quickSort

 sort 10000 items took 1.76266698837 usort 10000 items took 1.08757710457 quickSort 10000 items took 0.320873022079 

Вот код для sort (), использующий __toString ():

 $size=10000; class Person { var $age; function __construct($age) { $this->age = $age; $this->sortable=sprintf("%03d", $age); } public function __toString() { return $this->sortable; } } srand(1); $people=array(); for ($x=0; $x<$size; $x++) { $people[]=new Person(rand(1,100)); } $start=microtime(true); sort( $people, SORT_STRING); $total=microtime(true)-$start; echo "sort($size) took $total\n" 

Для этого конкретного сценария вы можете сортировать его с помощью функции usort (), где вы определяете свою собственную функцию для сравнения элементов в массиве.

 <?php class Person { var $age; function __construct($age) { $this->age = $age; } } function personSort( $a, $b ) { return $a->age == $b->age ? 0 : ( $a->age > $b->age ) ? 1 : -1; } $person1 = new Person(14); $person2 = new Person(5); $person3 = new Person(32); $person4 = new Person(150); $person5 = new Person(39); $people = array($person1, $person2, $person3, $person4, $person5); print_r( $people ); usort( $people, 'personSort' ); print_r( $people ); 

Вы можете использовать usort или кучу .

  class SortPeopleByAge extends SplMaxHeap { function compare($person1, $person2) { return $person1->age - $person2->age; } } $people = array(new Person(30), new Person(22), new Person(40)); $sorter = new SortPeopleByAge; array_map(array($sorter, 'insert'), $people); print_r(iterator_to_array($sorter)); // people sorted from 40 to 22 

Обратите внимание, что цель кучи состоит в том, чтобы иметь упорядоченную коллекцию в любое время и не заменять usort . Для больших коллекций (1000+) куча будет быстрее и меньше памяти.

Дополнительным преимуществом использования Heaps является возможность использовать функцию сравнения для обратных вызовов для других функций сортировки, таких как usort . Вам просто нужно помнить, что порядок сравнения отменен, поэтому любое сравнение, выполненное с кучей, приведет к обратному порядку в usort .

 // using $people array and $sorter usort($people, array($sorter, 'compare')); print_r($people); // people sorted from 22 to 40 

usort отлично подходит для небольших и средних коллекций, где вы будете сортировать один раз в конце. Конечно, вам не нужно иметь кучу, чтобы использовать usort . Вы можете также добавить любой другой действительный обратный вызов для сортировки.

Я просто закодировал это. Он должен быть быстрее, чем usort поскольку он не полагается на многочисленные вызовы функций.

 function sortByProp($array, $propName, $reverse = false) { $sorted = []; foreach ($array as $item) { $sorted[$item->$propName][] = $item; } if ($reverse) krsort($sorted); else ksort($sorted); $result = []; foreach ($sorted as $subArray) foreach ($subArray as $item) { $result[] = $item; } return $result; } 

Применение:

 $sorted = sortByProp($people, 'age'); 

О, и он использует ksort но он работает, даже если много $people имеют одинаковый $age .

Вам просто нужно написать пользовательскую функцию сравнения, а затем использовать что-то вроде usort для фактической сортировки. Например, если переменная-член была myVar , вы можете отсортировать ее следующим образом:

 function cmp($a, $b) { if ($a->myVar == $b->myVar) { return 0; } return ($a->myVar < $b->myVar) ? -1 : 1; } usort($myArray, "cmp"); 

Я не рекомендую мое решение в вашем примере, потому что это было бы уродливо (и я не тестировал его), но он работает … И в зависимости от необходимости он может помочь. 🙂

 class Person { public $age; function __construct($age) { $this->age = $age; } public function __toString() { return $this->age; } } $person1 = new Person(14); $person2 = new Person(5); $persons = array($person1, $person2); asort($persons); 

Вот стабильная реализация Radix Sort для значений 0 … 256:

 function radixsort(&$a) { $n = count($a); $partition = array(); for ($slot = 0; $slot < 256; ++$slot) { $partition[] = array(); } for ($i = 0; $i < $n; ++$i) { $partition[$a[$i]->age & 0xFF][] = &$a[$i]; } $i = 0; for ($slot = 0; $slot < 256; ++$slot) { for ($j = 0, $n = count($partition[$slot]); $j < $n; ++$j) { $a[$i++] = &$partition[$slot][$j]; } } } 

Это стоит только O ( n ), поскольку Radix Sort – это не сравнивающий алгоритм сортировки.

Одно из наблюдений заключается в том, что, если источником данных является база данных, вероятно, быстрее отсортировать с использованием SQL, чем в PHP. Конечно, это спорный вопрос, если источник данных из CSV или XML-файла.

Я пошел со следующим подходом: создал функцию, которая принимает массив объектов, а затем внутри функции я создаю ассоциативный массив, используя свойство как ключ для массива, а затем сортирую их ключи массива с помощью ksort:

 class Person { var $age; function __construct($age) { $this->age = $age; } } function sortPerson($persons = Array()){ foreach($persons as $person){ $sorted[$person->age] = $person; } ksort($sorted); return array_values($sorted); } $person1 = new Person(14); $person2 = new Person(5); $persons = array($person1, $person2); $person = sortPerson($persons); echo $person[0]->age."\n".$person[1]->age; /* Output: 5 14 */ 

Вы можете сделать это с uuzo goodies :

 $result = Arrays::sort(array($person1, $person2), Comparator::compareBy('age')); 

http://ouzo.readthedocs.org/en/latest/utils/comparators.html

usort() или uasort() /* to maintain index association if you were using an associative array */

Да. Если вы реализуете spl ArrayObject в объекте person, все нормальные функции массива php будут корректно работать с ним.

Попробуйте использовать: http://www.php.net/manual/en/function.usort.php

Пример:

 <?php function cmp($obja, $objb) { $a = $obja->sortField; $b = $objb->sortField; if ($a == $b) { return 0; } return ($a < $b) ? -1 : 1; } $a = array( /* your objects */ ); usort($a, "cmp"); ?> 

Если все переменные-члены, о которых идет речь, гарантированно отличаются друг от друга, будет проще и быстрее создавать новую коллекцию, индексированную этими значениями, а затем ksort it:

  foreach($obj_list as $obj) $map[$obj->some_var] = $obj; ksort($map); /// $map now contains the sorted list 

Если есть повторяющиеся значения, вы все равно можете избежать использования usort , используя менее известную функцию sort которую массивы массивов сортируются по значению первого скалярного элемента.

  foreach($obj_list as $obj) $map[] = array($obj->some_var, $obj); sort($map); // sorts $map by the value of ->some_var 

Я думаю, это будет в 10000000 раз быстрее, чем usort

Вот вариант, который учитывает следующее:

• Пространства имен
• частные дома
• с использованием методов геттера и сеттера
• свойство сортировать как параметр

PHP

 namespace Dummy; class Person { private $age; function __construct($age) { $this->setAge($age); } public function getAge() { return $this->age; } public function setAge($age) { $this->age = $age; } } class CustomSort{ public $field = ''; public function cmp($a, $b) { return strcmp($a->{'get'.ucfirst($this->field)}(), $b->{'get'.ucfirst($this->field)}()); } public function sortObjectArrayByField($array, $field) { $this->field = $field; usort($array, array("Dummy\CustomSort", "cmp")); return $array; } } $robert = new Person(20); $peter = new Person(12); $robin = new Person(44); $people = array($robert, $peter, $robin); var_dump( $people ); $customSort = new CustomSort(); $people = $customSort->sortObjectArrayByField($people, 'age'); var_dump( $people );