quick sortよりも高速でmerge sortのように安定しているソートアルゴリズムtim sort [勘違い]

<追記>ベンチマークプログラムに誤りがありました。ソート済のシーケンスに対してソートを掛けていました。ご指摘ありがとうございます＞ak氏</追記>

そんな夢のようなソートアルゴリズムがあるのかというと、あるらしいんです。それがtim sortと呼ばれるアルゴリズムです。

濃縮還元オレンジニュース：画期的（？）なソートアルゴリズム「Sleep Sort」｜gihyo.jp … 技術評論社

このあたりで拾ってきたネタですね。

merge sortを改良したアルゴリズムで、安定*1しており、しかも実行速度にも優れているとか。アルゴリズムの性能の評価は済んでいるらしく、CPythonやJDK7には既に導入済みのようですね。

ならば当然Perlのソートも…と考えるわけですが、まず評価のためにJavaのソースをC++にそのまま移植してみました。それがこれ（いちおうテスト済）：

https://github.com/gfx/cpp-TimSort/blob/master/timsort.hpp

オリジナルはこちら：

http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java

インターフェイスはC++の標準ライブラリstd::sort()/std::stable_sort()と同じです。

int/double/boost::rational<long long>の入ったstd::vectorをランダムシャッフルしてソートする、というベンチマークだと結果は以下のようになりました。

https://github.com/gfx/cpp-TimSort/blob/master/bench.cpp

# MacOSX Snow Leopard / Apple clang 2.0 (llvm 2.9) $ clang++ -DNDEBUG -O2 -Wall -Wextra bench.cp -o bench $ ./bench int size 100000 std::sort 0.12273 std::stable_sort 0.182555 timsort 0.021382 double size 100000 std::sort 0.121308 std::stable_sort 0.221106 timsort 0.026283 boost::rational size 100000 std::sort 3.60624 std::stable_sort 2.60706 timsort 0.319079</del>

適当なベンチマークですがだいぶ高速ですね。以下の記事では、ランダムなデータだとmerge sortよりも劣るという結果ですが、こちらはC++なせいかそうでもないように見えます。

Java 7のArrays.sort(Object[])：柴田芳樹 (Yoshiki Shibata)：So-netブログ

このアルゴリズム、かなり複雑なのでソラで書けそうもないのが欠点ですが、これだけ高速ならPerlに移植する価値はありそうです。

ベンチマークプログラムが誤っていたので再検討中...取り急ぎ修正してみると特に高速ではありません： https://github.com/gfx/cpp-TimSort/commit/392af11ea2dea47a93b705a5ef95994449766113

Permalink | コメント(4) | トラックバック(2) | 08:50

*1：この「安定(stable)」はソートアルゴリズムの用語で、同等のデータのソート前の並び順が、ソート後も保持されるという意味です。テストコードで示すと次のtest.cppのstabilityテストのような挙動を示すものです。 https://github.com/gfx/cpp-TimSort/blob/master/test.cpp#L157