java - java: 非常に大きな木?

Question

目的は、非常に大きな木を構築することです。非常に大きいとは、数ギガバイトに収まる数億のノードを意味します。

問題は、一般的なデータ構造のオーバーヘッドが大きすぎることです。「ノード」オブジェクトと子「マップ」を持つ余裕はありません。非常にコンパクトな方法でメモリに直接エンコードする必要があります。

したがって、内部でオブジェクトを使用せずに、キーと値として整数を持つツリーのメモリ効率の良い実装が存在するかどうか疑問に思っていました。ハッシュ スペース = エントリあたり平均 15 バイト) これにより、外部マッピング int<->keys および int<->values を使用してツリーを検索できます。

誰？

PS: 内部でオブジェクトを使用すると、少なくとも 5 倍のスペースが使用されます: 8 つの参照 + 4 つの余分なハッシュ スペース + 16 のオブジェクト ヘッダー + 8 つのキー ref + 8 つの値の参照 + 8 つの親の参照 + 8 つの子の参照 + (16 + x) for children map obj = エントリあたりほぼ 76+x バイト。(たとえば、デフォルトの実装では、エントリごとに約 100 バイトが必要でした)

Answer 1

これは実際には Java 固有の質問ではなく、より一般的な概念です。

これを試してください: http://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html

重要なのは、オブジェクトのオーバーヘッドを回避するために、プリミティブの配列を使用することです。

Answer 2

正確にそれを行う特定のツリー実装を知りませんが、VTD-XML は、バッファーへのポインターを持つトークンの配列を内部的に使用して、XML ツリー (DOM) を表します。おそらく、彼らのソリューションからインスピレーションを得ることができますか?

Answer 3

すでに実装されているものは見つからないと思いますが、説明したことはIntBufferを使用して非常に簡単に実装できます。インデックスをバッファ内のレコードに変換する「ラッパー」クラスを作成し、必要に応じてそれらのラッパーをインスタンス化/破棄します(つまり、ツリーをトラバースしているとき、親への参照を保持することはおそらく気にしません)。 ）。

いくつかの懸念があります。

• ラッパー インスタンスのガベージ コレクション: 存続期間が短い限り、Eden から出ることはないため、GC はほとんど無料です。
• バッファ内のレコードのガベージ コレクション: ライト ワンス ツリーがある場合、これは問題ありません。それ以外の場合は、空きリストを維持する必要があります。難しいことではありませんが、少し時間がかかります。
• ツリーを実装する一般的なメカニズム: これは、 のようなクラスで既に行われていますTreeMap。しかし、アルゴリズムは非常に単純で、Wikipediaから入手できます。

Answer 4

このライブラリは、目的を達成するのに役立つことに気付くかもしれません。これは、値をプリミティブとして格納するために特別に設計されており、オブジェクトを格納しているように見せるために、舞台裏でバイトコード ハッカーを実行します。そんな時に使う...

... 大規模なデータ コレクションをメモリに効率的に格納したい。このライブラリは、フル GC の時間を大幅に短縮し、メモリ消費も削減できます。

特定の Tree コレクションはありませんが、必要なものによってはうまくいくかもしれません。

http://code.google.com/p/vanilla-java/wiki/HugeCollections

Answer 5

子のリストを保持する代わりに、すべてのノードがその親への参照を持つことができます。したがって、ノードのシリアル化には 3 つ以上の整数値 (親、キー、値) は必要ありません。

このアプローチの問題は、ツリー トラバーサルです。すべてのノードの子の明確なリストを取得するには、すべてのノードを反復処理する必要があります。トリプレットが親の値でソートされている場合、トラバーサルが改善される可能性があります。もう 1 つの整数値、つまり次のキーへのポインターを追加すると、ノードをリンク リストに保持できるため、ノードの挿入と削除の作業が容易になります。