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配列の比較を自前で書いたのがオチ。