広く知られているinsertion sortのコードは駄目すぎる?


やねうらおさんによると、「広く知られているinsertion sortのコードは駄目すぎる」らしい。Wikipediaに載っているコード(2009.08.06版)を、

どこの馬鹿なアルゴリズムの教科書から引用してきたのかは知らないが、こんなものをサンプルとして掲載しないでもらいたい。

というのだから穏やかではない。

私の座右の書『コルメン』も、

一連の劣悪なコードはこいつが犯人かも知れない。

と非難されてしまっている。

実際のところ、どのくらいの性能差になるのか、実験してみた。

こんな感じ(codepad)。

C++の標準ライブラリ(std)のsortとWikipedia版、やねうらお版の比較。単位は秒。挿入ソートの2つ(つまりWikipedia版とやねうらお版)は、実行時間の比も計算した(1より小さい値はやねうらお版が速いことを意味する)。

size	repetition	std	wiki	yane	y/w
4	1048576		0.3512	0.1576	0.1333	0.8459
8	233016		0.1148	0.06757	0.07265	1.075
16	65536		0.111	0.02996	0.1191	3.976
32	20971		0.1388	0.1141	0.09537	0.836

Timeout

codepadはすぐにタイムアウトしてしまうから、ベンチマークにはちょっと使えない(そもそも、ほかにどんなプロセスが動いているかわからないし)。

手元のCore i7 940 2.93GHz、主記憶9Gのマシンで実行してみる。

GCC 4.4.2(64ビット)の場合(コンパイルオプションは「-O3」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.3001  0.1896  0.1957  1.032
8       1398099         0.1766  0.1374  0.1427  1.039
16      393216          0.1201  0.09756 0.09972 1.022
32      125829          0.1045  0.08267 0.08463 1.024
64      43689           0.08399 0.07897 0.08637 1.094
128     16047           0.07033 0.09022 0.1061  1.175
256     6144            0.06053 0.118   0.1466  1.243
512     2427            0.05325 0.1704  0.2192  1.287
1024    981             0.04746 0.263   0.3447  1.311
2048    405             0.04273 0.4241  0.5613  1.323
4096    168             0.03847 0.697   0.9245  1.326
8192    72              0.0356  1.187   1.582   1.333
16384   30              0.03148 1.978   2.623   1.326
32768   12              0.02696 3.157   4.208   1.333
65536   6               0.02857 6.37    8.425   1.323

配列のサイズが64くらいまでなら、std::sortを使うよりも挿入ソートのほうが速いようだ。その範囲では、Wikipedia版とやねうらお版にあまり差はない(Wikipedia版が若干速いか)。

インテルC++コンパイラ 11.0(64ビット)の場合(コンパイルオプションは「-fast」のみ)

size    repetition      std     wiki    yane    y/w
4       6291456         0.2103  0.2164  0.2285  1.056
8       1398099         0.1464  0.1455  0.1447  0.9947
16      393216          0.107   0.106   0.1072  1.011
32      125829          0.1034  0.08955 0.09303 1.039
64      43689           0.08693 0.08898 0.09369 1.053
128     16047           0.07405 0.1059  0.1113  1.051
256     6144            0.06446 0.1456  0.1503  1.032
512     2427            0.05672 0.218   0.2219  1.018
1024    981             0.05066 0.3439  0.3462  1.007
2048    405             0.04571 0.5608  0.5618  1.002
4096    168             0.04118 0.9253  0.9255  1
8192    72              0.03799 1.578   1.579   1
16384   30              0.03406 2.628   2.629   1.001
32768   12              0.02887 4.197   4.208   1.003
65536   6               0.0307  8.464   8.46    0.9995

GCCのときよりstd::sortが速くなるのが早い。サイズ64ならもうstd::sortでよいようだ。GCCの場合より、std::sortが有利になるのが少し早い。Wikipedia版とやねうらお版にあまり差はない(やはり、Wikipedia版が若干速いか)。

Visual Studio 2008(32ビット)の場合(Releaseモード。オプションはデフォルトのまま)

size    repetition      std     wiki    yane    y/w
4       6291456         0.329   0.184   0.171   0.9293
8       1398099         0.209   0.14    0.142   1.014
16      393216          0.136   0.114   0.111   0.9737
32      125829          0.105   0.1     0.098   0.98
64      43689           0.103   0.099   0.097   0.9798
128     16047           0.093   0.113   0.115   1.018
256     6144            0.083   0.141   0.155   1.099
512     2427            0.075   0.195   0.226   1.159
1024    981             0.066   0.295   0.35    1.186
2048    405             0.061   0.469   0.568   1.211
4096    168             0.057   0.77    0.937   1.217
8192    72              0.051   1.313   1.617   1.232
16384   30              0.045   2.207   2.72    1.232
32768   12              0.038   3.57    4.398   1.232
65536   6               0.04    6.966   8.513   1.222

配列サイズ64くらいまでは、挿入ソートがstd::sortより速い。その範囲では、Wikipedia版よりやねうらお版のほうが若干速いか。

いずれにしても、配列サイズが小さいなら、挿入ソートを試す価値はありそうだ。しかし、GNUやインテルのコンパイラをよく使う私には、挿入ソートの細かいチューニングは早すぎる最適化になりそうだ。

小さい配列限定のすごく速いソートなら、ソーティングネットワークはどうだろう。サイズ7の場合はこんな感じ(codepad)。batcherがソーティングネットワーク。単位は秒。codepadだと遅いか。

GCC 4.4.2(64ビット)では、ソーティングネットワークが速い。

std::sort: 0.411432
wikipedia: 0.3258
yaneurao: 0.331935
batcher: 0.28106

インテルC++コンパイラ 11.0(64ビット)の場合

std::sort: 0.324813
wikipedia: 0.331058
yaneurao: 0.298131
batcher: 0.228164

ここで使っている関数bathcersortは、CPANにあるAlgorithm::Networkで作った。次のようなコードでASCIIアートを描ける。

use Algorithm::Networksort qw(:all);
$inputs=7;
my @network = nw_comparators($inputs, algorithm => 'batcher');
print nw_graph(\@network, $inputs), "\n";
o--^--------^-----^-----------------o
   |        |     |                  
o--|--^-----|--^--v--------^--^-----o
   |  |     |  |           |  |      
o--|--|--^--v--|--^-----^--|--v-----o
   |  |  |     |  |     |  |         
o--|--|--|-----v--|--^--v--|--^--^--o
   |  |  |        |  |     |  |  |   
o--v--|--|--^-----v--|--^--v--|--v--o
      |  |  |        |  |     |      
o-----v--|--|--------v--v-----|--^--o
         |  |                 |  |   
o--------v--v-----------------v--v--o

仕組みを知りたいという向きにはKnuthの第3巻が、「サイズ7限定じゃ意味ないし、任意のサイズでできるようにしたらコンパイルできないじゃん」という向きには『LET OVER LAMBDA Edition 1.0』がおすすめ。

47561461474434133632

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です