Sorry, the title is misleading 
, I did not find some algorithm faster than quicksort, in fact, quicksort's lower bound is proven the lowest for any comparison sort algorithm.
Two days ago, a article about using quicksort algorithm in PHP by Tim Koschuetzki caught my eyes.
Koschuetzki was working on an array somewhat like this:
Array
(
[0] => Array
(
[idv11] => 624059d1f8N0
[adspots] => 2
)
[1] => Array
(
[idv11] => 67059d1f8N0
[adspots] => 4
)
[2] => Array
(
[idv11] => 6759d1f8N0
[adspots] => 8
)
)
I took out all the unnecessary keys and values for ease of understanding.
Koschuetzki's goal is to sort the array by the adspots. Since it's a multidimensional array, he can't use sort() provided by PHP, so he creates his own code in PHP and improved his code from Θ(n^2) time into Θ(n log n) time. Good work, but there should be a better way.
Usually, problems like this are taking care by the database, I don't know why Koschuetzki's corporation ask the sorting to be done in PHP. So I come up with something extremely fast.
Below is the simplified version of Koschuetzki's quicksort. I created it by modifying the PHP quicksort implementation posted on wikibook.
function quicksort_by_adspots($array){
if(!count($array)) return $array;
$k = $array[0]['adspots'];
$own = $array[0];
$x = $y = array();
$count = count($array);
for($i=1; $i<$count; $i++)
{
if($array[$i]['adspots'] <= $k)
{
$x[] = $array[$i];
}
else
{
$y[] = $array[$i];
}
}
return array_merge(quicksort_by_adspots($x), array($own), quicksort_by_adspots($y));
}
An array of 10000 values = 11 seconds!
Quicksort is fast, even PHP's internal is using quicksort. I believe
Radix sort are the only generally acceptable faster sorting function. PHP, as a
interpreted language usually can't top other
compiled languages.
So, I made a function do the same thing, but using usort().
function usort_by_adspots($array){
function adcomp($a, $b){
if ($a['adspots'] == $b['adspots']) {
return 0;
}
return ($a['adspots'] < $b['adspots']) ? -1 : 1;
}
usort($array, "adcomp");
return $array;
}
An array of 10000 values = 0.4 seconds!
Huge performance boost.
I guess this shows the importance of read the manual, I check out the entire manual and read each one of them today and finally found what I need. usort is the last array function in the manual.
Bookmark/Search this post with:
.
Thanks!
Good stuff man! You beat me to it. :] I was really looking at the usort function but could not figure out a way at first glance. Since I was under time constraints I decided to write it based on quicksort.
Thanks!
No problem.. I love to help
No problem.. I love to help people :)
Post new comment