PHPで安定ソート

※PHP8以降のソートは安定ソートになったので自前で実装する必要はない

オレンジニュースより、http://d.hatena.ne.jp/p4life/20090705/1246779084
自前で並び替えを行っているのが気になったので自分でも書いてみた。

<?php
/// stable uasort() implementation
function uasort_stable_2(array &$array, $cmp_function) {
    $i = 0;
    $tuples = array_map(function ($key, $value) use (&$i) {
        return array($i++, $key, $value);
    }, array_keys($array), array_values($array));
    uasort($tuples, function ($a, $b) use ($cmp_function) {
        $result = call_user_func($cmp_function, $a[2], $b[2]);
        if ($result == 0)
            $result = $a[0] - $b[0];
        return $result;
    });
    $array = array();
    foreach ($tuples as $tuple)
        $array[$tuple[1]] = $tuple[2];
    return $array;
}

※この実装ではコールバックは要素が等しい時に0を返す必要がある。
5000要素の配列のソート結果:

--------------------------------------------------------------------------------
Section         Total Ex Time         Netto Ex Time         #Calls    Percentage
--------------------------------------------------------------------------------
1               8.8060479164124       8.8060479164124       1          98.79%
2               0.082173824310303     0.082173824310303     1           0.92%
Global          8.9137120246887       0.025490283966064     1         100.00%

ベンチのソース:

<?php
require_once('Benchmark/Profiler.php');

run_test();

function run_test($count = 5000) {
    $profiler = new Benchmark_Profiler();
    $profiler->start();
    $input = make_random_input($count);
    $runSection = function ($name, $sort, $callback) use (&$profiler, $input) {
        $sorted = $input;
        $profiler->enterSection($name);
        $sort($sorted, $callback);
        $profiler->leaveSection($name);
        return $sorted;
    };
    $result = $runSection('1', 'uasort_stable', function ($a, $b) {
        return $a > $b;
    });
    $result2 = $runSection('2', 'uasort_stable_2', function ($a, $b) {
        return $a - $b;
    });
    $profiler->stop();
    $profiler->display();
    assert('count($result) == count($result2)');
    while (--$count >= 0) {
        assert('key($result) === key($result2)');
        assert('current($result) === current($result2)');
        next($result);
        next($result2);
    }
}

function make_random_input($count) {
    $input = array();
    $keySrc = '0123456789abcdefghijklmnopqrstuvwxyz';
    $keySrcLength = strlen($keySrc) - 1;
    while (count($input) < $count) {
        $keyLength = rand(1, 4);
        $s = '';
        for ($c = 0; $c < $keyLength; $c++)
            $s .= $keySrc[rand(0, $keySrcLength)];
        $input[$s] = rand(-200, 200);
    }
    return $input;
}

もしかしたらあるかも、と思いつつ2配列の比較を自前で書いたのがオチ。