Skip to content

Instantly share code, notes, and snippets.

@minrwhite
Last active August 29, 2015 14:26
Show Gist options
  • Save minrwhite/3ce181243e9075758e09 to your computer and use it in GitHub Desktop.
Save minrwhite/3ce181243e9075758e09 to your computer and use it in GitHub Desktop.
Recursive Key Sort
set logscale x
set logscale y
plot "plot.csv" using 1:2 with lines, "plot.csv" using 1:3 with lines
pause -1
43.5 4.5016407966614E-5 5.2601099014282E-6
104.75 0.00010192394256592 1.3470649719238E-5
317.75 0.00031262636184692 4.7758221626282E-5
973.75 0.00093798339366913 0.00016680359840393
5585.4375 0.0055374205112457 0.0013000071048737
27564.5 0.030550628900528 0.008007287979126
159589.875 0.19197821617126 0.084679558873177
1020809.125 1.2263167947531 0.72412523627281
<?php
// Generate the required values 0 to $number in a random order,
// reducing memory footprint as we go
function shuffledValueGenerator($number) {
$values = range(0, $number);
shuffle($values);
while($values) {
yield array_pop($values);
}
};
// populate an array recursively - top level has the initial $number
// keys, each value is determined by a 1 in 2 chance to be a
// normal value or an array with $number/16 keys - recursing down until
// it doesn't make sense to bit-shift $number any further - e.g. $number
// is 1 or less than 1
function recursiveArrayPopulate($number) {
$recArray = [];
foreach (shuffledValueGenerator($number) as $key) {
switch (rand(0, $number >= 1 ? 1 : 0)) {
case 0:
$recArray[$key] = "V";
continue;
case 1:
$recArray[$key] = recursiveArrayPopulate($number >> 4);
continue;
}
}
return $recArray;
}
// The function I am testing
function recursiveKeySort(&$by_ref_array)
{
ksort($by_ref_array, SORT_NUMERIC );
foreach ($by_ref_array as $key => $value) {
if (is_array($value))
{
recursiveKeySort($by_ref_array[$key]);
}
}
}
// function to generate an array with $topLevelKeys and a flat array
// with an equivalent number of total keys, returning the total keys,
// time taken for recursive sort, and time taken for flat sort as
// respective columns in an array
function compareArraySorts($topLevelKeys) {
$randomArray = recursiveArrayPopulate($topLevelKeys);
$totalKeys = count($randomArray, COUNT_RECURSIVE);
$rstart = microtime(true);
recursiveKeySort($randomArray);
$rend = microtime(true);
unset($randomArray);
$flatArray = [];
foreach (shuffledValueGenerator($totalKeys) as $key) {
$flatArray[$key] = "V";
}
$fstart = microtime(true);
ksort($flatArray);
$fend = microtime(true);
return [$totalKeys, ($rend - $rstart), ($fend - $fstart)];
}
// try this from 16 top-level values to 2048 top-level values.
// any bigger tends to exhaust the memory where the limit is set
// at 256M. Try each number of top-level values 16-times and take
// the average number of keys, and times, and echo into a csv to
// be read by gnuplot
for ($i = 16; $i < 4096; $i = $i << 1) {
$output = [];
for ($j = 0; $j < 16; $j++) {
$output[] = compareArraySorts($i);
}
echo implode(", ", array_map(function ($column) use ($output) {
return array_sum(array_column($output, $column)) / count($output);
}, [0, 1, 2])) . "\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment