2012/04/19

パトリシアトライのサイズ比較

 記事が前後しますが。気になったのでちょっと調べてみました。トライの内部形式をchar[]からbyte[]にすることでどれくらいインパクトがあるのか。byte[]にする際、UTF-8、Shift-JIS、EUC、JIS(ISO2022JP)でどのような違いがあるのか。

以下の表にまとめます。

トライのノード文字配列数
エンコーディング(内部形式)サイズサイズ全体サイズ
ISO-2022-JP(byte[])1,763,96758,210,9111,764,14241,189,910123,904,937
UTF-8(byte[])1,736,91057,318,0301,737,08340,404,315123,095,316
Shift_JIS(byte[])1,639,06454,089,1121,639,22935,103,790112,335,651
EUC_JP(byte[])1,633,86553,917,5451,634,03135,089,059112,013,060
UTF-16(char[])1,513,46948,431,0081,515,34635,043,030103,472,496
UTF-16(char[])+フィールド最適化(*1)1,513,469(*3)39,664,136(*4)1,515,33834,688,31291,774,563
UTF-16(char[])+フィールド最適化(*1)+多層トライ(*2)1,995,303(*3)55,082,824(*4)483,714(*5)10,345,546(*5)82,870,660

*1 - 子ノードを持たない/1つだけ/2つ以上、終端である/ないの組み合わせでそれぞれ最適なフィールドを持つノードクラスを使用する。
*2 - ラベルを逆順に持つ圧縮用トライを用意(参考: 多層トライの実験結果 - やた@はてな日記)。本来のトライのノードもその圧縮用トライのノードをフィールドに持つものを使用。
*3 - 全ノードの合計数。
*4 - 全ノードの合計サイズ。
*5 - 文字配列は圧縮用トライ内のもの。本来のトライには文字配列を持たない。

いずれもWikipedia日本語タイトル127.3万件を格納した結果です。フィールド最適化+多層トライのデータでは、圧縮用トライのノードや文字配列のサイズも加算されています。

こうして見てみると、多層トライがいかに圧縮率が高いかと、オブジェクト数の増減がいかにインパクトがあるかがわかります。せっかく多層トライで圧縮したメモリサイズ(24MB)も、ノードオブジェクト数の増加でその効果は半減しています。

結論: Javaではオブジェクト数大事

多層トライの実装はGitHubで公開してます。org.trie4j.trie.patricia.multilayer.MultilayerPatriciaTrieがフィールド最適化と多層トライの実装で、全タイトル挿入後のデータ、挿入してからpack(), morePack()を呼び出した後のデータが表の下2つです。packで多層トライでの圧縮、morePackで多層トライのノードのフィールド最適化を行います(morePack遅いです)。

下記にVisualVMでの主要なオブジェクトのスナップショットを。まずはUTF-16のフィールド最適化のみ。

次にフィールド最適化+多層トライ(もフィールド最適化)。

サイズをオブジェクト数で割るとわかるけど、1オブジェクトで24とか32バイト消費してます。フィールド最適化を行わない場合、40バイト消費することもあります(64bit環境で。32bitなら半分になります。)

結論: Javaではオブジェクト数大事(2回目)

しかしこの画像の小ささ何とかならんかな。

コメントを投稿