note 84729 deleted from function.array-splice by danbrown
| From: | danbrown@php.net | Date: | Mon, 28 Jul 2008 00:25:45 +0000 |
| Subject: | note 84729 deleted from function.array-splice by danbrown | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-142836@lists.php.net to get a copy of this message | ||
Note Submitter: loushou - life dot 42 at gmail dot com
----
seriously.... i don't think that you can get any faster than this.... quicksort for
multi-dimension arrays... give it an index and it will sort for you... this of course follows all
the same rules of performance as quicksort itself.
<?php
function q_sort(&$Info, $Index, $Left, $Right)
{
echo "memory usage <b>".memory_get_usage()."</b><br/>\n";
$L_hold = $Left;
$R_hold = $Right;
$Pivot = $Left;
while ($Left < $Right)
{
while (($Info[$Right][$Index] >= $Info[$Pivot][$Index]) && ($Left < $Right))
$Right--;
if ($Left != $Right)
{
$Info[$Left][$Index] = $Info[$Right][$Index];
$Left++;
}
while (($Info[$Left][$Index] <= $Info[$Pivot][$Index]) && ($Left < $Right))
$Left++;
if ($Left != $Right)
{
$Info[$Right][$Index] = $Info[$Left][$Index];
$Right--;
}
}
$Info[$Left][$Index] = $Info[$Pivot][$Index];
$Pivot = $Left;
$Left = $L_hold;
$Right = $R_hold;
if ($Left < $Pivot)
q_sort($Info, $Index, $Left, $Pivot-1);
if ($Right > $Pivot)
q_sort($Info, $Index, $Pivot+1, $Right);
}
?>
try this out with this code for instance.
<?php
echo "memory usage <b>".memory_get_usage()."</b><br/>\n";
echo "<span style='font-family:\"verdana\"; font-size:10px;'>";
$test = array();
srand(microtime(true));
$Start = microtime(true);
echo "gen start time: ".$Start."<br/>\n";
for ($i = 0; $i < 10000; $i++)
{
$test[] = array('number'=>rand(0, 1000000));
}
$End = microtime(true);
echo "gen end time: ".$End."<br/>\n";
echo "gen time difference: ".($End-$Start)."secs<br/>\n";
$Start = microtime(true);
echo "sort start time: ".$Start."<br/><br/>\n";
q_sort($test, 'number', 0, count($test)-1);
//$test = sortValues($test, 'number');
$End = microtime(true);
echo "sort end time: ".$End."<br/>\n";
echo "sort time difference: ".($End-$Start)."secs<br/>\n";
echo "<br/><br/><br/>";
for ($i=0; $i<count($test); $i++)
{
echo $test[$i]['number']."<br/>\n";
}
echo "</span>";
?>
additionally, the memory footprint on this is sooooooooo small. seriously that is why i added the
memory stuff in the code samples above to show you.