(続)LOUDSトライのライブラリの性能を比較してみた
LOUDSトライを比較した記事を書いたところ@overlast氏からwikipediaタイトルのような偏りの少ないデータでも評価してはどうか、という賢明なアドバイスを頂いたので試してみた。
からwikipediaタイトルを取得した。
$$ wc -l jawiki-latest-all-titles-in-ns0 1231018 jawiki-latest-all-titles-in-ns0
約123万件ある。これを用いてトライを作成すると以下のようなデータサイズとなった。
元データ : 26960268 byte marisa-trie : 7,199,728 byte ux-trie : 10,364,932 byte erika-trie : 18,866,382 byte
共通部分の多い住所データに比べると圧縮率は低いが、それでも元データに比べると十分小さくなっている。またライブラリの性能差は住所の場合とほぼ同じ。
次にcommon-prefix-searchについて。
marisa-trie : 11.9 sec ux-trie : 57.2 sec erika-trie : 20.7 sec
最後にpredictive-search
marisa-trie : 13.5 sec ux-trie : 45.8 sec erika-trie : 28.4 sec
どちらの検索も、データ量がおよそ10倍になっているため線形に検索時間が増加して10倍程度の時間がかかっている(erikaはpredictive-searchが10倍より遅いが、これはerikaのpredictive-searchが文字列をstringで返しているからかも。erikaではreverse-lookupのコストが大きいのでこういう仕様になっている)。
というわけで今回の実験でもmarisa大勝利だった。すごい・・・。
