Hatena::ブログ(Diary)

ny23の日記 このページをアンテナに追加 RSSフィード

2011-01-10 marisa-trie 強いな

トライ(ダブル配列,簡潔データ構造)と STL コンテナの比較(最新版)

|  トライ(ダブル配列,簡潔データ構造)と STL コンテナの比較(最新版)を含むブックマーク  トライ(ダブル配列,簡潔データ構造)と STL コンテナの比較(最新版)のブックマークコメント

[2011/11/30 更新; std::(unordered_)map でメモリ使用量を見積もる - ny23の日記に従い,STL コンテナのメモリ使用量を計測]

[2011/02/21 更新: marisa-trie 0.1.3; 発表資料(Prefix/Patricia Trie の入れ子による辞書圧縮) - やた@はてな日記 にてこの記事の実験結果を引用されているので,以後原則更新しないこととする.なお,marisa-trie は 検索時間が短くなりました - やた@はてな日記 にあるように,marisa-0.2.0-beta3 以降ではさらに検索が速くなっています.]

[2011/02/18 更新: marisa-trie の仕様変更に伴い,追記の記述を整合性が取れるよう変更; 最新版では未確認]

id:s-yata さんが marisa-trie を公開されたので,例によってベンチマークを取った結果を公開しておきます.以前,ux-trie のバグ絡みでコードを読んだとき,TAIL 部でトライの段数をもっと増やすとどうなるのかなと思っていたところだったので,非常に良いタイミングでした.marisa-trie でトライを構築する際のパラメタは,トライの数(build の第三引数)のところしか変えていません.Build は構築時間,Search は辞書順,Search* はランダム順の検索時間.Wikipedia-en は 20090929 のもの.

個々のライブラリへのリンクや細かい表記の意味,marisa-trie 以外の結果に関する考察は以下の記事を参照.

個人的には marisa-trie は圧縮率の高さよりも,その検索速度の速さにより魅力を感じます.

[追記] marisa-trie で patricia trie -> prefix tree にすると,Wikipedia-en ではトライのサイズが1-2割増え,検索速度も1-2割落ちます(郵便番号辞書の方では,トライのサイズはほぼ同じで検索速度は prefix tree の方が逆に僅かに高速).次に,TAIL 部を文字列化しないでそのままトライで保持すると,(Wikipedia-en では)トライの数が一つの時のみサイズが大幅に増え(tx と同じぐらい),検索速度も特にランダム検索順で大きく(1/2 ぐらいまで)低下します.この辺り,ほぼ予想通り*1の挙動です.

======================================================================
 Wikipedia-en 記事タイトル |  Build  | Search  | Search* | Size [bytes]
 #keys=6,890,514         |         |         |         |  136,297,337
======================================================================
 sorted keys
  Darts 0.32             | 14.283s |  0.527s |  6.694s |  552,547,920
  darts-clone 0.32g      |  6.575s |  0.625s |  5.946s |  258,735,104
  darts-clone 0.32g  v:1 | 15.917s |  0.764s |  6.227s |   95,080,448
 *darts-clone 0.32e5     | 14.532s |  0.924s |  5.890s |  113,360,140
 *darts-clone 0.32e5 v:1 | 13.996s |  0.852s |  5.562s |   87,122,880
  darts-clone 0.32e5 huge|  4.128s |  0.554s |  5.920s |  147,491,712
 *DASTrie 1.0 -c         |      NA |      NA |      NA |           NA
  DASTrie 1.0            |  4.951s |  1.012s |  6.212s |  157,593,742
 *doar 0.0.13 static     |  8.684s |  0.672s |  5.664s |  123,000,249
  --------------------------------------------------------------------
 *doar 0.0.13 dynamic    | +3.964s |  0.670s |  5.757s | +123,000,249
  dda                    |  3.222s |  0.612s |  7.191s |  517,091,328
 ---------------------------------------------------------------------
  map           k:char*  |  2.905s |  2.122s | 17.352s | ~515,663,184
  map           k:string | 10.482s |  6.041s | 25.479s | >515,663,184
  unordered_map k:char*  |  6.271s |  2.013s |  3.638s | ~460,539,072
  unordered_map k:string |  7.303s |  2.182s |  4.540s | >460,539,072
  --------------------------------------------------------------------
  marisa 0.1.3  #tries=1 | 23.118s |  4.087s | 16.491s |   49,350,092
  marisa 0.1.3  #tries=2 | 25.411s |  6.921s | 21.707s |   37,743,122
  marisa 0.1.3  #tries=3 | 25.786s |  7.524s | 22.945s |   35,767,947
  marisa 0.1.3  #tries=10| 26.206s |  7.841s | 23.633s |   34,802,056
  tx 0.18                | 18.611s | 24.969s | 62.604s |   87,520,717
  ux 0.1.2               | 46.515s | 45.921s | 67.670s |   49,134,003
  ux 0.1.2 isTailUX=false| 16.744s | 30.197s | 49.810s |  105,423,225
 =====================================================================
 randomized keys
  doar 0.0.13 dynamic    |+24.902s |  1.952s |  5.645s | +123,000,249
  dda                    | 10.017s |  3.647s |  8.589s |  517,091,328
  --------------------------------------------------------------------
  map           k:char*  | 18.576s |  3.637s | 21.164s | ~515,663,184
  map           k:string | 27.897s |  8.417s | 30.713s | >515,663,184
  unordered_map k:char*  |  6.360s |  3.754s |  3.646s | ~460,539,072
  unordered_map k:string |  7.302s |  4.605s |  4.549s | >460,539,072
  --------------------------------------------------------------------
  marisa 0.1.3  #tries=1 | 32.635s |  5.381s | 16.232s |   49,350,092
  marisa 0.1.3  #tries=2 | 34.408s |  8.400s | 21.977s |   37,743,122
  marisa 0.1.3  #tries=3 | 34.884s |  9.232s | 22.945s |   35,767,947
  marisa 0.1.3  #tries=10| 35.405s |  9.556s | 23.660s |   34,802,056
  tx 0.18                | 38.718s | 26.434s | 62.358s |   87,520,717
  ux 0.1.2               | 63.228s | 47.239s | 68.075s |   49,134,003
  ux 0.1.2 isTailUX=false| 33.159s | 31.547s | 50.461s |  105,423,225
======================================================================

======================================================================
 郵便番号辞書              |  Build  | Search  | Search* | Size [bytes]
 #keys=118,821           |         |         |         |      950,568          
======================================================================
 sorted keys
  Darts 0.32             |  0.039s |  0.003s |  0.012s |    2,156,576
  darts-clone 0.32g      |  0.038s |  0.003s |  0.010s |    1,069,056
  darts-clone 0.32g  v:1 |  0.020s |  0.003s |  0.007s |      106,496
 *darts-clone 0.32e5     |  0.171s |  0.004s |  0.013s |    1,154,676
 *darts-clone 0.32e5 v:1 |  0.165s |  0.004s |  0.011s |      650,116
  darts-clone 0.32e5 huge|  0.141s |  0.004s |  0.013s |    1,363,656
 *DASTrie 1.0 -c         |  2.226s |  0.010s |  0.018s |    1,248,609
  DASTrie 1.0            |  2.354s |  0.010s |  0.019s |    1,411,783
 *doar 0.0.13 static     |  0.064s |  0.004s |  0.013s |    1,204,561
  --------------------------------------------------------------------
 *doar 0.0.13 dynamic    | +0.091s |  0.004s |  0.013s |   +1,204,561
  dda                    |  0.023s |  0.004s |  0.014s |    2,129,920
  --------------------------------------------------------------------
  map           k:char*  |  0.043s |  0.028s |  0.074s |   ~7,604,544
  map           k:string |  0.137s |  0.072s |  0.147s |   >7,604,544
  unordered_map k:char*  |  0.023s |  0.010s |  0.027s |   ~6,653,976
  unordered_map k:string |  0.039s |  0.013s |  0.038s |   >6,653,976
  --------------------------------------------------------------------
  marisa 0.1.3  #tries=1 |  0.083s |  0.033s |  0.059s |      232,729
  marisa 0.1.3  #tries=2 |  0.083s |  0.034s |  0.060s |      232,111
  marisa 0.1.3  #tries=3 |  0.083s |  0.034s |  0.060s |      232,270
  marisa 0.1.3  #tries=10|  0.083s |  0.034s |  0.060s |      233,404
  tx 0.18                |  0.096s |  0.090s |  0.129s |      222,888
  ux 0.1.2               |  0.092s |  0.158s |  0.187s |      220,209
  ux 0.1.2 isTailUX=false|  0.092s |  0.157s |  0.187s |      222,165
 =====================================================================
 randomized keys
 *doar 0.0.13 dynamic    | +0.104s |  0.009s |  0.013s |   +1,204,561
  dda                    |  0.036s |  0.010s |  0.013s |    2,129,920
  --------------------------------------------------------------------
  map           k:char*  |  0.068s |  0.035s |  0.085s |   ~7,604,544
  map           k:string |  0.143s |  0.092s |  0.168s |   >7,604,544
  unordered_map k:char*  |  0.029s |  0.023s |  0.027s |   ~6,653,976
  unordered_map k:string |  0.049s |  0.036s |  0.039s |   >6,653,976
  --------------------------------------------------------------------
  marisa 0.1.3  #tries=1 |  0.121s |  0.036s |  0.059s |      232,729
  marisa 0.1.3  #tries=2 |  0.121s |  0.037s |  0.060s |      232,111
  marisa 0.1.3  #tries=3 |  0.121s |  0.037s |  0.060s |      232,270
  marisa 0.1.3  #tries=10|  0.121s |  0.037s |  0.060s |      233,404
  tx 0.18                |  0.168s |  0.097s |  0.129s |      222,888
  ux 0.1.2               |  0.174s |  0.165s |  0.187s |      220,209
  ux 0.1.2 isTailUX=false|  0.174s |  0.165s |  0.187s |      222,165
=====================================================================
(compiled with gcc 4.6.0 20110212, -O2 -march=core2 -m64)

*1:トライの数を一つにして,TAIL 部の処理を(速度の速い)文字列の照合のみで済ませる場合に検索速度は最速となり,TAIL 部のトライの数を増やせば増やすほど,TAIL で文字列照合する部分が減っていくので,TAIL なしの単純なトライの検索速度に近づく.