PHP7から、内部的なソートアルゴリズムが変更されました。これはsort系のPHP関数だけでなく、その他PHPの内部処理でも利用されています。
この変更により最悪時の性能はかなり改善されたと思われますが、現在の実装が最適かどうかは今後の検証が必要だと感じています。
新旧の実装
PHP5までのソート実装は教科書的とも言えるクイックソートでした。クイックソートは平均的には最速レベルのソートではあるものの、最悪時の性能が非常に悪くなることでも有名です。
PHP7のソート実装でもクイックソートが用いられていますが、以前の実装とは次のような点が異なっています。
- pivot選択の際、これまで1点決め打ちだったのを3点または5点から選ぶように
- 要素数が少なくなってからは挿入ソートに切り替え
1つめの工夫により、最悪ケースに近づく可能性が以前より下がったと考えられます。2つめの工夫により性能も上がりそうです。
性能
次のように、100万要素の配列$array1
と$array2
をPHP5.6とPHP7でソートしてみました。
<?php
$array1 = $array2 = array();
define("SIZE", 1000000);
for ($i = 0; $i < SIZE; $i++) {
$array1[$i] = SIZE-$i;
switch ($i % 4) {
case 0:
$array2[$i] = SIZE-$i;
break;
case 1:
$array2[$i] = SIZE+$i;
break;
case 2:
$array2[$i] = 2*SIZE-$i;
break;
case 3:
$array2[$i] = $i;
break;
}
}
$start = microtime(true);
sort($array1);
$time = microtime(true) - $start;
echo $time."s\n";
$start = microtime(true);
sort($array2);
$time = microtime(true) - $start;
echo $time."s\n";
PHP 5.6.3 | PHP 7.0.0-dev | |
---|---|---|
$array1 |
0.426 sec | 0.523 sec |
$array2 |
27.4 sec | 0.599 sec |
$array1
のように綺麗な並び順の場合はPHP5の方が有利だという結果になりました。もしかすると、PHP7の新実装は細かい改善の余地があるのかもしれません。
一方で、多少意地悪な配列を食わせるとPHP5はひどく性能が悪くなることもわかりますが、PHP7の方は安定していそうな結果になりました。
#実装箇所
それぞれの実装を読んでみたい方のために実装箇所も紹介しておきます。
PHP5のソート関数はZend/zend_qsort.cのzend_qsort()
、またPHP7で実装されたソート関数は[Zend/zend_sort.c]
(https://github.com/php/php-src/blob/master/Zend/zend_sort.c)の`zend_sort()`です。
#さらなる最適化
ググってみると最近のナウなソートアルゴリズムとしてイントロソートなどがあるようで、PHP7の実装は今更感があるのかなと思いました。
アルゴリズムなら任せろ!という方がいらしたら、PHP7開発中の今のうちに改善提案を出してみてはいかがでしょうか。よろしくお願いします。
#参照