trie4jの最新の実装で、Wikipedia日本語タイトル127万件を格納する速度(build)、全件を照合する速度(contains)、消費サイズ(size)を測ってみました。
| クラス | build(ms) | contains(ms) | size(MB) |
|---|---|---|---|
| java.util.HashSet | 417 | 453 | 160.4 |
| java.util.TreeSet | 402 | 261 | 160.2 |
| PatriciaTrie | 442 | 244 | 104.6 |
| TailPatriciaTrie(SuffixTrieTail) | 1,220 | 271 | 100.8 |
| TailPatriciaTrie(ConcatTail) | 517 | 241 | 86.0 |
| MultilayerPatriciaTrie | 704 | 386 | 91.8 |
| MultilayerPatriciaTrie(packed) | 2,822 | 866 | 82.9 |
| DoubleArray | 471 | 106 | 48.5 |
| TailDoubleArray(SuffixTrieTail) | 3,078 | 175 | 37.3 |
| TailDoubleArray(ConcatTail) | 2,597 | 157 | 42.0 |
| LOUDSTrie(SuffixTrieTail) | 777 | 508 | 18.1 |
| LOUDSTrie(ConcatTail) | 234 | 483 | 22.9 |
- 補足1 - 今回からbuild, contains共に正味の速度を測るようにした(前回まではWikipediaアーカイブからの要素取得も入っていた)ので、HashSetも前回に比べると速くなっている様に見えている。
- 補足2 - TailPatriciaTrie(suffixTrieTail)のサイズが大きいのは、SuffixTrieTailBuilderのトライが消費している分がでかい(約23MB)。TailPatriciaTrieは要素追加に対応するので、SuffixTrieTailBuilderもトライを保持しておく必要がある。
- 補足3 - MultilayerPatriciaTrie(packed)は、ラベルを2層目のトライに追い出した状態。追い出しに時間がかかる(2秒超)が、サイズは10MB弱小さくなる。但し以降要素の追加はできない。また、DoubleArray以降は構築に別のトライを必要とし(今回PatriciaTrieを使用)、構築後は要素の追加はできない(未実装)。
- 補足4 - DoubleArrayやLOUDSTrieで構築後の要素追加を実装する方法がないわけではないが、実用的な速度で追加するのはかなり難しそう。特にWikipedia級のデータになると1要素ずつ何万件もずらすような操作が発生してしまい、性能が出ない。
- 補足5 - DoubleArrayの速度が劇的に改善してるのは、文字へのコード採番方式を変更したため。今までHashMapを使っていたが、TreeSet
(総数カウント、列挙用)とchar[Character.MAX_VALUE](コード変換テーブル)の2つに置き換えた。
意外とHashSetとTreeSetはがんばってるんだなという印象。Trieの利点であるcommonPrefixSearchやpredictiveSearchは使えないけど。あとメモリ消費はやっぱりでかい。あと、HashSetの方が速いと思ってたんだけど、意外にTreeSetの方が速かった。メモリ消費もこの2つでは変わらない。
MultilayerPatriciaTrieは結構実装がんばってるんだけど、packしない前(要素追加可能)はTailPatriciaTrie(concatTail)に負けてるし、pack後(要素追加不可)はDoubleArray, LOUDSTrieにぼろ負け。結構トリッキーな実装してるし、実装ほんとに苦労したから残念なんだけど、現状存在意義無さそう。experimental状態(src.kitchensink)にしようかな。
あとTailDoubleArrayが遅いのは、DoubleArrayと比較して、空き要素の検索に時間がかかるようになるため。DoubleArrayだと1文字だけのラベル、子供1つだけというノードが大量に存在し、それがbase/checkの隙間を埋めてくれる。一方TailDoubleArrayはラベルをTAIL配列に追い出すことによってそういうノードがなくなるため、空きノードの検索対象が増え、速度が遅くなる。
今のところ、
- 要素動的追加必須 -> TailPatriciaTrie(ConcatTail)
- 検索速度重視 -> DoubleArray
- サイズ重視 -> LOUDSTrie(SuffixTrieTail)
