9
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

PHP7調査(18)内部的なソートアルゴリズムの再実装

Last updated at Posted at 2015-04-16

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.czend_qsort()、またPHP7で実装されたソート関数は[Zend/zend_sort.c]
(https://github.com/php/php-src/blob/master/Zend/zend_sort.c)の`zend_sort()`です。

#さらなる最適化

ググってみると最近のナウなソートアルゴリズムとしてイントロソートなどがあるようで、PHP7の実装は今更感があるのかなと思いました。

アルゴリズムなら任せろ!という方がいらしたら、PHP7開発中の今のうちに改善提案を出してみてはいかがでしょうか。よろしくお願いします。

#参照

9
9
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
9
9

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?