自作ウェーブレット木ライブラリshellinfordのパフォーマンス測定をしてみた

自作ウェーブレット木ライブラリshellinfordのパフォーマンス測定をしてみた。

shellinford - shellinford: succinct document retrieval library - Google Project Hosting


テスト用のデータは以下のようにして生成した。

$$ shuf -i 1-100000000 -n 10000000 > test_bv.txt
$$ perl -e 'while($i++ < 10000000) { $x=int(rand(256); print "$x\n") } ' > test_wt.txt

テストに用いたコードはshellinford/sampleに置いておいた。

$$ make

$$ ./make_bit_vector test_bv.dic < test_bv.txt
$$ ./rank_bit_vector test_bv.dic
$$ ./select_bit_vector test_bv.dic

$$ ./make_wavelet_tree test_wt.dic < test_wt.txt
$$ ./rank_wavelet_tree test_wt.dic
$$ ./select_wavelet_tree test_wt.dic

結果は以下のとおり。

rank_bit_vector: 1.30s
select_bit_vector: 4.45s
rank_wavelet_tree: 27.17s
select_wavelet_tree: 879.99s

ビットベクトル→ウェーブレット木でrankが20倍遅くなっている。うむむ。これはもうちょっと改善したいかも。
selectは実装が適当(ただの二分探索)ということもあってかなり遅いけどあまり使わないからいいか。。。