CODEWITHSUNDEEP
phpsorting
skcubrats
skcubrats

Reputation:

Sort array by object property in PHP?

If I have an object as such:

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

and I have any array of Persons

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

Is there an easy way to sort the $people array by the Person->age property?

Upvotes: 58

Views: 43059

Answers (15)

Paul Dixon
Paul Dixon

Reputation: 301075

The question was concerned about the inefficiency of using usort because of the overhead of calling the comparison callback. This answer looks at the difference between using the built-in sort functions and a non-recursive quicksort implementation.

The answer changed over time as PHP evolved since 2009, so I've kept it updated. The older material, while no longer relevant, is still interesting though!

TL;DR: as of php 7.0.1, a non-recursive quicksort is no longer faster than using usort with a callback. This wasn't always the case, which is why the details below make interesting reading. The real takeaway is that if you benchmark your problem and try alternative approaches, you can come up with surprising results.

Jan 2016 update

Well here we are with php 7.0 released and 7.1 on the way! Finally, for this dataset, the built-in usort is ever-so-slightly faster!

+-----------+------------+------------+------------+------------+------------+
| 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 |
+-----------+------------+------------+------------+------------+------------+

Jan 2015 update

When I originally answered this in 2009, I compared using usort with a non-recursive quicksort to see if there was a difference. As it turned out, there was significant difference, with the quicksort running 3x faster.

As it's now 2015, I thought it might be useful to revisit this, so I took code which sorts 15000 objects using usort and quicksort and ran it on 3v4l.org which runs it on lots of different PHP versions. The full results are here: 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 |
+-----------+------------+------------+------------+------------+------------+

Original Notes from 2009

I tried a usort, and sorted 15000 Person objects in around 1.8 seconds.

As you are concerned about the inefficiency of the calls to the comparison function, I compared it with a non-recursive Quicksort implementation. This actually ran in around one third of the time, approx 0.5 seconds.

Here's my code which benchmarks the two approaches

// 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";

An interesting suggestion was to add a __toString method to the class and use sort(), so I tried that out too. Trouble is, you must pass SORT_STRING as the second parameter to sort get it to actually call the magic method, which has the side effect of doing a string rather than numeric sort. To counter this, you need to pad the numbers with zeroes to make it sort properly. Net result was that this was slower than both usort and the custom quickSort

sort 10000 items took      1.76266698837
usort 10000 items took     1.08757710457
quickSort 10000 items took 0.320873022079

Here's the code for the sort() using __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"

Upvotes: 88

oshell
oshell

Reputation: 9123

Here is an option that takes following things into account:

  • namespaces
  • private properties
  • using getter and setter methods
  • property for sort as parameter

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

Upvotes: 0

woru
woru

Reputation: 1420

You can do it with ouzo goodies:

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

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

Upvotes: 2

Camilo Martin
Camilo Martin

Reputation: 37908

I just coded this. It should be faster than usort as it does not rely on numerous function calls.

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

Usage:

$sorted = sortByProp($people, 'age');

Oh, and it uses ksort but it works even if many $people are of the same $age.

Upvotes: 9

xmc
xmc

Reputation: 251

I went with the following approach: created a function that takes an array of objects, then inside the function I create an associative array using the property as key for the array, then sort they array keys using 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
*/

Upvotes: 2

user187291
user187291

Reputation: 53950

If all member variables in question are guaranteed to be different, it will be simpler and faster to create a new collection indexed by these values and then ksort it:

 foreach($obj_list as $obj)
    $map[$obj->some_var] = $obj;
 ksort($map);
 /// $map now contains the sorted list

If there are duplicate values, you can still avoid usort by utilizing a less known feature of sort that arrays of arrays are sorted by the value of the first scalar member. 

 foreach($obj_list as $obj)
    $map[] = array($obj->some_var, $obj);
 sort($map); // sorts $map by the value of ->some_var

I guess this still will be 10000000 times faster than usort

Upvotes: 1

Gordon
Gordon

Reputation: 317177

You could either use usort or a 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

Note that the purpose of an Heap is to have an ordered collection at all times and not to replace usort. For large collections (1000+), a heap will be faster and less memory intensive though.

An added benefit of having Heaps is being able to use their comparison function for callbacks to other sorting functions, like usort. You just have to remember that the order for the comparison is reversed, so any comparison done with a Heap will result in reversed order in usort.

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

usort is fine for small to medium collections where you will do the sorting once at the end. Of course, you dont have to have a heap to use usort. You can just as well add any other valid callback for the sorting.

Upvotes: 11

jimbo
jimbo

Reputation: 11042

Try usort: http://www.php.net/manual/en/function.usort.php

Example:

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

?>

Upvotes: 1

Paul Dixon
Paul Dixon

Reputation: 301075

You just need to write a custom comparison function, then use something like usort to do the actual sorting. For example, if the member variable was myVar, you could sort it as follows:

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

usort($myArray, "cmp");

Upvotes: 5

adamsch1
adamsch1

Reputation: 301

One observation is that if the source of the data is from a database, it's probably faster to sort using SQL than it would be within PHP. Of course this is moot if the data source is from a CSV or XML file.

Upvotes: 2

txyoji
txyoji

Reputation: 6868

Yes. If you implement spl ArrayObject in your person object, all the normal php array functions will work properly with it.

Upvotes: 1

Gumbo
Gumbo

Reputation: 655707

Here’s a stable Radix Sort implementation for values 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];
        }
    }
}

This costs only O(n) since Radix Sort is a non-comparing sorting algorithm.

Upvotes: 2

Toto
Toto

Reputation: 2450

I do not advice my solution in your example because it would be ugly (And I have not benchmarked it), but it works.... And depending of the need, it may help. :)

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

Upvotes: 2

meder omuraliev
meder omuraliev

Reputation: 186742

For that specific scenario, you can sort it using the usort() function, where you define your own function to compare the items in the array.

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

Upvotes: 42

grantwparks
grantwparks

Reputation: 1153

usort() or uasort() /* to maintain index association if you were using an associative array */

Upvotes: 1

Related Questions