« libdcs | トップページ | sais-2.4.0 »

sais-lite-2.4.0

sais-lite-2.4.0をこっそり公開〜。バグが無ければ向こうのもそのうち更新します。

File: sais-lite-2.4.0.zip
Size: 17,096 bytes
SHA1: 7b7677b02ca9e65bac8b8295c35bf387856814ff

今回はstage1の処理などを大幅に書き変えたので、接尾辞配列の構築にかかる時間が少し短縮されています。 あと、ほとんど意味の無かったOpenMP関連のコードを削除しました。parallel suffix sortingにはdcsを使った方が良さげ。

ベンチマーク結果は以下の通りです。divsufsort超えまで後もう少しだけどこれ以上は厳しいかな…

  • divsufsort2 - divsufsort-2.0.0
  • DC - Difference-Cover algorithm (v=32)
  • DS - Deep-Shallow sorting algorithm
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
  • sais1 - 前のバージョンのsais
  • sais2 - sais-lite-2.4.0
Manzini's Large Corpus
FilesSizedivsufsort2DCDSKALSsais1sais2
totals896819039126.420675.410328.396526.220456.762244.310187.092
chr22.dna345537585.27020.1127.06219.3789.47410.4749.076
etext9910527734018.49469.88635.54480.86858.28237.50231.430
gcc-3.0.tar866304009.91253.98642.57843.19636.76019.94815.194
howto394221055.26021.9767.77621.74014.93611.1648.422
jdk13c697288998.65864.45433.74437.91238.90015.56211.012
linux-2.4.5.tar11625472014.72274.98424.17661.26049.14028.35221.646
rctail9611471115117.444114.88655.87273.99263.63433.34823.014
rfc11642190115.39280.10031.02866.69263.14831.20023.554
sprot34.dat10961718618.24883.53029.90068.59651.74232.55024.506
w3c210420157913.02091.49660.71652.58670.74624.21019.238
Maniscalco's Gauntlet Corpus
FilesSizedivsufsort2DCDSKALSsais1sais2
totals6705010312.64860.556671.40620.95869.97010.9007.828
abac2000000.0100.06626.4460.0200.0220.0120.010
abba105006001.61010.32429.3562.65012.5321.4301.024
book1x20153754202.39012.820116.4688.44418.7723.7562.756
fib_s14930352149303524.12215.954223.7563.91016.2342.5081.828
fss10120789083.35213.37098.0983.60813.1362.0241.446
fss928514430.4521.8047.1700.5802.5060.3260.218
houston38400000.0901.852152.0700.4901.1040.2120.138
paper5x809819240.0920.4060.5960.2060.3860.0980.054
test120971520.2241.9788.0340.3382.2460.1620.118
test220971520.1300.9528.0760.3422.2580.1640.122
test320971520.1761.0301.3360.3700.7740.2080.114
Testfiles2
FilesSizedivsufsort2DCDSKALSsais1sais2
totals587202566.44435.07092.61811.70650.1725.7384.510
test1-120971520.2141.2408.1040.3462.3040.1620.118
test1-220971520.1321.0068.1180.3422.2460.1640.118
test2-120971520.0460.9982.4680.1960.8060.0700.056
test2-220971520.0321.1080.1040.1940.8340.0960.056
test3-120971520.2021.0581.3360.3720.7760.2080.116
test3-220971520.1361.0861.5800.3620.7760.2280.126
test4-120971520.1541.2923.6460.3062.5260.1960.146
test4-220971520.1361.3024.3360.3142.4380.2000.168
test4-320971520.3301.1744.6580.4642.2160.1720.152
test5-120971520.3240.7380.6720.2521.8000.1500.142
test5-220971520.1840.7501.1740.2561.7340.1660.152
test6-120971520.2601.0443.8420.3081.6520.1940.178
test6-220971520.1620.8421.2960.2660.7500.1540.140
test720971520.4641.2143.2760.4462.3280.3120.234
test8293601283.66820.21848.0087.28226.9863.2662.608

Testfiles2は最近サフィックスソートのテストに使用しているファイルです。一応こちらも公開しておきます。ファイルサイズの関係上xz形式で圧縮されているのでご注意を。

File: Testfiles2.tar.xz
Size: 207,268 bytes
SHA1: 840774dff1db8b1f9b2d81e7d96f3c4e8dab0cf8

test8以外は2MiBと小さめのサイズですが、線形アルゴリズム以外が高速にソートするのは難しい内容となっています。自作のサフィックスソートに自信のある方は是非とも挑戦してみてください。(ぇ

--------------------------------

先日定兼氏がdbwt(Direct BWT)を公開されたのでそれのテストもしたかったけど、 Ubuntuだとクラッシュしてしまう…ポインタの使い方が環境依存っぽい?これの修正は面倒だなぁ。

|

« libdcs | トップページ | sais-2.4.0 »

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: sais-lite-2.4.0:

« libdcs | トップページ | sais-2.4.0 »