最新の各種トライ速度比較

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)

と使い分けるのが良さそうです。

各種トライの速度比較

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)にて公開してます。

ダブルアレイのサイズ比較

今勉強＆実装してるダブルアレイのサイズを測ってみました。詳しい話はまた今度(というつつパトリシアトライの解説もまだ途中だけど・・・)。

データはパトリシアトライと同じく、Wikipedia日本語タイトルの127万エントリ。文字列は全てcharで保持してます。また、予めパトリシアトライを構築し、それをもとにダブルアレイを構築してます。

以下の表にまとめます。

実装	配列要素数(base/check等)	TAIL配列要素数	全体サイズ
DoubleArray*1	5,668,704	0	48,547,151
TailDoubleArray*2	1,679,616	4,651,339(capacity: 4,718,590)	31,947,268
TailCompactionDoubleArray*3	1,679,616	1,797,866(capacity: 2,359,294)	27,226,058
OptimizedTailCompactionDoubleArray*4	1,519,679	1,797,866	21,177,535

*1 - シンプルなダブルアレイ実装。空き要素の位置を記録して構築高速化、孫ノードの多い子ノードを先に登録してメモリ利用効率向上、TAIL無し。
*2 - TAILあり。
*3 - 接尾辞トライによるTAIL圧縮。
*4 - 構築終了時に配列サイズをtrim。checkの要素をintではなくcharにする。

パトリシアトライの時に苦労していたのが嘘のように、シンプルな実装でいきなり48MBを叩きだしてます。前回Javaではオブジェクト数大事、と連呼してましたが、トライを保持する方法がノードオブジェクトをポインタでつなぐ方法から、int配列2つに変わったことで、TAIL圧縮すらしてないのに約34MB減りました。

結論: やっぱりオブジェクト数大事

さらにTAIL配列、TAIL配列圧縮等工夫していくことで、最終的に21MBまで小さくなっています。これ以上は、ダブルアレイの仕組みそのものを変えないと大幅な圧縮は期待できず、行き着く先は、トライの保持をビットベクタで行うLOUDS(Level Order Unary Degree Sequence。参考)です。なので今後はLOUDSを勉強&実装してく予定です。

ダブルアレイの実装について少し。最初のDoubleArrayクラスでは、教科書通りの実装(こことか参照)に加えて、少し効率化を図ってます。一つは構築速度の効率化として行なっている、空き要素位置の保持です。これは最初の空き要素位置を保持する変数を1個儲け、2番目以降の空き要素位置はcheck配列内に保持してます。ただし真面目にやると大変(時間がかかる)なので、実際見に行って空き要素ではなければ、そこから1つずつ空き要素を探すようにしています。もう一つは孫ノードの多い子ノードを先に登録することで充填率が上がり、結果配列のサイズが小さくなります。これはまぁデータ依存なところはありますが。

TailDoubleArrayクラスは、DoubleArrayにTAIL配列(ここのMinimal Prefix Double-Arrayあたり参照)を導入したものです。一つしか子持たないノードが続く区間は、ラベルを文字配列内にコピーすることで、メモリ利用効率を上げます。

TailCompcationDoubleArrayクラスは、TAIL配列を可能な限り共有することで、さらに効率を上げます。"world"がTAILに格納されている状態で"javaworld"を格納する場合に"world\0java\1(0)"というように、既に接尾辞の一部が格納されている場合はそれを再利用するという工夫も行なってます。これは、多層トライで使ったテクニックを応用して、TAILを逆順に格納したトライをつくることで実現しています。このあたりはまた別途詳しく書く予定。

OptimizedTailCompactionDoubleArrayクラスは、構築終了時にbase配列やcheck配列の末尾にある使用していない領域を縮小したり、TAIL配列(中身はStringBuilder)をtrimしたりしてます。また、check配列をintではなくcharにしています。文字の種類が32,767を超えると格納できなくなりますし、次の空き要素までの距離が32,768を超えても格納できなくなります。現実的にはどちらもまず起こらない(Wikipedia日本語タイトルでも、文字種は7,564)ので、実用上問題ないんじゃないかと思います(でも念のため別クラスとして実装)。

実装は今までどおり、GitHubで公開してます。