« IS法 その2 | トップページ | CMake: uninstall target »

IS法 その3

さて、今回はキャッシュ効率の改善のために induceSA を書き換えてみました。使用した方法は、itssort で用いられているものと基本的に同じです。

File: is3.zip
Size: 15,533 bytes
SHA1: 97d598e28651a6c5b5555ff405a0b530c0ae5b5e

IS1から3を使って Suffix array の構築時間を測定した結果が以下になります。

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS1 - ほぼオリジナルと同じ NZC Induced sorting algorithm
  • IS2 - 配列tを排除したIS法
  • IS3 - 今回の改良したIS法
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
FilesDCDSIS1IS2IS3KALS
totals722.19846.89435.07342.10266.99527.85510.05
chr22.dna19.987.0614.8612.1410.8317.329.35
etext9973.0832.4562.8147.8039.6374.7551.50
gcc-3.0.tar54.9634.1432.9826.5621.2141.6536.80
howto22.647.8216.7613.5811.4121.0314.81
jdk13c56.0828.0827.2522.4516.4334.4835.73
linux-2.4.5.tar74.1824.2446.5637.0930.0559.6049.05
rctail96110.3056.0558.4045.5133.5570.8463.63
rfc82.4427.9854.5341.4832.7665.4755.85
sprot34.dat85.7229.6958.4444.3534.5169.0451.63
w3c281.7548.6241.7034.1525.5053.3470.90
abac0.0626.480.020.000.000.020.02
abba9.8929.512.602.221.402.5112.48
book1x2013.0795.356.165.433.847.4418.68
fib_s1493035216.18177.075.564.242.553.8816.23
fss1013.4582.754.153.432.003.5313.06
fss91.444.820.500.360.280.582.50
houston1.81114.110.350.230.180.501.08
paper5x800.380.620.110.080.080.170.36
test10.948.060.250.190.150.332.04
test20.948.070.260.210.160.322.06
test31.021.340.260.200.150.390.77
test41.021.590.280.230.170.390.77
test50.860.990.280.170.150.270.75

普通のファイルでも Deep-Shallow sorting algorithm とほぼ互角なので、やっとそれなりの速度になったかな。しかし、上位のSACAにはまだ遠く及ばず・・。

|

« IS法 その2 | トップページ | CMake: uninstall target »

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: IS法 その3:

« IS法 その2 | トップページ | CMake: uninstall target »