Вопрос касался неэффективности использования usort из-за накладных расходов при вызове обратного вызова сравнения. В этом ответе рассматривается различие между использованием встроенных функций сортировки и нерекурсивной реализацией быстрой сортировки.
Ответ менялся со временем по мере развития PHP с 2009 года, поэтому я постоянно обновлял его. Более старый материал, хотя и более не актуален, но все же интересен!
TL; DR: с php 7.0.1 нерекурсивная быстрая сортировка больше не работает быстрее, чем использование 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 с нерекурсивной быстрой сортировкой, чтобы увидеть, есть ли разница. Как оказалось, разница была значительная , при этом быстрая сортировка работала в 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 года
Я попробовал usort и отсортировал 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
Вот код для сортировки () с использованием __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"