質問

この面接の質問をされました。

40億個の整数を含む入力ファイルがあるとき、ファイルに含まれていない整数を生成するアルゴリズムを提供しなさい。メモリは1GBとする。メモリが10MBしかない場合はどうするか、追って説明しなさい。

私の分析

ファイルサイズは4×10 ⁹ ×4バイト＝16GBとなります。

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

質問は、ソートされた大きな整数の集合の中で、欠落した整数を検出する最善の方法は何かということです。

私の理解では（すべての回答を読んで）。

32ビット整数の話だとすると、2つの ³² = 4*10 ⁹ のような別個の整数です。

ケース1：1GB＝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：10MBメモリ＝10 * 10 ⁶ * 8ビット＝8000万ビット

解決策

すべての可能な16ビット接頭辞に対して、2つの接頭辞があります。 ¹⁶ 数 整数＝65536なので、2個必要です。 ¹⁶ * 4 * 8 = 200万ビットです。65536個のバケットを構築する必要があります。最悪の場合、40億の整数がすべて同じバケツに属することになるので、各バケツについて、すべての可能性を保持する4バイトが必要です。

1. ファイルの最初のパスを通して、各バケツのカウンターを構築します。
2. バケットをスキャンし、ヒット数が65536以下の最初のバケットを見つける。
3. ステップ2で見つけた16ビット上位接頭辞を持つ新しいバケットを構築します。 ファイルの2回目のパスを通して
4. ステップ3で構築されたバケットをスキャンし、最初にないバケットを見つける。 がヒットする。

上記のコードとよく似ています。

結論 ファイルパスを増やすことで、メモリを削減することができます。

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

解決方法は？

整数とは32ビットを意味すると仮定すると : 10MBの容量があれば、入力ファイルを一通り見て、任意の16ビット接頭辞を持つ数値の数を数えるには十分すぎるほどです。少なくともバケツの1つは、2より少ない数でヒットするはずです。 ¹⁶ 回です。そのバケツに含まれる可能性のある数字のうち、どれがすでに使われているかを調べるために、2回目のパスを実行します。

32ビット以上でも有限の大きさであることを意味する場合 : 32ビットの範囲外の数値はすべて無視します。

integer"が数学的整数を意味する場合 : 入力を一通り読み、その中から <ストライク 最大数 の長さは、今まで見た中で一番長い数です。終わったら、次のように出力してください。 <ストライク 最大値＋1 桁が1つ多い乱数。(ファイルの中の数字の一つは、正確に表現するのに10MB以上かかるビグナムかもしれませんが、入力がファイルであれば、最低限 長さ に収まるものであれば何でもよい)。