algorithm - 与えられた 40 億に含まれない整数を生成する

Question

私はこのインタビューの質問を受けました：

40 億の整数を含む入力ファイルが与えられた場合、ファイルに含まれていない整数を生成するアルゴリズムを提供します。1 GB のメモリがあるとします。メモリが 10 MB しかない場合に何をするかをフォローアップします。

私の分析：

ファイルのサイズは 4×10 ⁹ ×4 バイト = 16 GB です。

外部ソートを実行できるため、整数の範囲を知ることができます。

私の質問は、ソートされた大きな整数セットで不足している整数を検出する最良の方法は何ですか?

私の理解（すべての回答を読んだ後）：

32 ビット整数について話していると仮定すると、2 ³² = 4*10 ^{9 個}の異なる整数があります。

ケース 1: 1 GB = 1 * 10 ⁹ * 8 ビット = 80 億ビットのメモリがあります。

解決：

1 つの異なる整数を表す 1 ビットを使用すれば、それで十分です。ソートは必要ありません。

実装：

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

ケース 2: 10 MB メモリ = 10 * 10 ⁶ * 8 ビット = 8000 万ビット

解決：

考えられるすべての 16 ビットプレフィックスには、2 ¹⁶個の整数 = 65536 があり、2 ¹⁶ * 4 * 8 = 200 万ビットが必要です。65536 個のバケットを構築する必要があります。最悪の場合、40 億個の整数すべてが同じバケットに属するため、バケットごとにすべての可能性を保持する 4 バイトが必要です。

ファイルの最初のパスで各バケットのカウンターを構築します。

バケットをスキャンして、ヒット数が 65536 未満の最初のバケットを見つけます。

ファイルの 2 番目のパスを通じてステップ 2 で見つかった上位 16 ビットプレフィックスを持つ新しいバケットを構築します。

ステップ 3 で構築されたバケットをスキャンし、ヒットがない最初のバケットを見つけます。

コードは上記のものと非常によく似ています。

結論: ファイルパスを増やすことでメモリを減らします。

^{遅れて到着した人への説明: この質問は、ファイルに含まれていない整数が 1 つだけあるとは言っていません。少なくとも、ほとんどの人はそのように解釈していません。ただし、コメントスレッドの多くのコメントは、タスクのバリエーションに関するものです。残念ながら、それをコメントスレッドに導入したコメントは後で作成者によって削除されたため、孤立した返信がすべてを誤解しているように見えます。とても紛らわしいです、すみません。}

score 539 · Accepted Answer

「整数」が 32 ビットを意味すると仮定すると、指定された 16 ビットプレフィックスを持つ入力ファイルに含まれる数字の数を数えるには、10 MB のスペースで十分です。入力ファイル。^{バケットの少なくとも 1 つは、2 16}回未満のヒットになります。2 番目のパスを実行して、そのバケット内の可能な番号のうち、既に使用されているものを見つけます。

それが 32 ビットを超えることを意味するが、まだサイズが制限されている場合: (符号付きまたは符号なし; 選択した) 32 ビット範囲外にあるすべての入力数値を無視して、上記のように実行します。

「整数」が数学的な整数を意味する場合: 入力を一度読み、これまでに見た中で最も長い数の~~最大の~~長さを追跡します。完了したら~~、最大値に 1 を足し~~た乱数を 1 桁増やして出力します。(ファイル内の数値の 1 つは、正確に表すのに 10 MB 以上かかる bignum である可能性がありますが、入力がファイルの場合は、少なくともそれに収まるものの長さを表すことができます)。

score 204 · Accepted Answer

統計に基づいたアルゴリズムは、決定論的アプローチよりも少ないパスを使用してこの問題を解決します。

非常に大きな整数が許可されている場合、O(1) 時間で一意である可能性が高い数値を生成できます。GUIDのような疑似乱数の 128 ビット整数は、セット内の既存の 40 億の整数の 1 つと衝突するのは、640 億のケースのうち 1 つ未満です。

整数が 32 ビットに制限されている場合、10 MB をはるかに下回る使用量で、1 回のパスで一意である可能性が高い数値を生成できます。疑似乱数の 32 ビット整数が既存の 40 億の整数の 1 つと衝突する確率は、約 93% (4e9 / 2^32) です。1000 個の疑似乱数整数がすべて衝突する確率は、12 兆分の 1 未満です (衝突確率 ^ 1000)。したがって、プログラムが 1000 個の疑似乱数候補を含むデータ構造を維持し、既知の整数を反復処理して候補から一致を除外する場合、ファイルにない整数が少なくとも 1 つ見つかることはほとんど確実です。

score 124 · Accepted Answer

問題は、ファイルにない可能な限り最小の数を見つける必要があることを指定していないため、入力ファイル自体よりも長い数を生成することができます。:)

score 60 · Accepted Answer

1 GBのRAMバリアントの場合、ビットベクトルを使用できます。40億ビット==500MBバイト配列を割り当てる必要があります。入力から読み取った数値ごとに、対応するビットを「1」に設定します。完了したら、ビットを繰り返し処理して、まだ「0」である最初のビットを見つけます。そのインデックスが答えです。

score 49 · Accepted Answer

^{それらが 32 ビット整数である場合 (おそらく 2 32}に近い ~40 億の数の選択から)、40 億の数のリストは、可能な整数 (4 * 10 ⁹ / (2 ³² ))の最大 93% を占めることになります。）。したがって、各ビットがゼロに初期化された2 ^{32ビットのビット配列を作成する場合 (2}²⁹バイト ~ 500 MB の RAM を使用します。バイト = 2 ³ビット = 8 ビットを覚えておいてください)、整数リストを読み、各 int に対して、対応するビット配列要素を 0 から 1 に設定します。次に、ビット配列を読み取って、まだ 0 である最初のビットを返します。

RAM が少ない (~10 MB) 場合は、このソリューションを少し変更する必要があります。10 MB ~ 83886080 ビットは、0 から 83886079 までのすべての数値のビット配列を作成するのに十分です。したがって、int のリストを読み取ることができます。ビット配列に 0 ～ 83886079 の # のみを記録します。数字がランダムに分布している場合。圧倒的な確率で (約10 ^-2592069で 100% 異なります)、欠落している int が見つかります)。実際、1 から 2048 までの数字 (256 バイトの RAM のみ) を選択した場合でも、圧倒的な割合 (99.9999999999999999999999999999999999999999999999999999999995%) の割合で欠落している数字が見つかります。

しかし、約 40 億の数字があるとしましょう。2 ³² - 1 の数字と 10 MB 未満の RAM がありました。したがって、整数の小さな範囲には、数値が含まれていない可能性がわずかにあります。

リスト内の各 int が一意であることが保証されている場合は、数値を合計し、# が 1 つ欠けている合計を減算して完全な合計 (½) (2 ³² ) (2 ³² - 1) = 9223372034707292160 を求めて、欠落している int を見つけることができます。 . ただし、int が 2 回発生した場合、このメソッドは失敗します。

ただし、分割して征服することはいつでもできます。単純な方法は、配列を読み込んで、前半 (0 から 2 ³¹ -1) と後半 (2 ³¹、2 ³² ) にある数字の数を数えることです。次に、数字の少ない範囲を選び、その範囲を半分に分割することを繰り返します。^{(たとえば (2 31} , 2 ³² ) に2 つ少ない数があった場合、次の検索では (2 ³¹ , 3*2 ³⁰ -1), (3*2 ³⁰ , 2 ³² )の範囲の数がカウントされます。数字がゼロの範囲が見つかるまで繰り返し、答えが得られます. O(lg N) ~ 32 配列を読み取る必要があります.

その方法は非効率的でした。各ステップで 2 つの整数のみを使用しています (または 4 バイト (32 ビット) の整数で約 8 バイトの RAM)。^{より良い方法は、sqrt(2 32} ) = 2 ¹⁶ = 65536 個のビンに分割することです。それぞれのビンには 65536 個の数値があります。各ビンはそのカウントを格納するために 4 バイトを必要とするため、2 ¹⁸バイト = 256 kB が必要です。したがって、ビン 0 は (0 ～ 65535=2 ¹⁶ -1)、ビン 1 は (2 ¹⁶ =65536 ～ 2*2 ¹⁶ -1=131071)、ビン 2 は (2*2 ¹⁶ =131072 ～ 3*2 ¹⁶ - 1=196607)。Python では次のようになります。

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

~40 億の整数リストを読みます。^{2 16 個}のビンのそれぞれに含まれる int の数を数え、65536 個すべての数値を持たない incomplete_bin を見つけます。次に、40 億の整数リストをもう一度読みます。ただし、今回は整数がその範囲内にある場合にのみ通知します。見つけたら少しひっくり返します。

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break

score 39 · Accepted Answer

なぜそんなに複雑にするのですか？ファイルに存在しない整数を要求しますか？

指定されたルールに従って、保存する必要があるのは、ファイル内でこれまでに遭遇した最大の整数だけです。ファイル全体が読み取られたら、それより1大きい数を返します。

ルールに従って、アルゴリズムによって返される整数または数値のサイズに制限がないため、maxintなどにヒットするリスクはありません。

score 34 · Accepted Answer

これは、バイナリ検索の変形を使用して、非常に小さなスペースで解決できます。

0からまでの数値の許容範囲から始めます4294967295。
中点を計算します。
ファイルをループし、中間値と等しい、小さい、または大きい数値の数をカウントします。
数字が同じでない場合は、完了です。中点数が答えです。
それ以外の場合は、数値が最も少ない範囲を選択し、この新しい範囲で手順 2 から繰り返します。

これには、ファイル全体で最大 32 回の線形スキャンが必要ですが、範囲とカウントを格納するために数バイトのメモリしか使用しません。

これは、16k の代わりに 2 つのビンを使用する点を除いて、Henning のソリューションと本質的に同じです。

score 27 · Accepted Answer

編集OK、ファイル内の整数が静的分布に従うと想定しているため、これはあまり考えられていませんでした。どうやら彼らはする必要はありませんが、それでもこれを試す必要があります:

約 43 億の 32 ビット整数があります。それらがファイル内でどのように分散されているかはわかりませんが、最悪のケースはシャノンエントロピーが最も高いもの、つまり均等な分散です。この場合、ファイル内で整数が 1 つも発生しない確率は次のようになります。

( (2³²-1)/2³² )⁴ ⁰⁰⁰ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

シャノンエントロピーが低いほど、この確率は平均で高くなりますが、この最悪のケースでも、ランダムな整数で 5 回推測した後、90% の確率で非発生数が見つかります。疑似乱数ジェネレーターでそのような数値を作成し、それらをリストに保存するだけです。次に、int を次々と読み取り、それをすべての推測と比較します。一致する場合は、このリストエントリを削除します。すべてのファイルを確認した後、複数の推測が残っている可能性があります。それらのいずれかを使用します。まれに (最悪の場合でも 10%)、推測が残っていない場合、ランダムな整数の新しいセットを取得します。今回はおそらくそれ以上です (10->99%)。

メモリ消費: 数十バイト、複雑さ: O(n)、オーバーヘッド: int を比較するのではなく、避けられないハードディスクアクセスにほとんどの時間が費やされるため、無視できます。

静的分布を仮定しない場合の実際の最悪のケースは、すべての整数が最大で発生することです。これは、1 - 4000000000/2³² ≈ 6% のすべての整数のみがファイルに出現しないためです。そのため、さらに推測が必要になりますが、それでもメモリを大量に消費することはありません。

score 24 · Accepted Answer

[0、2 ^ x --1]の範囲から1つの整数が欠落している場合は、それらをすべて一緒にxorします。例えば：

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

（これが質問に正確に答えないことは知っていますが、非常によく似た質問に対する良い答えです。）

score 20 · Accepted Answer

彼らは、値が大きなセットの一部ではないかどうかを非常に効率的に絶対的に判断できる確率的ブルームフィルターについて聞いたことがあるかどうかを確認しようとしている可能性があります(ただし、その値がセットのメンバーである可能性が高い場合にのみ判断できます)。

score 17 · Accepted Answer

元の質問の現在の表現に基づくと、最も簡単な解決策は次のとおりです。

ファイル内の最大値を見つけて、それに1を追加します。

score 14 · Accepted Answer

を使用しBitSetます。1バイトあたり8でビットセットにパックされた40億の整数（最大2 ^ 32の整数を想定）は、2 ^ 32/2 ^ 3 = 2 ^29=約0.5Gbです。

もう少し詳細を追加するには、数値を読み取るたびに、対応するビットをビットセットに設定します。次に、BitSetをパスして、存在しない最初の番号を見つけます。実際、乱数を繰り返し選択し、それが存在するかどうかをテストすることで、これを同じように効果的に行うことができます。

実際、BitSet.nextClearBit（0）は、最初の未設定ビットを通知します。

BitSet APIを見ると、0..MAX_INTのみをサポートしているように見えるため、2つのビットセット（1つは+'ve番号用、もう1つは-'ve番号用）が必要になる場合がありますが、メモリ要件は変わりません。

score 12 · Accepted Answer

サイズ制限がない場合、最も簡単な方法は、ファイルの長さを取得し、ファイルの長さ + 1 乱数の数字 (または単に "11111..." s) を生成することです。利点: ファイルを読み取る必要さえなく、メモリ使用量をほぼゼロに抑えることができます。欠点: 何十億もの数字を出力します。

ただし、唯一の要因がメモリ使用量を最小限に抑えることであり、他に何も重要でない場合は、これが最適なソリューションになります。「ルールの最悪の乱用」賞を受賞することさえあります。

score 11 · Accepted Answer

数値の範囲が常に 2^n (2 の偶数乗) であると仮定すると、(別のポスターで示されているように) 排他的論理和が機能します。理由については、次のように証明しましょう。

法則

1 つの要素が欠落している要素を持つ整数の 0 ベースの範囲が与えられた場合2^n、既知の値を xor 演算して欠落した数値を生成するだけで、欠落している要素を見つけることができます。

の証拠

n = 2 を見てみましょう。n = 2 の場合、0、1、2、3 の 4 つの一意の整数を表すことができます。これらのビットパターンは次のとおりです。

0 - 00
1 - 01
2 - 10
3 - 11

さて、見てみると、すべてのビットが正確に 2 回設定されています。したがって、偶数回設定されるため、数値の排他的論理和は 0 になります。単一の数値が欠落している場合、排他的論理和は、欠落している数値と排他的論理和を計算すると、次のような数値を生成します。 0. したがって、欠落数と結果の排他的論理和の数はまったく同じです。2 を削除すると、結果の xor は10(または 2) になります。

では、n+1 を見てみましょう。各ビットが設定された回数を、n各ビットが設定された回数をと呼びましょう。ビットが 0 に設定された要素とビットが 1 に設定された要素があるため、の値はに等しくなります。また、は常に偶数であるため、常に各ビットが偶数回設定されます。xn+1 yyy = x * 2xn+1xn+12xn+1

したがって、n=2機能し、n+1機能するため、 xor メソッドはのすべての値に対して機能しますn>=2。

0 ベースの範囲のアルゴリズム

これは非常に簡単です。2*n ビットのメモリを使用するため、32 以下の任意の範囲で、2 32 ビット整数が機能します (ファイル記述子によって消費されるメモリは無視されます)。そして、ファイルの単一パスを作成します。

long supplied = 0;
long result = 0;
while (supplied = read_int_from_file()) {
    result = result ^ supplied;
}
return result;

任意ベースの範囲のアルゴリズム

このアルゴリズムは、範囲の合計が 2^n に等しい限り、任意の開始番号から任意の終了番号までの範囲で機能します。ファイルを介して（最初に最小値を取得し、2 番目に不足している int を計算します）。

long supplied = 0;
long result = 0;
long offset = INT_MAX;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    result = result ^ (supplied - offset);
}
return result + offset;

任意の範囲

すべての範囲が少なくとも 1 回は 2^n の累乗を超えるため、この修正された方法を任意の範囲のセットに適用できます。これは、欠けているビットが 1 つある場合にのみ機能します。ソートされていないファイルの 2 つのパスが必要ですが、毎回欠落している番号が 1 つ見つかります。

long supplied = 0;
long result = 0;
long offset = INT_MAX;
long n = 0;
double temp;
while (supplied = read_int_from_file()) {
    if (supplied < offset) {
        offset = supplied;
    }
}
reset_file_pointer();
while (supplied = read_int_from_file()) {
    n++;
    result = result ^ (supplied - offset);
}
// We need to increment n one value so that we take care of the missing 
// int value
n++
while (n == 1 || 0 != (n & (n - 1))) {
    result = result ^ (n++);
}
return result + offset;

基本的に、範囲を 0 付近に再設定します。次に、排他的論理和を計算するときに、追加する並べ替えられていない値の数をカウントします。次に、ソートされていない値のカウントに 1 を追加して、欠落している値を処理します (欠落している値をカウントします)。次に、n の値を xor し続けます。n が 2 のべき乗になるまで、毎回 1 ずつ増やします。結果は元の基数に戻されます。終わり。

PHPでテストしたアルゴリズムは次のとおりです（ファイルの代わりに配列を使用しますが、同じ概念です）：

function find($array) {
    $offset = min($array);
    $n = 0;
    $result = 0;
    foreach ($array as $value) {
        $result = $result ^ ($value - $offset);
        $n++;
    }
    $n++; // This takes care of the missing value
    while ($n == 1 || 0 != ($n & ($n - 1))) {
        $result = $result ^ ($n++);
    }
    return $result + $offset;
}

任意の範囲の値 (負の値を含めてテスト) を配列に入力し、その範囲内に欠落している値を入力すると、毎回正しい値が見つかりました。

別のアプローチ

外部ソートを使用できるので、ギャップをチェックしてみませんか? このアルゴリズムを実行する前にファイルがソートされていると仮定すると、次のようになります。

long supplied = 0;
long last = read_int_from_file();
while (supplied = read_int_from_file()) {
    if (supplied != last + 1) {
        return last + 1;
    }
    last = supplied;
}
// The range is contiguous, so what do we do here?  Let's return last + 1:
return last + 1;

score 9 · Accepted Answer

不適切に引用されていない限り、トリックの質問。ファイルを一度読み込んで最大整数を取得しn、を返しn+1ます。

もちろんn+1、整数オーバーフローが発生した場合に備えて、バックアップ計画が必要です。

score 9 · Accepted Answer

入力ファイルのサイズを確認し、そのサイズのファイルで表現するには大きすぎる数値を出力します。これは安っぽいトリックのように思えるかもしれませんが、面接の問題に対する創造的な解決策であり、メモリの問題を巧みに回避し、技術的には O(n) です。

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

常に2 bitcountより大きい10 ^bitcount -1を出力する必要があり^ます。技術的には、打ち負かさなければならない数は2^{ビットカウント}- (4 * 10 ⁹ - 1)です。これは、ファイル内に (40 億 - 1) 個の他の整数が存在することがわかっているためです。完全に圧縮したとしても、少なくともそれぞれ1ビット。

score 8 · Accepted Answer

最も簡単な方法は、ファイル内の最小数を見つけて、それより1少ない数を返すことです。これは、O（1）ストレージと、n個のファイルのO（n）時間を使用します。ただし、数値範囲が制限されている場合は失敗し、min-1が数値にならない可能性があります。
ビットマップを使用する簡単で簡単な方法については、すでに説明しました。このメソッドは、O（n）時間とストレージを使用します。
2^16カウントバケットを使用する2パス方式も言及されています。2 * nの整数を読み取るため、O（n）時間とO（1）ストレージを使用しますが、2^16を超える数値のデータセットを処理することはできません。ただし、2パスではなく4パスを実行することで、（たとえば）2 ^ 60 64ビット整数に簡単に拡張できます。また、メモリに収まる数のビンのみを使用し、それに応じてパス数を増やすことで、小さなメモリの使用に簡単に適応できます。この場合、実行時間はO（n）ではなく、O（n * log n）になります。
ltn100が指摘したように、これまでrfrankelによって、そしてircmaxellによって詳細に言及された、すべての数値をXORする方法は、stackoverflow＃35185で尋ねられた質問に答えます。O（1）ストレージとO（n）ランタイムを使用します。今のところ32ビット整数を想定すると、XORは7％の確率で個別の数値を生成します。理論的根拠：与えられた〜4Gの異なる数が一緒にXORされ、約 300Mがファイルにない場合、各ビット位置のセットビット数は奇数または偶数になる可能性が等しくなります。したがって、2 ^ 32の数値は、XORの結果として発生する可能性が等しく、そのうち93％がすでにファイルに含まれています。ファイル内の数値がすべて区別されていない場合、XORメソッドの成功の確率が高くなることに注意してください。

score 7 · Accepted Answer

どういうわけか、この問題を読んですぐに対角化について考えました。私は任意に大きな整数を想定しています。

最初の数を読みます。40億ビットになるまでゼロビットで左パディングします。最初の (上位) ビットが 0 の場合、1 を出力します。それ以外の場合は 0 を出力します (実際には左パディングする必要はありません。数値に十分なビットがない場合は 1 を出力するだけです。) 2 番目のビットを使用する以外は、2 番目の数値で同じことを行います。この方法でファイルを続行します。一度に 1 ビットずつ 40 億ビットの数値を出力しますが、その数値はファイル内のどの数値とも同じではありません。証明: n 番目の数と同じだった場合、n 番目のビットについては一致しますが、構造上は一致しません。

score 6 · Accepted Answer

ビットフラグを使用して、整数が存在するかどうかをマークできます。

ファイル全体をトラバースした後、各ビットをスキャンして、番号が存在するかどうかを確認します。

各整数が32ビットであると仮定すると、ビットフラグ付けが行われる場合、それらは1GBのRAMに便利に収まります。

score 6 · Accepted Answer

完全を期すために、別の非常に単純なソリューションを次に示します。これは、実行に非常に長い時間がかかる可能性が高く、メモリをほとんど使用しません。

可能なすべての整数をからint_minまでの範囲int_maxとしbool isNotInFile(integer)、ファイルに特定の整数が含まれていない場合は true を返し、それ以外の場合は false を返す関数 (その特定の整数をファイル内の各整数と比較することによって)

for (integer i = int_min; i <= int_max; ++i)
{
    if (isNotInFile(i)) {
        return i;
    }
}

score 5 · Accepted Answer

10 MB のメモリ制約の場合:

数値をバイナリ表現に変換します。
左 = 0、右 = 1 の二分木を作成します。
バイナリ表現を使用してツリーに各数値を挿入します。
番号がすでに挿入されている場合、リーフはすでに作成されています。

終了したら、以前に作成されたことのないパスを使用して、要求された番号を作成します。

40 億の数 = 2^32、つまり 10 MB では不十分な場合があります。

編集

最適化が可能です。両端のリーフが作成され、共通の親を持つ場合は、それらを削除して、親にソリューションではないというフラグを立てることができます。これにより、枝がカットされ、メモリの必要性が減少します。

編集Ⅱ

ツリーを完全に構築する必要もありません。数値が類似している場合にのみ、深い分岐を構築する必要があります。枝も切ると、この解決策が実際に機能する可能性があります.

score 5 · Accepted Answer

1 GB バージョンについて回答します。

質問には十分な情報がないため、最初にいくつかの仮定を述べます。

整数は 32 ビットで、範囲は -2,147,483,648 ～ 2,147,483,647 です。

擬似コード:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}

score 3 · Accepted Answer

2 ^{128*10 ¹⁸} + 1 (これは (2 ⁸ ) ^{16*10 ¹⁸} + 1 ) - 今日の普遍的な答えではないでしょうか? これは、現在のファイルシステムの最大ファイルサイズである 16 EB ファイルでは保持できない数値を表します。

score 3 · Accepted Answer

ビット消去

1 つの方法はビットを削除することですが、実際には結果が得られない可能性があります (そうならない可能性があります)。疑似コード:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set)
foreach long fileVal in file
{
    val = val & ~fileVal;
    if (val == 0) error;
}

ビット数

ビット数を追跡します。最小量のビットを使用して値を生成します。繰り返しますが、これは正しい値を生成する保証はありません。

範囲ロジック

順序付けられた範囲 (開始順) のリストを追跡します。範囲は次の構造で定義されます。

struct Range
{
  long Start, End; // Inclusive.
}
Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

ファイル内の各値を調べて、現在の範囲から削除してみてください。このメソッドにはメモリの保証はありませんが、かなりうまくいくはずです。

score 3 · Accepted Answer

ライアンが基本的に言ったように、ファイルをソートしてから整数を調べ、そこで値がスキップされると、それがあります:)

反対票を投じた人の編集：OPは、ファイルをソートできると述べたので、これは有効な方法です。

score 3 · Accepted Answer

これは解決済みの問題だと思います (上記を参照) が、次のような質問を受ける可能性があるため、覚えておくべき興味深い副次的なケースがあります。

正確に 4,294,967,295 (2^32 - 1) の 32 ビット整数の繰り返しがなく、1 つだけが欠落している場合、簡単な解決策があります。

現在の合計をゼロから開始し、ファイル内の各整数に対して、その整数に 32 ビットオーバーフローを追加します (事実上、runningTotal = (runningTotal + nextInteger) % 4294967296)。完了したら、実行中の合計に 4294967296/2 を追加します。これも 32 ビットオーバーフローです。これを 4294967296 から引くと、結果は欠損整数になります。

「失われた整数が 1 つだけ」の問題は、1 回の実行と、データ専用の 64 ビットの RAM (実行中の合計に 32 ビット、次の整数の読み取りに 32 ビット) だけで解決できます。

当然の結果: 整数の結果に必要なビット数を気にしなければ、より一般的な仕様を一致させるのは非常に簡単です。与えられたファイルに含めることができないほど大きな整数を生成するだけです。繰り返しますが、これは最小限の RAM しか占有しません。擬似コードを参照してください。

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}

score 2 · Accepted Answer

32ビットの制約を想定していない場合は、ランダムに生成された64ビットの数値（または悲観論者の場合は128ビット）を返すだけです。衝突の可能性は1 in 2^64/(4*10^9) = 4611686018.4（およそ40億分の1）です。あなたはほとんどの場合正しいでしょう！

（冗談...ちょっと。）

score 1 · Accepted Answer

いくつかのツリー構造に未訪問の整数の範囲を格納することにより、既存の整数を読み取った後、欠落している整数の検索を高速化できます。

[0..4294967295]を格納することから始め、整数を読み取るたびに、その整数が含まれる範囲をスプライスし、空になると範囲を削除します。最後に、範囲にない整数の正確なセットがあります。したがって、最初の整数として5を表示すると、[0..4]と[6..4294967295]になります。

これはビットのマーキングよりもはるかに遅いため、ツリーの下位レベルをファイルに保存できる場合は、10MBの場合の解決策になります。

このようなツリーを格納する1つの方法は、範囲の開始をキーとして、範囲の終了を値として持つBツリーです。最悪の場合の使用法は、すべての奇数または偶数の整数を取得する場合です。これは、ツリーに2^31の値または数十GBを格納することを意味します...痛い。最良のケースは、ツリー全体に少数の整数のみを使用するソート済みファイルです。

ですから、正解ではありませんが、この方法について言及したいと思いました。私はインタビューに失敗すると思います;-)

score 1 · Accepted Answer

それらを並べ替える必要はありません。それらのサブセットを繰り返し分割するだけです。

最初のステップは、クイックソートの最初のパスのようなものです。整数 x の 1 つを選択し、それを使用して配列を通過させ、x 未満のすべての値をその左に配置し、x より大きい値をその右に配置します。x のどちらの辺が利用可能なスロットの最大数を持っているかを見つけます (リストにない整数)。これは、x の値とその位置を比較することで簡単に計算できます。次に、サブリストの分割を x のその側で繰り返します。次に、使用可能な整数の最大数などを使用して、サブサブリストでパーティションを繰り返します。空の範囲に到達するための比較の合計数は、約 40 億回である必要があります。

score 1 · Accepted Answer

おそらく、私はこの質問の要点を完全に見逃していますが、ソートされた整数のファイルから欠落している整数を見つけたいですか?

ええと... 本当ですか？そのようなファイルがどのようになるか考えてみましょう:

1 2 3 4 5 6 ... 最初の欠番 ... など

この問題の解決策は簡単に思えます。

score 0 · Accepted Answer

私はこれをよく読んでいるかもしれませんが、質問には「ファイルに含まれていない整数を生成する」と書かれています。リストを並べ替えて、最大エントリに1を追加します。Bam、ファイルに含まれていない整数。

score 0 · Accepted Answer

古い質問ですが、「非機能」要件について疑問に思います。私の意見では、手がかりが与えられるべきです-この質問が本以外の場所で尋ねられた場合、その後、すべての可能性を長所と短所で議論します. 多くの場合、それは就職の面接での質問のように思われますが、ソフト要件を知らずに明確な答えを与えることはできないため、私は当惑しています。 "。

そのような質問は、合理的な答えを与えることができるかもしれないと思います.

int ごとに 4 バイトを使用して、すべての数値を新しいファイルにマージソートします。もちろん、これは最初は遅くなります。ただし、少ないメモリ量で実行できます (必ずしもすべてを RAM に保持する必要はありません)。
二分探索を使用して、番号が事前に並べ替えられたファイルに存在するかどうかを確認します。値ごとに 4 バイトのままなので、これは問題ありません

欠点:

ファイルサイズ
最初の並べ替えが遅い - ただし必要なのは 1 回だけ

利点:

検索が非常に速い

繰り返しになりますが、本に対する非常に良い質問です。しかし、解決すべき問題が完全にはわかっていない場合に、単一の最善の解決策を求めるのは奇妙な質問だと思います。

score -1 · Accepted Answer

確かに、限られた経験 (Uni で Java の学習を始めたばかり) で言えば、int の 1 つのセット (バレル) を実行し、番号が見つからない場合はバレルを破棄できます。これにより、スペースが解放され、データの各ユニットに対してチェックが実行されます。探しているものが見つかったら、それをカウント変数に追加します。長い時間がかかりますが、セクションごとに複数の変数を作成し、各変数に対してチェックカウントを実行し、それらが同時に終了/破棄されていることを確認すると、変数ストレージは増加しませんか? そして、チェックプロセスをスピードアップします。ちょっとした考え。

algorithm - 与えられた 40 億に含まれない整数を生成する

私の分析：

私の理解（すべての回答を読んだ後）：

ケース 1: 1 GB = 1 * 10 9 * 8 ビット = 80 億ビットのメモリがあります。

解決：

実装：

ケース 2: 10 MB メモリ = 10 * 10 6 * 8 ビット = 8000 万ビット

解決：

38 に答える 38

法則

の証拠