0

成長する配列のように機能するデータ構造があります。これらの整数がこのデータ構造に重複していない場合にのみ、不明な量の整数が 1 つずつ挿入されます。

最初は a で十分だと思っていましたstd::setが、新しい整数が入ってくると自動的に大きくなり、重複がないことを確認します。

しかし、セットが大きくなるにつれて、挿入速度が低下します。ハッシュ以外にこの仕事をするための他のアイデアはありますか?

Ps

すべての要素を xor したり、(rmq のように) スパース テーブルを作成するなどのトリックが適用されるのだろうか?

4

6 に答える 6

3

問題にメモリを費やすつもりなら、2^32 ビットは 512MB であり、その時点でビット フィールドを使用できます。可能な整数ごとに 1 ビットです。CPU キャッシュの影響は別として、これにより O(1) の挿入時間とルックアップ時間が得られます。

ユースケースについて詳しく知らなければ、これが価値のあるメモリの使用なのか、それとも莫大なメモリ消費でほとんど利益が得られないのかを判断するのは困難です。

于 2012-09-15T08:41:57.773 に答える
2

このサイトには、可能なすべてのコンテナーが含まれており、各アクションの実行時間をレイアウトしているため、おそらくこれが役立ちます。

http://en.cppreference.com/w/cpp/container

提案されている unordered_set が最善の方法のようです。

于 2012-09-15T08:41:49.723 に答える
1

を試すことができますstd::unordered_set。これはハッシュテーブルとして実装する必要があります（「ハッシュ以外」と書く理由はわかりません。std::set通常、バランスの取れたツリーとして実装されるため、挿入パフォーマンスが不十分になります）。

于 2012-09-15T08:35:58.763 に答える
1

数値が収まる範囲がある場合は、std::setバケットとしていくつかを作成できます。

EDIT-指定した範囲によると、十分に高速std::setである必要があります。O(log n) は、いくつかの測定を行って、自分のケースでは遅いことがわかっていない限り、ほとんどの目的で十分に高速です。

また、Pigeonhole Principleを使用setsして、可能な重複を拒否することもできます (セットが大きくなる場合に適用されます)。

于 2012-09-15T08:29:43.293 に答える
0

重複を検出するには、ビット ベクトルが役立ちます。

于 2012-09-15T14:23:48.537 に答える
0

最適な決定を行うには、さらに多くの要件が必要になります。この提案は、次の制約に基づいています: Alcott 32 ビット整数、約 10.000.000 要素 (つまり、2^32 のうち任意の 10m)

これは、すべてのノードが連続領域の開始と終了の 2 つの値を格納する BST (二分探索木) です。最初の要素にはリージョンの開始番号が格納され、2 番目の要素には最後の番号が格納されます。この配置では、非常に小さな木の高さで 10M の制限に達することを期待して、大きな領域が許可されるため、検索が安価になります。10m 要素のデータ構造は、ノードごとに 8 バイト、さらにリンク (2x4 バイト) をノードごとに最大 2 つの子を使用します。したがって、すべての 10M 要素に対して 80M を作成します。そしてもちろん、通常より多くの要素が挿入されている場合は、挿入されていない要素を追跡できます。スペースに細心の注意を払う必要があり、シミュレーションや統計チェックを実行した後、小さな領域 (長さが 32 ビット未満) がたくさんあることがわかった場合は、ノード タイプを次の 1 つの数値に変更することをお勧めします。地域、

ビットマップへのアクセスを調整する必要がなく、たとえば、要素が 8 つしかない連続したチャンクしかない場合、メモの要件は、ノードに 4+1 バイト、子に 4+4 バイトであるためです。お役に立てれば。

于 2012-09-16T22:31:23.263 に答える