0

の一連の 40 億個の 32 ビット整数から欠落している数を見つける問題について読んでいましたProgramming Pearlsが、解決策を完全に得ることができませんでした。

ランダムな順序で最大 40 億個の 32 ビット整数を含むシーケンシャル ファイルが与えられた場合、ファイルにない 32 ビット整数を見つけます。
制約: 数百バイトのメイン メモリが必要ですが、ディスク上の外部スクラッチ ファイルを十分に使用できます。

説明されている解決策は、上位ビットを使用して範囲内の数値を分離するプロセスです (つまり、最初のパスでは、先行0ビットを持つものを 1 つのファイルに書き込み、先行ビットを持つものを別のファイルに書き込みます1。2 番目のビットなどを使用して続行します。 ）、範囲内の数字の半分未満を含む半分を新しい検索範囲として使用して半分に分割します。

私はグーグルで検索して、 SOで同様の投稿を見つけましたが、これは正確な数がどのように見つかるかという私の質問に完全には答えていません(バイナリ検索がどのように範囲に収まるかわかりません)。
@Damien_The_Unbeliever の回答が最も関連性が高いようですが、私の観点からは、プロセスに従うと 2 つのファイルになると思いました。範囲内に 2 つの数値を持つファイルと 1 つの数値を持つファイルです。
1 つのファイル内の (1 つの) 数値を他の最大の数値で減算することにより、不足している数値を取得できます (ビットマスクは必要ありません。また、範囲がどの時点でも不明であるため、実際にビットマスクを適用できるかどうかはよくわかりません)。

私はこれで間違っていますか？誰かがこれを理解するのを助けることができますか?

4

3 に答える 3

3

データ自体をコピーしたり、ディスクに何かを書き込んだりする必要はありません。データの一部のパーティションのメンバーを数えて、開口部を特定します。トレードオフは、パス数とメモリの間です (メモリが増えると、より多くのカウントが可能になり、パーティションが小さくなります)。

これが8回のパスでの解決策です。一度に 4 ビットを使用してデータを分割します。2^4 = 16 個の可能な値なので、16 個のパーティションのそれぞれのカウントを格納するには 64 バイトが必要です。したがって、各 4 ビット ニブル値には関連するカウントがあります。

データを通過させ、数値の最初の 4 ビットのニブルに一致する関連するカウントをインクリメントします。パーティションがいっぱいの場合、そのカウントは 2^28 になります。満杯でないニブルの 1 つを選択してください --- これが結果の最初のニブルになります。

カウントをゼロにして、最初のニブルと一致しない数字を無視し、数字の 2 番目のニブルに関連付けられたカウントをインクリメントして、別のパスを作成します。1 秒のニブルの値は 2^24 になります。いっぱいでないものを選んでください。

8 つのニブルがすべて揃って、O(N) に答えが得られるまで、この方法で続行します。

一度に 1 ビットのみをチェックする場合、これは32 回のパスを必要とするバイナリ検索になります。（編集：スキップしている値をまだ読み取る必要があるため、実際にはバイナリ検索ではありません。それがO（Nである理由です。以下の編集を参照してください。）カウント用のKBのメモリがある場合は、それを行うことができます4パスで; 256 KB の場合、2 --- 実際には 128 KB で実行できます。これは、カウントに short int を使用できるためです。ここでは、数百バイトに制限されています --- 6 ビット/6 パス/256 バイトでしょうか?

編集: Li-aung Yip のソリューションはより適切にスケーリングされ、パスで複数のビットで分割するように変更できることは明らかです。書き込みが読み取りよりも遅い場合、おそらく最良の解決策は、この読み取り専用の回答と Li-aung Yip のディスクベースの回答とのハイブリッドでしょう。

上記のようにニブルをカウントするパスを実行し、次にニブルの 2 番目のセットをカウントする際に、最初のニブルに一致する数値のみ (または最後の 28 ビットのみ) を、2 番目のニブルに従って 16 個のファイルに書き込みます。

2 番目のニブルを選択し、それを読み取って 3 番目のニブルのカウントを取得し、2 番目のニブルに一致する数値のみを書き込みます。ファイルが容量に近い場合、数値がかなり均一に分布している場合、または最も少ないものを選択した場合毎回ニブルすると、ファイル サイズの約 6.66% (1/16+1/16^2...) しか書き込む必要がありません。

于 2012-04-14T23:07:57.030 に答える
2

数値をバイナリ分割して小さなファイルに繰り返し分割すると、最終的には次のようになります。

  • 最後の有効ビットのみが異なる 2 つの数値を含む一連のファイル
  • 1 つの番号のみを含む 1 つのファイル。

ファイル内にある数字の最後のビットを反転して、欠落している数字を取得します。

0x00 から 0x07 までの数字の例を見てみましょう。0x04 はありません。

000
001

010
011

... (missing)
101

110
111

を取り101、最下位ビットを反転して100、欠落しているを取得し0x04ます。

于 2012-04-14T10:07:25.647 に答える
1

32 ビット整数を使用して 40 億の整数を表現できます。数値をそれ自体で XOR することは、アセンブリ コードでレジスタをゼロにする標準的な方法です。欠落している数値が 1 つだけであることが保証されている場合は、整数のビットごとの XOR、つまり O(N) ソリューションが役に立ち、追加の 32 ビット整数のスペースが 1 つだけ必要になります。簡単な例として、3 ビットの数値を考えてみましょう。したがって、数値 0 ～ 7 が表現可能であり、そのうちの 1 つが欠落しています。6 (110) が欠落していると仮定します。欠落 = n1 XOR n2 XOR n3 XOR .. XOR n7. = 000 XOR 001 XOR 010 XOR 011 XOR 100 XOR 101 XOR 111

問題が 1 から 100 の間の不足している数字を見つけることだった場合、除外する必要がある要素を除外することから始める必要があります。AND を使用して、数値のビットをマスクすることにより、32 ビット整数範囲からより小さい範囲にドロップできます。

于 2012-05-31T00:02:13.030 に答える