marisa-trie の高速化と実験結果（続き）
概要
昨日の実験結果（marisa-trie の高速化と実験結果 - やた＠はてな日記）では索引のサイズを変更した結果を表にしていたわけですが，索引のサイズ以外にも変更した部分があったため，その部分のみを適用した結果を調べてみました．
変更箇所
select() の実装において，最初の二分探索（512-bit 単位）を（探索範囲が小さいときだけ）線形探索に切り替えました．クイックソートにて，範囲が狭くなると挿入ソートにするのと同じ感覚です．なお，条件文を減らすために，線形探索用の番兵を追加しています．
後は，select() を使わない BitVector から select 用の索引を取り除くなど，空間効率の面で少し修正しています．こちらは元よりアクセスしない部分なので，検索時間には影響なしです．
実験結果
- 実装の種類
- Version: 0.1.0
- Version: 0.1.1（2011-02-18 現在の最新版）
- 無駄な rank() の呼び出しを取り除いたもの
- Version: 0.x.y
- 二分探索を線形探索に切り替え，不要な索引を取り除いたもの
- キー集合
検索時間の単位は [us/key] です．
キーの並び：昇順
------+---------+---------+-------+-------+-------+-------+-------+-------
#tries #nodes size build restore lookup find predict predict
breadth depth
[bytes] [us] [us] [us] [us] [us] [us]
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.0
1 1564294 9850414 3.323 1.265 1.404 1.500 1.605 1.692
2 2087639 7056713 3.593 2.407 2.564 2.678 2.782 2.896
3 2264302 6522559 3.733 2.791 2.948 3.079 3.183 3.279
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.1
1 1564294 9850414 3.314 0.994 1.143 1.238 1.317 1.439
2 2087639 7056713 3.593 1.840 2.006 2.128 2.215 2.320
3 2264302 6522559 3.733 2.102 2.302 2.433 2.512 2.625
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.x.y
1 1564294 9834950 3.340 0.898 1.055 1.160 1.212 1.308
2 2087639 7033077 3.602 1.631 1.814 1.936 1.971 2.102
3 2264302 6496167 3.742 1.901 2.076 2.198 2.233 2.364
------+---------+---------+-------+-------+-------+-------+-------+-------
キーの並び：ランダム順
------+---------+---------+-------+-------+-------+-------+-------+-------
#tries #nodes size build restore lookup find predict predict
breadth depth
[bytes] [us] [us] [us] [us] [us] [us]
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.0
1 1564294 9850414 4.474 2.294 2.747 2.939 3.070 3.166
2 2087639 7056713 4.675 3.733 4.265 4.483 4.588 4.710
3 2264302 6522559 4.814 4.143 4.701 4.963 5.015 5.146
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.1
1 1564294 9850414 4.483 1.971 2.425 2.608 2.695 2.835
2 2087639 7056713 4.675 3.114 3.602 3.794 3.890 4.012
3 2264302 6522559 4.823 3.419 3.951 4.151 4.239 4.361
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.x.y
1 1564294 9834950 4.483 1.866 2.364 2.547 2.608 2.730
2 2087639 7033077 4.692 2.896 3.436 3.628 3.680 3.803
3 2264302 6496167 4.823 3.201 3.759 3.960 4.012 4.134
------+---------+---------+-------+-------+-------+-------+-------+-------思いのほか良い性能を発揮しました．さすがに索引のサイズを大きくした場合と比べれば遅いのですが，Version 0.1.1 と Version 0.x.y を比較すると，Version 0.x.y の方が明らかに高速です．
残念ながら辞書の互換性は失われてしまいますが，辞書のサイズを減らしつつ，検索時間も短縮できるということで，ソースコードを少し修正してから Version 0.2.0 にしようと思っています．
