如果我有一个这样的对象:
class Person {
var $age;
function __construct($age) {
$this->age = $age;
}
}
和我有任何阵列Person小号
$person1 = new Person(14);
$person2 = new Person(5);
$people = array($person1, $person2);
是否有一种简单的方法来$people按Person->age属性对数组进行排序？
Pau*_*xon 87
由于调用比较回调的开销,问题是关注使用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年,我认为重新审视它可能是有用的,所以我使用usort和quicksort对15000个对象进行排序,并在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,并在大约1.8秒内对15000个Person对象进行了排序.
由于您担心调用比较函数的效率低下,我将其与非递归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()的sort()的代码:
$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"
med*_*iev 42
对于该特定方案,您可以使用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 );
Gor*_*don 10
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
请注意,Heap的目的是始终拥有有序集合而不是替换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");
usort()或者uasort() /* to maintain index association if you were using an associative array */