Recursive Key Sort

test.cmd

set logscale x
set logscale y
plot "plot.csv" using 1:2 with lines, "plot.csv" using 1:3  with lines
pause -1

test.csv

test.php

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

test.png