プリミティブint(s) の大きなリスト (約 800,000 int)を格納するためのスペース効率の良いコレクションが必要です。これcontains()により、定義された順序での高速操作と反復が可能になります。
contains()int がリストにあるかどうかを確認するためのより高速な操作は、非常に頻繁に行われるため、最優先事項です。
私は、Trove、Guava などの広く使用されている人気のあるサードパーティ ライブラリを使用することにオープンです。
Trove のTIntSetを見てきましたが、とにかく反復の順序を定義できないと思います。
コレクションのサイズは約 800,000 int になります。コレクションの値の範囲は 0 ～Integer.Max_VALUEです。反復の順序は、実際にはコレクションに値を追加する順序に基づいている必要があります。または、順序付けされた int[] を提供するだけで、同じ順序で反復する必要があります。
データ構造として、long の配列を選択します(論理的には2 つの intとして扱います)。high-int 部分 (ビット 63 から 32) は、コレクションに追加するint 値を表します。下位整数部分 (ビット 31 ～ 0) は、反復時の後続のインデックスを表します。800.000 の一意の整数の場合、サイズ 800.000 の長い配列を作成する必要があります。
ここで、配列を、値によって順序付けられたバイナリ バランス ツリーとして編成します。左が小さい値、右が大きい値です。さらに 2 つの追跡値が必要です。反復を開始する最初のインデックスを指す int と、最後に挿入された値のインデックスを指す int です。
新しい値を追加するたびに、バランスの取れた二分木を再編成し、最後に追加された値から現在追加されている値 (インデックスとして) を指すポインターを更新します。
この値 (配列と両方の int 値) を選択したコレクションとしてラップします。
このデータ構造を使用すると、 O(log(n))の検索パフォーマンスと、値のサイズの 2 倍のメモリ使用量が得られます。
これはデータベースの臭いですが、より直接的なアプローチが必要なため、java.nio のメモリ マップファイルを使用します。特に、800_000 int の自己定義された順序は、他の方法では機能しません。ただし、ファイル内の順序と並行して、メモリ内の BitSet を使用して内容を実現できます。
高速操作のためSetsに、ハッシュ (例: ) に基づいて設定された2 つのセットを使用できます。もう1つは、特定の順序で反復するようなツリー構造に基づいて設定されます。
int を追加する必要がある場合は、両方のセットを同時に更新します。TIntSetcontainsTreeSet
LinkedHashSetあなたが探しているもののように思えます。内部的には、aHashSetと aの 2 つの構造を維持LinkedListし、高速な 'contains()' (前者から) と定義された反復順序 (後者から) の両方を可能にします。
を使用するだけArrayList<Integer>です。