0

AとBをセットしました

セットAには1億個の数字があります（各数字は64ビットです）

セットBには1億個の数字があります（各数字は64ビットです）

2セットは同じサイズです。

データはすべてランダムで、ソートされていません。

2 つのセット間で重複する番号を見つけるためにどのアルゴリズムをお勧めしますか?

(約4Gのメモリと100~200Gbのディスク容量を利用できます)

前もって感謝します。

4

4 に答える 4

2

おそらく、実行時間の点で最も安価な方法は (ただし、残念ながらプログラミング時間ではありません)、A の要素をオープン アドレスのハッシュ テーブルに格納し、ハッシュ テーブルで B の各要素を検索することです。妥当なハッシュ関数を考え出すことができれば (詳細は後述)、約 60% の負荷率で単純な線形ハッシュを使用できます。これは、テーブルが 10 8 * (1/.6) * 8 バイトを占有することを意味します。約1.3GB。(標準ライブラリでオープン アドレスのハッシュ テーブルを提供する言語は知りません。C++ の unordered_sets はバケット チェーンを使用して実装されます。個々の要素が個別のストレージ割り当てでない場合、オーバーヘッドがわずかに増えるだけです。良いアロケータこれは実現可能かもしれません。）

幸いなことに、特に要素の削除に対処する必要がない場合は、オープン アドレスの線形プローブ ハッシュ テーブルを作成するのは非常に簡単です。問題は 2 つだけです。

  1. 「占有されていない」ことを意味する値を予約する必要があります。

  2. 優れたハッシュ関数が必要です。または少なくとも合理的なもの。

データが 64 ビット空間で本当にランダムに分散されている場合、ハッシュは単純です。データを目的のサイズに縮小するだけです。これを行う簡単な方法は、モジュロ演算子を使用することです。これは、テーブル サイズを素数にするように手配すれば、データが完全にランダムに分散されていなくてもうまく機能するはずです (166666783 は、60% の負荷に対して適切なサイズです)。 1 億要素の係数)。

「占有されていない」ことを意味する値を見つけることは、よりトリッキーになる可能性があります。1 つの値が不可能であることを既に知っている可能性があります (おそらく value 0)。そうでない場合は、ランダムな 64 ビット番号を選択できます。データセットに存在しない可能性はかなり高いですが、存在する場合は簡単なバックアップがあります。ハッシュテーブルに入れず、すべての値をBそれに対してチェックしてください。

前述の「値なし」ハックを含む、上記の説明に基づく疑似 C++ コード:

class HundredMillionSet {
  std::vector<uint64_t> h_;
  const size_t size_
  const uint64_t no_value_;
  bool has_no_value_;
  HundredMillionSet(size_t size, uint64_t no_value)
      : h_(size, no_value), size_(size), no_value_(no_value), has_no_value_(false) {}

  void insert(uint64_t v) {
    if (v == no_value_) { has_no_value_ = true; }
    else {
      size_t i = v % size_;
      while (h_[i] != no_value_) {
        if (++i == size_) i = 0;
      }
      h_[i] = v;
    }
  }

  bool check(uint64_t v) {
    if (v == no_value_) return has_no_value_;
    size_t i = v % size_;
    while (h_[i] != v && h_[i] != no_value_) {
      if (++i == size_) i = 0;
    }
    return h_[i] == v;
  }
};
于 2013-04-15T00:09:59.907 に答える
0

64 ビット = 8 バイト。2*8*100,000,000byte = 1.6GB => 数値を RAM に保持できます (ノード構造にはおそらく 2 倍の量が必要になります...)。私はバランスの取れた二分木に行きます（AVL、AB ...ツリーのwikiを検索するだけです）。あるセットから 1 つのツリーに、別のセットから別のツリーに数値を追加して、交差を行うだけです。

2 つの配列を並べ替えて交差させたいだけかもしれません。それが最も簡単な解決策になるはずです。

メモリ内のすべての数値を処理できない場合は、データベース (MySQL、PostgreSQL など) を使用してください。2 つの並べ替えられたテーブルと交差点。非常に高速で、最も重要なのは実装が簡単であることです。

于 2013-04-14T19:26:03.760 に答える