自作ウェーブレット木ライブラリ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は実装が適当(ただの二分探索)ということもあってかなり遅いけどあまり使わないからいいか。。。