旧世代 Marisa (0.1.5) と最新 Marisa (0.2.2) の比較
概要
marisa-trie の初期版を公開してから約 2 年になるわけですが，いまだに改良の余地があります．最近は，互換性のことを考慮して，データ構造に手を加えない範囲で改良をしてきました（※）．個別の改良は効果の薄いものばかりですが，古い実装と最新の実装を比べてみると，かなり速くなっていることが分かります．
※ 次にデータ構造を変更するとすれば，インタフェースも一緒に変更するでしょうから，別ライブラリとして公開することになると思います．とはいえ，先に片付けるべき用事があったり体調を崩したりで，なかなかまとまった時間を確保できずに停滞中です．
ベンチマーク
ベンチマークの設定
ベンチマークをおこなった環境は以下の通りです．
※ これまでの経験から，gcc では差が小さくなることが予想されます．
ベンチマークに使ったデータは以下の通りです．
ベンチマーク結果において，#tries はパトリシアトライの再帰構造の深さを示しています．size は構築された辞書のサイズ，build は辞書を構築する速度，lookup は文字列を入力して ID を受け取る速度，reverse は ID を入力してキーを受け取る速度を示しています．[K/s] は 1 秒あたりに処理されたキー数を意味しています．また，marisa-0.1.5 のサイズおよび速度を基準として，marisa-0.2.2 のサイズおよび速度を百分率で示しています．
marisa-trie 以外との比較については トライ（ダブル配列，簡潔データ構造）と STL コンテナの比較（最新版） - ny23の日記 が参考になります．
marisa-0.1.5 のベンチマーク結果
| JAWIKI | size | build | lookup | reverse |
|---|---|---|---|---|
| #tries | [bytes] | [K/s] | [K/s] | [K/s] |
| 1 | 11,539,596 | 797.11 | 2131.47 | 2370.8 |
| 2 | 8,406,184 | 744.32 | 1264.81 | 1295.63 |
| 3 | 7,773,651 | 704.11 | 1097.04 | 1145.2 |
| 4 | 7,562,348 | 689.13 | 1086.97 | 1116.74 |
| 5 | 7,475,662 | 670.21 | 1076.86 | 1106.27 |
| JAWIKI-R | size | build | lookup | reverse |
|---|---|---|---|---|
| #tries | [bytes] | [K/s] | [K/s] | [K/s] |
| 1 | 11,539,596 | 510.41 | 916.41 | 1142.68 |
| 2 | 8,406,184 | 491.92 | 646.27 | 748.77 |
| 3 | 7,773,651 | 477.63 | 599.31 | 675.92 |
| 4 | 7,562,348 | 472.99 | 577.16 | 673.53 |
| 5 | 7,475,662 | 473.95 | 584.34 | 662.64 |
marisa-0.2.2 (svn-r133) のベンチマーク結果
| JAWIKI | size | - | build | - | lookup | - | reverse | - |
|---|---|---|---|---|---|---|---|---|
| #tries | [bytes] | [%] | [K/s] | [%] | [K/s] | [%] | [K/s] | [%] |
| 1 | 11,588,904 | 100.43 | 1141.65 | 143.22 | 2954.62 | 138.62 | 2707.53 | 114.20 |
| 2 | 8,467,920 | 100.73 | 948.44 | 127.42 | 1828.06 | 144.53 | 1704.48 | 131.56 |
| 3 | 7,841,664 | 100.87 | 895.99 | 127.25 | 1626.9 | 148.30 | 1542.09 | 134.66 |
| 4 | 7,633,584 | 100.94 | 869.63 | 126.19 | 1559.46 | 143.47 | 1485.36 | 133.01 |
| 5 | 7,548,584 | 100.98 | 865.95 | 129.21 | 1553.64 | 144.28 | 1463.36 | 132.28 |
| JAWIKI-R | size | - | build | - | lookup | - | reverse | - |
|---|---|---|---|---|---|---|---|---|
| #tries | [bytes] | [%] | [K/s] | [%] | [K/s] | [%] | [K/s] | [%] |
| 1 | 11,588,904 | 100.43 | 742.45 | 145.46 | 1166.96 | 127.34 | 1373.41 | 120.19 |
| 2 | 8,467,920 | 100.73 | 656.12 | 133.38 | 852.21 | 131.87 | 972.2 | 129.84 |
| 3 | 7,841,664 | 100.87 | 628.15 | 131.51 | 790.11 | 131.84 | 906.64 | 134.13 |
| 4 | 7,633,584 | 100.94 | 620.4 | 131.17 | 785.48 | 136.09 | 893.51 | 132.66 |
| 5 | 7,548,584 | 100.98 | 647.76 | 136.67 | 783.16 | 134.02 | 883.8 | 133.38 |
