2012/06/15

各種トライの速度比較

6/17 GCの影響をできるだけ排除するように実装し、測り直しました。

LOUDSTrieの実装が落ち着いてきたので、パトリシアトライ、ダブルアレイ、LOUDSトライの構築、contains速度を測ってみました。

何回か測ってみたけど、だいたいこんな感じ。

構築(ms)contains(ms)
java.util.HashSet1,042816
PatriciaTrie(UTF-16 char[])891662
MultilayerPatriciaTrie(多層トライ)3,5381,354
TailCompactionDoubleArray5,082858
OptimizedTailCompactionDoubleArray5,7601,022
LOUDSTrie9221,025

CPUはCore i7 2.5GHz。データはWikipedia日本語タイトル127万件。パトリシアトライの実装はここ、ダブルアレイの実装はここを参照。DoubleArray2つとLOUDSTrieはPatriciaTrieを使って構築してるので、実際の構築時間はPatriciaTrieの分も必要です。

意外とLOUDSTrieが構築、検索共に頑張ってる印象。というかDoubleArrayってもっと速いんじゃなかったっけ。実装が悪いのかも知れませんが。

実装はTrie4J(GitHub)にて公開してます。

コメントを投稿