php - 在PHP中按对象属性对数组进行排序？

Question

如果我有这样一个对象:

class Person {
  var $age;
  function __construct($age) {
    $this->age = $age;
  }
}

并且我有任何Person数组

$person1 = new Person(14);
$person2 = new Person(5);
$people = array($person1, $person2);

有没有一种简单的方法可以根据 Person->age 属性对 $people 数组进行排序？

Answer 1

问题是关于使用 usort 效率低下的问题。因为调用比较回调的开销。这个答案着眼于使用内置排序函数和非递归快速排序实现之间的区别。

随着 PHP 自 2009 年以来的发展，答案随着时间的推移而改变，所以我一直在更新它。旧 Material 虽然不再相关，但仍然很有趣!

TL;DR:从 php 7.0.1 开始，非递归快速排序不再比使用带有回调的 usort 更快。并非总是如此，这就是为什么要详细说明下面进行有趣的阅读。真正的收获是，如果您对问题进行基准测试并尝试其他方法，您会得出令人惊讶的结果。

2016 年 1 月更新

我们已经发布了 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 年 1 月更新

当我在 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 |
+-----------+------------+------------+------------+------------+------------+

2009 年的原始笔记

我试过 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 作为第二个参数传递给 sort 才能真正调用魔术方法，这具有执行字符串而不是数字排序的副作用。为了解决这个问题，您需要用零填充数字以使其正确排序。最终结果是这比 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"