8

セクション 2.6 と問題 2 にあります。元の問題は次のようなものです。

「4,300,000,000 個の 32 ビット整数を含むシーケンシャル ファイルが与えられた場合、少なくとも 2 回出現するものをどのように見つけることができますか?」

この演習に対する私の質問は、上記の問題のトリックは何か、この問題はどのような一般的なアルゴリズム カテゴリに属しているのかということです。

4

4 に答える 4

10

長さ 2^32 ビット (ゼロに初期化) のビット配列を作成します。これは約 512MB で、最新のマシンの RAM に収まります。

int ごとにファイルの読み取りを開始し、int の値と同じインデックスでビットをチェックします。ビットが設定されている場合は重複が見つかりました。ビットがゼロの場合は 1 に設定し、ファイルから次の int に進みます。 .

その秘訣は、適切なデータ構造とアルゴリズムを見つけることです。この場合、すべてが適切なデータ構造で RAM に収まり、シンプルで効率的なアルゴリズムを使用できます。
数値が int64 の場合は、使用可能な追加ストレージの量に応じて、適切な並べ替え戦略を見つけるか、複数のパスを作成する必要があります。

于 2011-04-02T07:06:14.007 に答える
7

ピジョンホールの原理 -- M 個のピジョンホールに N 個のハトがいて、N>M の場合、1 つの穴に少なくとも 2 羽のハトがいます。32 ビット整数のセットは 2^32 のピジョンホールであり、ファイル内の 43 億個の数値がハトです。4.3x10^9 > 2^32 なので、重複があることがわかります。

この原則を適用して、探している重複が数値のサブセットにあるかどうかをテストできますが、ファイル全体を読み取るという犠牲を払って、RAM に一度に少しずつロードする必要はありません。回数を数えるだけです。テスト範囲内の数値を確認し、その範囲内の整数の総数と比較します。たとえば、1,000,000 から 2,000,000 までの重複をチェックするには、次のようにします。

int pigeons = 0;
int pigeonholes = 2000000 - 1000000 + 1; // include both fenceposts
for (each number N in file) {
  if ( N >= 1000000 && N <= 2000000 ) {
    pigeons++
  }
}
if (pigeons > pigeonholes) {
  // one of the duplicates is between 1,000,000 and 2,000,000
  // try again with a narrower range
}

チェックする範囲の大きさと16GBのデータを何回読みたいかはあなた次第です:)

一般的なアルゴリズムのカテゴリに関する限り、これは組み合わせ論 (カウントに関する数学) の問題です。

于 2011-04-03T11:41:57.557 に答える
-1

32ビットの正の整数とは、この問題を解決するために特別なアルゴリズムやトリックは必要ないと思います。簡単な観察だけで、意図した解決策が得られます。

私の観察では、このようになります。シーケンシャルファイルには32ビット整数（0から2 ^ 31-1）のみが含まれます。それらすべてをそのファイルに一意に配置すると仮定すると、2^31行になります。これらの正の整数をもう一度入力すると、2 ^ 31 * 2行になり、4,300,000,000よりも小さくなることがわかります。

したがって、答えは0から2^31-1の範囲の正の整数全体です。

于 2011-04-02T07:11:27.013 に答える
-1

整数を並べ替えてループし、連続する整数が重複しているかどうかを確認します。これをメモリ内で行う場合、現在のマシンで可能な 16 GB のメモリが必要です。これが不可能な場合は、mergesort を使用して数値を並べ替え、中間配列をディスクに保存することができます。

私の最初の実装の試みは、unixのコマンドsortとコマンドを使用することです。uniq

于 2011-04-02T15:30:51.237 に答える