ソートされた整数のリストがたくさんありますが、それらはすべてそれぞれ 3600 項目未満です。できるだけメモリに保持したいので、スペース効率の良いデータ構造を探しています。
最も一般的な操作は、挿入、メンバーシップ テスト、範囲クエリです。
整数はほとんどが 10 億から 100 億の範囲になりますが、理論的には、整数がはるかに小さくなるコーナーケースがいくつかある可能性があります。
私はスキップリストを見てきましたが、これは非常に優れていますが、もっと効率的な構造があるかもしれないと感じています。
これは、アクセス パターンと変更に関するルックアップの割合に大きく依存します。ルックアップが変更よりもはるかに一般的である場合 (あなたの場合は明らかに挿入)、これは非常に一般的ですが、実際には、最適なメモリ効率を提供する並べ替えられた配列を回避できます。
挿入が実際にはより一般的である場合、ソートされた配列はおそらく機能せず、より複雑なデータ構造に頼る必要があります。B ツリーは、多くのノードをまとめてパックするため、AVL、スキップ リスト、赤黒ツリーほどリンケージ オーバーヘッドの影響を受けないため、候補のように思えます。
基数ツリーを調査することも同様に興味深いと思います。特に、リストに連続した整数が多数ある場合は、そのような範囲が基数ツリーによって「圧縮」されるためです。
ブルーム フィルターを使用すると、メンバーシップ クエリをさらに最適化できることに注意してください。ある意味では、これらはメンバーシップ クエリの最もスペース効率の良いデータ構造ですが、確率論的であるため、他の決定論的なデータ構造と組み合わせてのみ使用できます。もちろん、間違った回答を返すことが許可されている場合を除きます :-)。