在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数组进行排序？

- skcubrats

---

我正在尝试避免使用usort()，因为随着我的people数组的增长，它是一个过于昂贵的调用。假设$people中有15,000个条目。 - skcubrats

你认为usort有什么低效之处，需要通过其他方法来避免？usort会原地排序，并且应该非常高效。 - Paul Dixon

每次调用都会创建一个函数，这在大数据集中效率低下。 - skcubrats

我已经发布了一些基准测试细节 - usort并不算太糟糕，但确实可以使用非递归快速排序来获得更快的速度。 - Paul Dixon

你在做什么需要一次性排序15000个对象？ - Gumbo

Answer 1

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

随着PHP的发展，这个答案随时间而变化自2009年以来一直保持更新。虽然旧材料已经不再相关，但仍然很有趣！

总之，截至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年更新

我最初在2009年回答这个问题时，将使用 usort 和非递归快速排序进行比较以查看是否存在差异。结果发现，快速排序的运行速度要快三倍。

由于现在已经是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对象进行了排序。

考虑到比较函数调用的低效性，我将其与一种非递归的快速排序实现进行了比较。后者实际上只花费了大约三分之一的时间，即约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"

- Paul Dixon

---

你检查过那个算法的正确性了吗？你需要将 $array[$i] < $tmp 改为 $array[$i]->age < $tmp->age，$tmp < $array[$j] 改为 $tmp->age < $array[$j]->age，以及 $i->age <= $j->age 改为 $i <= $j。 - Gumbo

哦，如果你想比较这两个算法，你应该在相同的数据上运行它们，而不仅仅是在大小相同但特征完全不同的数据上。生成你的人员数组一次，并使用这两个算法对同样的数据进行排序。 - Gumbo

你如何修改quickSort函数以接受第二个参数来按升序或降序排序数组？此外，感谢这个伟大的函数。我肯定会好好利用它！ - tollmanz

你的 quickSort 函数让我想起了我的 C/C++ 课程，非常棒。 - AVProgrammer

为什么这不是一个被接受的答案 - 社区通过问题和被接受的答案而成长。 - Eujinks

Answer 2

针对这种情况，您可以使用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 );

- meder omuraliev

---

我正在尝试避免使用usort()，因为随着我的people数组的增长，它的调用太昂贵了。假设$people中有15,000个条目。 - skcubrats

我认为你可以更简单地实现personSort()，像这样：return $a->age - $b->age; - Don Kirkby

真的吗？我只是太习惯这样做了，没有进行数学思考。 - meder omuraliev

@DonKirkby 如果使用浮点数，return $a->age - $b->age; 会产生错误的结果，你可以使用自 PHP 7.0 开始支持的太空船操作符，并且它适用于浮点数 return $a->age <=> $b->age;。 - Yoann Kergall

Answer 3

你可以使用 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+），堆将更快，内存占用更少。 拥有堆的附加好处是可以使用它们的比较函数作为回调到其他排序函数，例如usort。您只需要记住，比较的顺序是相反的，因此使用堆进行任何比较都会导致usort中的顺序相反。

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

usort 在小到中等大小的集合中很好用，其中您将在最后一次进行排序。当然，您不必拥有堆来使用 usort。您也可以添加任何其他有效的回调进行排序。

- Gordon

---

在处理大数据时，最正确的答案是使用迭代器。每次运行迭代器只占用当前值的内存，而数组则占用所有条目的内存。堆形式的迭代器更加资源高效。 - Marcel

Answer 4

我刚编写了这个代码。它应该比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年龄相同，也可以正常工作。

- Camilo Martin

Answer 5

您只需要编写一个自定义比较函数，然后使用类似usort的方法来进行实际排序。例如，如果成员变量是myVar，则可以按以下方式对其进行排序：

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

usort($myArray, "cmp");

- Paul Dixon

Answer 6

你可以使用 ouzo goodies 实现这个目标：

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

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

- woru

Answer 7

我不建议在你的示例中使用我的解决方案，因为它会很丑（而且我没有进行基准测试），但它可以工作...根据需要，它可能会有所帮助。 :)

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);

- Toto

---

我认为缓慢的原因在于每个对象仍然会导致一次函数调用，只不过现在是在类本身中。 - Camilo Martin

Answer 8

这是一个针对值在0到256之间的稳定的基数排序(Radix Sort)实现，其中stable和Radix Sort是链接。

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) 的成本，因为基数排序是一种非比较排序算法。

- Gumbo

Answer 9

我采取了以下方法：创建一个函数，该函数接受对象数组作为参数。在函数内部，我使用属性作为键创建关联数组，然后使用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
*/

- xmc

Answer 10

有一个观察结果是，如果数据来源于数据库，使用SQL进行排序可能比在PHP内部进行排序更快。当然，如果数据来源于CSV或XML文件，这一点就无关紧要了。

- adamsch1