java - 長い値の巨大なリストを格納するために使用するデータ構造

Question

Java プログラムでロング インデックスのリストをキャッシュしていますが、メモリがオーバーフローしています。そこで、すべての連続インデックスの開始インデックスと終了インデックスのみをキャッシュし、ArrayList の必要な API を書き直すことにしました。では、開始/終了インデックス キャッシュを実装するには、どのデータ構造が最適でしょうか? TreeMap を使用し、開始インデックスをキーとして、終了インデックスを値として保持する方がよいでしょうか?

Answer 1

最もコンパクトな表現は、特定のアプリケーションでのインデックスの分布に大きく依存します。

インデックスが密にクラスター化されている場合、mvp によって提案された範囲ベースの表現はおそらくうまく機能します (同様の問題であるため、ラスター グラフィックスのランレングス エンコーディングの実装を見ることができます)。

インデックスが密集した実行でクラスター化されていない場合、そのエンコーディングは実際にメモリ消費を増加させます。まばらに入力されたリストの場合、 FastUtil の LongArrayList や LongOpenHashSet などのプリミティブ データ構造、またはGnu TroveやColtの同様の構造を調べることができます。ほとんどの VM では、ArrayList 内の各 Long オブジェクトは 20 バイト以上を消費しますが、プリミティブ long は 8 バイトしか消費しません。したがって、標準の Collections フレームワークではなく、タイプ固有のプリミティブ コレクションを使用すると、多くの場合、大幅なメモリ節約を実現できます。

私は FastUtil に非常に満足していますが、別の解決策の方が適しているかもしれません。少しのシミュレーションとメモリ プロファイリングは、独自のデータの最も効果的な表現を決定するのに役立ちます。

Answer 2

私があなたなら、ビット文字列ストレージのいくつかのバリエーションを使用します。

Java では、ビット文字列はBitSetによって実装されます。

たとえば、一意の 32 ビット整数の任意のリストを表すには、それを 40 億ビット長の単一のビット文字列として格納できるため、4 bln / 8 ビット = 512 MB のメモリが必要になります。これはたくさんありますが、最悪の場合です。

しかし、あなたはそれよりもずっと賢くなることができます。たとえば、65536 ビット以下 (または 8KB 以下) など、より小さな固定 (または動的) サイズのビット文字列のリストまたはバイナリ ツリーとして格納できます。つまり、このツリーの各リーフ オブジェクトには、開始オフセットと長さを表す小さなヘッダー (簡単にするために 2 の累乗ですが、必ずしもそうである必要はありません) と、実際の配列メンバーを格納するビット文字列があります。効率を高めるために、必要に応じて、gzip または同様のアルゴリズムを使用してこのビット文字列を圧縮できます。これにより、アクセスが遅くなりますが、メモリ効率が 10 倍以上向上する可能性があります。

If your 20 million index elements are almost consecutive (not very sparse), it should take only around 20mln/8bits ~= 2 million bits = 2 MB to represent it in memory. If you gzip it, it will be probably under 1MB overall.

Answer 3

ほとんどの BitSet (圧縮または非圧縮) 実装は整数用です。ここに long 用の 1 つがあります: http://www.censhare.com/en/aktuelles/censhare-labs/yet-another-compressed-bitsetは、順序付けられたプリミティブ long ハッシュ セットまたは long から long へのハッシュ マップのように機能します。