Succinct なトライの実験 その 8（select() の計算にテーブルを導入）
…懲りることなく sumire-tries に変更を加えました．
今回の変更では，select() 内のループによる計算を，テーブル参照に置き換えました．入力のパターンが少ないとき，全パターンあるいは一部パターンの計算結果を保存しておくことで高速化するという一般的な方法です．
修正版は既にアップロードしてあります．
修正箇所は，BasicSuccinctBitVector, SimplifiedSuccinctBitVector, HybridSuccinctBitVector の select_1() と select_0() です．計算結果のテーブルについては，SelectTable というクラスを新たに定義して，static な関数に static な変数として持たせました．
実験結果は以下のとおりです．
| ID | コーパス | キー数 | 平均キー長（bytes） |
|---|---|---|---|
| jawiki | 日本語版 Wikipedia タイトル一覧 | 942,390 | 20.4 |
| enwiki | 英語版 Wikipedia タイトル一覧 | 6,437,567 | 18.6 |
| ja1gms | 日本語版 Google n-gram コーパスの 1-gram | 2,565,427 | 18.8 |
| en1gms | 英語版 Google n-gram コーパスの 1-gram | 13,588,391 | 8.3 |
次の表は，すべてのキーを辞書順に検索するのに要した時間（秒）を示しています．
| ラベル昇順 | jawiki | enwiki | ja1gms | en1gms |
|---|---|---|---|---|
| BasicTrie | 0.84 | 6.36 | 2.81 | 10.29 |
| SuccinctTrie | 3.49 | 33.34 | 12.71 | 57.14 |
| LoudsTrie（旧） | 2.61 | 17.40 | 7.44 | 21.66 |
| LoudsTrie（新） | 2.40 | 16.27 | 6.99 | 20.94 |
| （新）/（旧） | 92.0% | 93.5% | 94.0% | 96.7% |
| LoudsPlusTrie（旧） | 2.48 | 16.75 | 7.14 | 20.66 |
| LoudsPlusTrie（新） | 2.22 | 15.16 | 6.48 | 19.48 |
| （新）/（旧） | 89.5% | 90.5% | 90.8% | 94.3% |
| 出現頻度降順 | jawiki | enwiki | ja1gms | en1gms |
| BasicTrie | 0.36 | 2.60 | 1.04 | 4.81 |
| SuccinctTrie | 0.77 | 5.52 | 2.40 | 13.05 |
| LoudsTrie（旧） | 1.92 | 12.29 | 5.03 | 14.03 |
| LoudsTrie（新） | 1.73 | 11.12 | 4.55 | 13.21 |
| （新）/（旧） | 90.1% | 90.5% | 90.5% | 94.1% |
| LoudsPlusTrie（旧） | 1.82 | 11.77 | 4.74 | 13.32 |
| LoudsPlusTrie（新） | 1.56 | 10.21 | 4.13 | 12.14 |
| （新）/（旧） | 85.7% | 86.7% | 87.1% | 91.1% |
次の表は，すべてのキーをランダム順に検索するのに要した時間（秒）を示しています．
| ラベル昇順 | jawiki | enwiki | ja1gms | en1gms |
|---|---|---|---|---|
| BasicTrie | 1.32 | 12.17 | 4.29 | 20.89 |
| SuccinctTrie | 5.61 | 67.47 | 21.09 | 123.48 |
| LoudsTrie（旧） | 4.45 | 41.04 | 12.91 | 43.25 |
| LoudsTrie（新） | 4.10 | 39.77 | 12.38 | 39.43 |
| （新）/（旧） | 92.1% | 96.9% | 95.9% | 91.2% |
| LoudsPlusTrie（旧） | 4.31 | 46.46 | 13.28 | 43.61 |
| LoudsPlusTrie（新） | 3.96 | 45.03 | 12.28 | 41.54 |
| （新）/（旧） | 91.9% | 96.9% | 92.5% | 95.3% |
| 出現頻度降順 | jawiki | enwiki | ja1gms | en1gms |
| BasicTrie | 0.75 | 6.80 | 2.42 | 13.38 |
| SuccinctTrie | 2.35 | 23.07 | 7.06 | 40.69 |
| LoudsTrie（旧） | 3.80 | 35.33 | 10.27 | 32.61 |
| LoudsTrie（新） | 3.42 | 34.31 | 9.69 | 31.45 |
| （新）/（旧） | 90.0% | 97.1% | 94.4% | 96.4% |
| LoudsPlusTrie（旧） | 3.70 | 40.52 | 10.69 | 35.18 |
| LoudsPlusTrie（新） | 3.42 | 38.88 | 9.77 | 33.27 |
| （新）/（旧） | 92.4% | 96.0% | 91.4% | 94.6% |
検索時間が 3 〜 14% 短縮されました．select() の高速化なので，キーが長くて少ない場合に効果が高くなっています．
索引を追加したり（2009-11-03 - やた＠はてな日記），ノードを並べ替えたり（2009-11-05 - やた＠はてな日記），無駄な計算を取り除いたり（2010-01-17 - やた＠はてな日記，2010-01-27 - やた＠はてな日記），計算結果を使い回したり（2010-01-19 - やた＠はてな日記），あらかじめ計算しておいたり（今回），いろいろとやってきました．最初の頃の実験結果と比べると，検索時間が半分以下に短縮されているところもあり，実装段階における工夫や失敗が性能を左右してしまうことが良く分かります．
