1

正の整数 (数百万の要素) のソートされたリストに最適なデータ構造を見つけようとしています。要件は次のとおりです (重要度順):

  1. 小さなメモリフットプリント

  2. 高速O(log n)検索

  3. より速く挿入/削除memcpy()

検索用と挿入用の 2 つの配列を保持することを考えています。いくつかの操作ごとに、メインの操作を再編成し、2 つ目の操作をクリーニングします。何かご意見は？私は正しい軌道に乗っていますか？

ps。重複はありません。スレッドセーフである必要はありません。読み取りは頻繁に行われますが、書き込みはほとんど行われません。整数は構造内で不均一に分布しています。つまり、いくつかの構造には数個の要素しか含まれていませんが、他の構造には数百万の要素があり、0 から までの位置を取ります0xFFFFFFFF。

4

7 に答える 7

2

Van Emde Boas Treeを使いたいと思います

次の特徴があります。 

Space   O(M)
Search  O(log log M)
Insert  O(log log M)
Delete  O(log log M)
于 2012-07-02T18:27:39.750 に答える
1

@Peter Lawrey は良いスタートを切ったと思います: サブディバイド。部分的に異なるのは、256 の項目に細分化し、それぞれが 2^23 の項目を追跡することです。整数の分布に応じて、上位または下位の 8 ビットを使用して分割します。

下位のものについては、int がまばらな場合は Set (または同様のもの) から始めます。ただし、その Set が特定のサイズに達すると (密度が高くなり始めます)、BitSet に切り替えます。値の削除をサポートする必要があるかどうかはわかりません。その場合、BitSet から Set に戻す必要があります。

ps他のすべてが失敗した場合、すべての正の整数の単純なビットセットは「わずか」268MBです（私の計算が正しければ...）

于 2012-07-02T18:50:37.403 に答える
0

リンクリストはどうですか？momoryの制約は、intのサイズ+前のポインターと次のポインターの少しのオーバーヘッドになります。挿入と削除に関しては、時間の要件は、リストを下に移動して、挿入しているものよりも小さいものが見つかり、そのレコードの直前に配置することだけです。削除するには、変更の前と次のポインタのみが必要であり、検索は挿入と同じくらい簡単です。

于 2012-07-02T18:30:42.090 に答える
0

現代世代の試行のいくつかを見ることができます(そのリンクにはFusion treesについては言及されていません)。ただし、それらはすべて実装がかなり複雑だと思います。運が良ければ、大胆な人があなたが使用できる実装を作成してオープンソース化していることに気付くかもしれません。

注目すべきもう 1 つの点は、従来のB-treeです。

データ セットのサイズが比較的一貫している場合は、1 レベルの B ツリーを作成することもできます (つまり、単一のルート ノードと複数の子ノードを使用)。これにより、実装がかなり簡素化されます ( int[][]、それが意味をなす場合、内部キーをリーフへのピークに置き換えます)。

于 2012-07-04T11:27:55.970 に答える
0

速度についてあまり心配しておらず、メモリ使用量が心配な場合は、int の配列をロードし、別の配列を作成し、数値 X (メモリの過負荷を防ぐために 1K 程度) になるまで配列を並べ替えてから、配列のその部分をテキスト ファイルとして保存し (objectOutputStream は int を int として保存します)、配列をクリアしてから、配列内の次の X 個の int に対して同じことを行います。出力ストリームをマークして、ファイルを追加する（true）か、上書きするかを確認してください。これがデフォルトです。

于 2012-07-02T18:49:22.453 に答える