Darts と Darts-clone 0.32g を比べるために，辞書の構築時間とサイズ，および検索にかかる時間を計測しました．大雑把にまとめると，辞書のサイズ，検索時間ともに Darts-clone の方が優秀ということになります．
Darts-clone による検索が高速な理由としては，辞書が小さくなることによって，キャッシュの利用効率が向上したことが考えられます．このことは，辞書がキャッシュに収まるかどうかという状況において Darts と Darts-clone の違いが顕著になっていることから確認できます．また，キーをランダム順に検索したときの所要時間からも確認できます．
もう 1 つの理由として考えられるのは，終端ノードの有無をフラグとして各ノードに持たせていることが挙げられます．このフラグは，終端文字による遷移の確認を省略するための工夫であり，特に commonPrefixSearch() において高い効果を発揮します．
ただし，Darts-clone ではオフセットやラベルの取り出しに論理演算を必要とするため，わずかながらオーバーヘッドが大きくなっています．また， traverse() を繰り返し呼び出す場合， traverse() をインライン化できず，検索時間が悪化することがあるようです．
注意：検索時間については，辞書とキャッシュのサイズ，キャッシュとメモリのレイテンシ，検索するキーの偏り，コンパイラによるインライン化など，影響する要素がとても多く，環境によっては大きく変化する可能性があります．
実験では，いくつかのキー集合に対する辞書を Darts と Darts-clone により構築し，サイズと構築時間を調べた後，各キーを辞書順に検索するのに要する時間と，ランダム順に検索するのに要する時間を計測しました． traverse() については，各キーを 1 バイトずつ traverse() に渡して探索するのに要した時間になっています．
※ 計測には Darts-clone に付属のツール darts-benchmark を使用しました．
実験環境の OS は 64-bit 版 Ubuntu 9.04 で，コンパイラは gcc 4.3.3 です．
| PC 型番 | CPU 型番 | CPU 周波数 |
|---|---|---|
| Dell Precision T3400 | Core 2 Quad Q9550 | 2.83GHz |
実験には，日本語と英語のキー集合に加えて，7 桁郵便番号を使用しました．
| ID | 出典 | 内容 | キー数 | サイズ [bytes] |
補足 |
|---|---|---|---|---|---|
| JA1 | ipadic-2.6.3 | 見出し語 | 159,442 | 2,892,008 | 漢字かな混じり |
| JA2 | 日本語版 Wikipedia | タイトル | 865,489 | 18,439,874 | タイトル一覧 |
| JA3 | 日本語版 Google N-gram | 形態素 | 2,565,427 | 50,784,220 | unigram のみ |
| EN1 | !WordNet-3.0 | 英語 | 147,306 | 1,839,597 | 英単語 |
| EN2 | 英語版 Wikipedia | タイトル | 5,716,820 | 111,542,495 | タイトル一覧 |
| EN3 | 英語版 Google N-gram | 単語 | 13,588,391 | 125,937,836 | unigram のみ |
| DIG | 郵便番号辞書 | 7 桁郵便番号 | 118,559 | 948,472 | 2008 年 6 月 30 日更新版 |
各コーパスの詳細については，以下の URL で確認することができます．
- JA1: https://ja.osdn.net/projects/ipadic/
- JA2: https://dumps.wikimedia.org/jawiki/
- JA3: https://googlejapan.blogspot.com/2007/11/n-gram.html
- EN1: https://wordnet.princeton.edu/
- EN2: https://dumps.wikimedia.org/enwiki/
- EN3: https://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html
- DIG: https://www.post.japanpost.jp/zipcode/download.html
実験の結果は，以下のようになりました．
- 辞書のサイズ：キロバイト単位
- 構築時間：ナノ秒単位
- 辞書の構築に要した時間をキー数で割った値を示しています．
- 検索時間：ナノ秒単位
- キーを 1 つ検索するのに要した時間の平均値を示しています．
no values は，Darts-clone において，すべてのキーに 0 を関連付けたときの実験結果を示しています．no values 以外は，関連付ける値を指定しなかったときの結果を示しています．
- 辞書サイズ
[KB]と構築時間[ns/key]
| corpus | version | size | build() |
|---|---|---|---|
| JA1 | Darts | 7,023 | 828 |
| Darts-clone | 3,336 | 368 | |
| no values | 1,272 | 690 | |
| JA2 | Darts | 84,911 | 2,950 |
| Darts-clone | 40,004 | 1,326 | |
| no values | 14,981 | 2,441 | |
| JA3 | Darts | 162,689 | 2,035 |
| Darts-clone | 76,778 | 1,181 | |
| no values | 25,578 | 1,797 | |
| EN1 | Darts | 7,526 | 1,426 |
| Darts-clone | 3,527 | 747 | |
| no values | 1,293 | 950 | |
| EN2 | Darts | 513,873 | 2,518 |
| Darts-clone | 240,634 | 1,058 | |
| no values | 88,129 | 2,701 | |
| EN3 | Darts | 406,358 | 927 |
| Darts-clone | 193,324 | 421 | |
| no values | 65,628 | 899 | |
| DIG | Darts | 2,153 | 337 |
| Darts-clone | 1,067 | 337 | |
| no values | 106 | 253 |
構築時間については，Darts-clone の方が Darts より短くなっています．ただし，関連付ける値として各キーにユニークな値を指定した場合，Darts-clone の構築時間は，以下のように遅くなります．
| corpus | JA1 | JA2 | JA3 | EN1 | EN2 | EN3 | DIG |
|---|---|---|---|---|---|---|---|
build() [ns/key] |
1,196 | 5,942 | 4,728 | 2,037 | 6,666 | 2,001 | 843 |
値の指定によって構築時間が大きく変化する理由は，Darts-clone が辞書のデータ構造として Directed Acyclic Word Graph (DAWG) を採用するからです．DAWG は値の重複率が高いトライを圧縮するのに適したデータ構造ですが，DAWG を構築してからダブル配列に変換する必要があります．特に，値に重複がない場合，トライと DAWG は同じになるので，構築の手間が増えるだけになってしまいます．そのため，現在の実装（0.32g）では，値の指定がない場合，すなわち値が重複しないことが明らかな場合は，DAWG を経由することなくダブル配列を構築するようにしています．結果として，ユニークな値を指定したときの構築時間が最も長くなります．
上述の通り，no values で辞書が小さくなっている理由も DAWG です．DAWG はトライの共通部分木を併合して得られるグラフなので，関連付ける値が同じキーのみを併合することができます．つまり，各キーに値を関連付ける必要がないときや，関連付ける値の種類が少ないときは，Darts-clone を使うことで，辞書のサイズをさらに抑えることができます．
- 検索時間（辞書順）
[ns/key]
| corpus | version | exactMatchSearch() | commonPrefixSearch() | traverse() |
|---|---|---|---|---|
| JA1 | Darts | 48.9 | 64.8 | 45.5 |
| Darts-clone | 33.1 | 43.8 | 52.8 | |
| no values | 31.1 | 41.8 | 51.1 | |
| JA2 | Darts | 98.4 | 135.3 | 119.1 |
| Darts-clone | 94.6 | 125.0 | 144.6 | |
| no values | 107.2 | 134.0 | 157.7 | |
| JA3 | Darts | 88.1 | 131.2 | 109.1 |
| Darts-clone | 85.8 | 109.1 | 126.7 | |
| no values | 92.8 | 117.9 | 135.1 | |
| EN1 | Darts | 70.0 | 99.4 | 90.2 |
| Darts-clone | 54.7 | 78.0 | 97.0 | |
| no values | 54.3 | 78.0 | 96.6 | |
| EN2 | Darts | 90.9 | 128.9 | 124.3 |
| Darts-clone | 88.5 | 118.1 | 140.6 | |
| no values | 101.0 | 131.3 | 155.3 | |
| EN3 | Darts | 51.9 | 72.5 | 63.3 |
| Darts-clone | 40.5 | 56.7 | 70.3 | |
| no values | 44.2 | 60.3 | 75.1 | |
| DIG | Darts | 18.8 | 26.8 | 43.3 |
| Darts-clone | 24.2 | 42.6 | 36.2 | |
| no values | 24.1 | 36.2 | 35.7 |
- 検索時間（ランダム順）
[ns/key]
| corpus | version | exactMatchSearch() | commonPrefixSearch() | traverse() |
|---|---|---|---|---|
| JA1 | Darts | 170.4 | 223.4 | 209.1 |
| Darts-clone | 76.2 | 91.1 | 104.5 | |
| no values | 60.5 | 75.4 | 86.0 | |
| JA2 | Darts | 620.8 | 822.4 | 774.6 |
| Darts-clone | 516.4 | 533.9 | 578.3 | |
| no values | 488.1 | 502.3 | 546.5 | |
| JA3 | Darts | 693.8 | 845.9 | 810.8 |
| Darts-clone | 584.7 | 608.1 | 627.6 | |
| no values | 561.3 | 576.9 | 608.1 | |
| EN1 | Darts | 228.5 | 307.0 | 285.7 |
| Darts-clone | 111.3 | 139.9 | 157.4 | |
| no values | 93.0 | 122.4 | 137.1 | |
| EN2 | Darts | 796.9 | 977.1 | 967.8 |
| Darts-clone | 674.2 | 717.7 | 756.5 | |
| no values | 731.6 | 772.0 | 817.1 | |
| EN3 | Darts | 545.3 | 646.1 | 635.8 |
| Darts-clone | 453.3 | 512.2 | 525.4 | |
| no values | 457.7 | 500.4 | 519.6 | |
| DIG | Darts | 40.2 | 57.0 | 83.5 |
| Darts-clone | 43.9 | 64.9 | 60.7 | |
| no values | 37.5 | 48.2 | 49.9 |