« 2007年3月 | トップページ | 2007年5月 »

MSufSort-3.1.1b

MSufSort-3.1.1beta が公開されています。サフィックスのソートを一番大きい bucket から行うように変更されたみたいです。

                              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
MSufSort-3.1.1b      2.600     6.071     2.316    10.987
qsufsort             8.121     8.061    10.074    26.256

昨日のファイルでテストをしたところ、3.1bとは全く違う結果になりました。 1 と 3 ではかなり(というかもの凄く)改善されてます。・・なぜ 2 だけ遅くなるのだろうか ?

| | コメント (0) | トラックバック (0)

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 にいくつか論文を追加しました。

| | コメント (0) | トラックバック (0)

libdivsufsort-1.2.0 (安定版) リリース

libdivsufsort の安定版、libdivsufsort-1.2.0 をリリースしました。

1.0.2 からの主な変更点は以下の通りです。

  • ソートアルゴリズムの大幅な改良を行いました。
  • ライセンスを GNU Lesser General Public License から MIT/X11 License に変更しました。
  • デフォルトで構築するライブラリを共有ライブラリ(cygwin環境ではDLL)に変更しました。

| | コメント (0) | トラックバック (0)

Tandem repeat sorting algorithm

libdivsufsort-1.1.7」を公開。 substringsort の後に行っていたソートを Maniscalco's tandem repeat sorting algorithm (trsort) に変更しました。

この Tandem repeat sort は、Ranksort と Copy method (の一部) を組み合わせたようなアルゴリズムで、大抵のデータは高速にソートすることができます。が、最悪時間計算量は O(n^2 log n) になるため、divsufsort-1.1.7 ではそうなる前にソート法を Larsson-Sadakane sort へ切り替えて残りを処理しています。

これで、divsufsortの最悪時間計算量が O(n log n) になったはず・・。

| | コメント (0) | トラックバック (0)

« 2007年3月 | トップページ | 2007年5月 »