Если у меня есть объект как таковой:
class Person {
var $age;
function __construct($age) {
$this->age = $age;
}
}
и у меня есть любой массив из Person s
$person1 = new Person(14);
$person2 = new Person(5);
$people = array($person1, $person2);
Есть ли простой способ отсортировать массив $people с помощью свойства Person->age?
Вопрос касался неэффективности использования usort из-за накладных расходов на вызов обратного вызова сравнения. В этом ответе рассматривается разница между использованием встроенных функций сортировки и нерекурсивной реализацией quicksort.
Ответ изменился с течением времени, поскольку PHP развился с 2009 года, поэтому я сохранил его. Более старый материал, хотя и не актуальный, по-прежнему интересен!
TL; DR: по состоянию на php 7.0.1 нерекурсивная быстрая сортировка уже не быстрее, чем использование usort с обратным вызовом. Это не всегда так, поэтому детали ниже интересное чтение. Реальная выгода заключается в том, что если вы проверите свою проблему и попробуйте альтернативные подходы, вы можете придумать удивительные результаты.
Хорошо, вот мы с выпуском 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 |
+-----------+------------+------------+------------+------------+------------+
Когда я ответил на это в 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 |
+-----------+------------+------------+------------+------------+------------+
Я попробовал 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
Здесь код для 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 или heap.
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);
Heres a stable 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
*/
Вы можете сделать это с помощью ouzo 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 );