« libdivsufsort-1.2.0 (安定版) リリース | トップページ | MSufSort-3.1.1b »

Test 1

サフィックスソートアルゴリズムの丈夫さをテストするためのファイルを3つほど作り、それぞれのアルゴリズムの Suffix Array の構築にかかった時間を計測してみた。

test1.gz, test2.gz, test3.bz2, generator.c.gz

                              Running times (in sec)
Program              test1     test2     test3    totals
=======           ========  ========  ========  ========
Archon3r3         1842.609    42.591  1205.943  3091.143
BPR                  6.449     1.852   771.879   780.180
DC32                 7.140     7.130     8.111    22.381
Deep-Shallow        20.829    20.849    11.696    53.374
DivSufSort-1.0.2     4.716     4.766     2.142    11.624
DivSufSort-1.2.0     1.801     1.110     1.471     4.382
KA                   2.343     2.273     2.022     6.638
KS                   5.237     5.227     5.237    15.701
MSufSort-3.1b       13.829     1.091  1625.036  1639.956
qsufsort             8.121     8.061    10.074    26.256

ふぅむ・・、O(n), O(n log n) time のアルゴリズムはそれなりに安定した結果になったけど、 やはりそれ以外の O(n^2), O(n^2 log n) time のアルゴリズムは構築にかなりの時間がかかりますねえ。

=====================

links にいくつか論文を追加しました。

|

« libdivsufsort-1.2.0 (安定版) リリース | トップページ | MSufSort-3.1.1b »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/154471/41473682

この記事へのトラックバック一覧です: Test 1:

« libdivsufsort-1.2.0 (安定版) リリース | トップページ | MSufSort-3.1.1b »