6/17 GCの影響をできるだけ排除するように実装し、測り直しました。
LOUDSTrieの実装が落ち着いてきたので、パトリシアトライ、ダブルアレイ、LOUDSトライの構築、contains速度を測ってみました。
何回か測ってみたけど、だいたいこんな感じ。
| 構築(ms) | contains(ms) | |
|---|---|---|
| java.util.HashSet | 1,042 | 816 |
| PatriciaTrie(UTF-16 char[]) | 891 | 662 |
| MultilayerPatriciaTrie(多層トライ) | 3,538 | 1,354 |
| TailCompactionDoubleArray | 5,082 | 858 |
| OptimizedTailCompactionDoubleArray | 5,760 | 1,022 |
| LOUDSTrie | 922 | 1,025 |
CPUはCore i7 2.5GHz。データはWikipedia日本語タイトル127万件。パトリシアトライの実装はここ、ダブルアレイの実装はここを参照。DoubleArray2つとLOUDSTrieはPatriciaTrieを使って構築してるので、実際の構築時間はPatriciaTrieの分も必要です。
意外とLOUDSTrieが構築、検索共に頑張ってる印象。というかDoubleArrayってもっと速いんじゃなかったっけ。実装が悪いのかも知れませんが。
実装はTrie4J(GitHub)にて公開してます。
