StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The question was concerned about the inefficiency of using <a href="http://www.php.net/usort" rel="nofollow noreferrer">usort</a> 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.</p> <p>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!</p> <p><strong>TL;DR: as of php 7.0.1, a non-recursive quicksort is no longer faster than using usort with a callback.</strong> 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.</p> <h2>Jan 2016 update</h2> <p>Well here we are with php 7.0 released and 7.1 on the way! Finally, for this dataset, the built-in usort is <em>ever-so-slightly</em> faster!</p> <pre><code>+-----------+------------+------------+------------+------------+------------+ | 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 | +-----------+------------+------------+------------+------------+------------+ </code></pre> <h2>Jan 2015 update</h2> <p>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 <em>significant</em> difference, with the quicksort running 3x faster.</p> <p>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: <a href="http://3v4l.org/WsEEQ" rel="nofollow noreferrer">http://3v4l.org/WsEEQ</a></p> <pre><code>+-----------+------------+------------+------------+------------+------------+ | 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 | +-----------+------------+------------+------------+------------+------------+ </code></pre> <h2>Original Notes from 2009</h2> <p>I tried a <a href="http://www.php.net/usort" rel="nofollow noreferrer">usort</a>, and sorted 15000 Person objects in around 1.8 seconds. </p> <p>As you are concerned about the inefficiency of the calls to the comparison function, I compared it with a non-recursive <a href="http://en.wikipedia.org/wiki/Quicksort" rel="nofollow noreferrer">Quicksort</a> implementation. This actually ran in around one third of the time, approx 0.5 seconds.</p> <p>Here's my code which benchmarks the two approaches</p> <pre><code>// 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"; </code></pre> <p>An interesting suggestion was to add a <code>__toString</code> 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</p> <pre><code>sort 10000 items took 1.76266698837 usort 10000 items took 1.08757710457 quickSort 10000 items took 0.320873022079 </code></pre> <p>Here's the code for the sort() using __toString():</p> <pre><code>$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" </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload