

> Q.最大で40億個の32ビット整数がでたらめな順に入っているファイルがあるとします。このファイルに入っていない32ビット整数を一つ見つけてください。  
>  『珠玉のプログラミングー本質を見抜いたアルゴリズムとデータ構造』 column2.1.A より

と言う問題です。

本に載っている解き方としては、

>
> 40億個の整数を最初のビットが0のものと1のものにわけて、2つのファイルに書き込んでいきます。それぞれのファイルに20億個の整数が書かれているはずです。次に、出力されたファイルで整数の個数の少ない方を新しい入力ファイルとし、今度は2番目のビットをみてこれを2つのファイルに分けます。そしてこれを次々と繰り返していくと出力させる。

と言うものです。

この方法をPythonでコード化することができません。調べ方が悪いのかこの方法でやっている人も見つけられませんでした。

Pythonでコード化する方法もしくは答えをご提示していただけないでしょうか？


CC BY-SA 4.0
2019-03-30T07:43:43.320
53825
2019-04-03T14:53:25.510
2019-03-30T08:30:45.053
3060
31353
question
python アルゴリズム
32ビット整数がでたらめな順に入っているファイルに入っていない32ビット整数を一つ見つけてください。


> 「整数の先頭ビットを読み出す」部分がわかりません。

組み込み関数の `bin` や `format` を使うと良いでしょう。  
[組み込み関数 — Python 3.7.3
ドキュメント](https://docs.python.org/ja/3/library/functions.html#bin)

[code]

    >>> format(2**32-1, '032b')
    '11111111111111111111111111111111'
    
[/code]

>
> ０と1のランダムに並んだ４０億個の３２ビット整数の入力ファイルの作り方と、分けたファイルを新しい入力ファイルとし、２番目のビットを見ていくと言う部分がわかりません。大量のリストを作っていく感じなのでしょうか？

ファイルを作る、というのは文字通りファイルを作るという意味で、これは40億要素のリストを作成するとメモリに乗り切らないため、1行ずつ読み込みつつ順次ファイルを作成していくことで最終的にメモリに乗り切るサイズにするのが目的になります。

Pythonにおけるファイルの作り方や書き込みの仕方としては、以下のようになります。

[code]

    file_name = '0.txt'
    file_path = '/tmp/{}'.format(file_name)
    with open(file_path, 'w') as f: # ファイルオープン
        f.write('some_string') # 書き込み
    
[/code]

これらを組み合わせることで、実装可能になるはずです。


CC BY-SA 4.0
2019-03-30T08:51:30.957
53830
2019-03-30T08:51:30.957
29826
53825
answer


# 最初の回答（誤りが多い）

本のやりかたですと、32bit整数は2^32=4,294,967,296個あり、整数の個数の上限が4*10^9=4,000,000,000個なので最悪ファイルを40億個作らなければならなくなり、正直おすすめできません。例えば0,
1, 2, ...,
3,999,999,999と32bit整数を配置したファイルを読み込んだ場合にたくさんのファイルを生成します。そのようなことをすればファイルシステム自体がパンクするでしょう。

このアルゴリズムはC言語をターゲットにしているものと思いますが、Pythonは整数型がイミュータブルなのでファイルを４バイトずつリードするといずれメモリがパンクします。これを回避するためには１バイトリードを４回行うのがよいでしょう。numpyを使うという手もあると思います。

ファイルにおける32bit整数というのは、テキスト１行で表している場合もあるでしょうが、おそらくこの本ではバイナリデータのことを差していて、たいていのPCではリトルエンディアンを採用しているので最上位ビットは４バイトデータのうちの４バイト目（１始まりの場合）のbit7です。

試しにバイナリデータをリード／ライトするコードを書いていくとよいでしょう。例えばファイルに１バイト、37('%')というデータをライトするコードはこのような感じです。リードも同様ですが、とにかく検索エンジンで調べてみてください。

[code]

    import sys
    import struct
    
    out = open("out1.txt", "w")
    out.write(struct.pack('B', 37))
    out.close()
    
[/code]

最上位ビットが０か１かを判定するには論理積演算子(&)などを用います。

とにかく本に書いてある方法を実際に実装しようとすると、まず、判定用の出力ファイルの名前を決めるところから始めないといけないと思います。この処理をとにかく32段繰り返す必要がありますが、このルーチンを書くためには木(tree)という概念と深さ優先探索というアルゴリズム、つまり再帰を理解する必要があるでしょう。

もしかしたらその本に書いてあるアルゴリズムは、「分かっている人」向けのジョークなのかもしれませんね。ファイルに書くか、メモリに置くかということだけでも一考に値します。私はPythonのみならずC言語においてもそのようなプログラムを記述したくないです。

こんなネガティブな回答になってしまって申し訳ありません。

# ２回目の回答

私の回答に誤りが多数含まれていましたので訂正させていただきます。まず、Pythonでは数値型をイミュータブルで扱うので大量の数値を扱うとメモリがパンクするということについて、実はそうでないことを示します。

[code]

    for i in range(0, 1000000000):
        print(str(i))
    
[/code]

このプログラムはPython
3系において正しく動作します。それぞれの数値のデータ領域は、必要とされなくなった時に正しく解放されるためメモリを食い尽くす現象が発生しないものと思います。

次に、表題に示されているプログラムをデバッグすることは非常に困難であると考えるため、C言語によるバイナリライトプログラムを提示します。0x00000000から0xFFFFFFFFまでをライトするプログラムです。

[code]

    #include <stdio.h>
    
    int main() {
        FILE *out;
        unsigned int i;
        unsigned int j;
        unsigned int end_j;
        unsigned int buf[0x400];
    
        out = fopen("out3.txt", "wb");
        i = 0;
        do {
            for (j = 0; j < 0x400; ++j)
                buf[j] = i + j;
            fwrite(&buf, sizeof(unsigned int), 0x400, out);
            i += 0x400;
        } while (i);
        fclose(out);
    
        return 0;
    }
    
[/code]

このプログラムはちょうど16GBのファイルを生成するため、大量のディスク容量をもつストレージで実行してください。私はうっかりCドライブ(SSD)上でこれを実行してしまったためWindowsを不安定にしてしまいました。作成したバイナリデータを見ると、正しくデータが作成されていることが分かります。

[code]

    $ od -N 100 -t x1 out3.txt
    0000000 00 00 00 00 01 00 00 00 02 00 00 00 03 00 00 00
    0000020 04 00 00 00 05 00 00 00 06 00 00 00 07 00 00 00
    0000040 08 00 00 00 09 00 00 00 0a 00 00 00 0b 00 00 00
    0000060 0c 00 00 00 0d 00 00 00 0e 00 00 00 0f 00 00 00
    0000100 10 00 00 00 11 00 00 00 12 00 00 00 13 00 00 00
    0000120 14 00 00 00 15 00 00 00 16 00 00 00 17 00 00 00
    0000140 18 00 00 00
    0000144
    $ od -j 17179869084 -N 100 -t x1 out3.txt
    177777777634 e7 ff ff ff e8 ff ff ff e9 ff ff ff ea ff ff ff
    177777777654 eb ff ff ff ec ff ff ff ed ff ff ff ee ff ff ff
    177777777674 ef ff ff ff f0 ff ff ff f1 ff ff ff f2 ff ff ff
    177777777714 f3 ff ff ff f4 ff ff ff f5 ff ff ff f6 ff ff ff
    177777777734 f7 ff ff ff f8 ff ff ff f9 ff ff ff fa ff ff ff
    177777777754 fb ff ff ff fc ff ff ff fd ff ff ff fe ff ff ff
    177777777774 ff ff ff ff
    200000000000
    
[/code]

実行時間は2～3分といったところです。ちなみに私はWSL上のUbuntuで実行しました。

[code]

    $ time ./write3
    
    real    2m22.821s
    user    0m16.391s
    sys     2m6.141s
    
[/code]


CC BY-SA 4.0
2019-04-02T15:23:08.320
53873
2019-04-03T13:06:50.577
2019-04-03T13:06:50.577
31654
31654
53825
answer


## 特定の位置のビットが 0 か 1 か判定する方法

このアルゴリズムを使う場合、与えられた 32 bit 整数 `n` の `i` 番目のビットが `0` か `1`
か判定する必要があります。今回のアルゴリズムでは「`i`
番目のビット」は上位ビットから数えることも下位ビットから数えることもできます。ここでは下位ビットから数えることにします。またプログラムの分かりやすさのため、解説文と異なり「最初のビット」を「0
番目のビット」と数えることにします。

`n` の `i` 番目のビットが `0` か `1` か判定するためには、ビット演算を使うと簡単にできます。`i` 番目のビットだけ `1`
で後のビットは `0` の数 `mask` を用意し、`n` と `mask` をビットごとに AND 演算し、`i` 回右シフトすると良いです。

具体例を使って考えてみます。`n = 42`, `i = 3` とします。

[code]

                  n = 0b_0010_1010
               mask = 0b_0000_1000
           n & mask = 0b_0000_1000
    (n & mask) >> i = 0b_0000_0001
    
[/code]

このように、`(n & mask) >> i` の計算結果が `0` か `1` かを見れば、`i` 番目のビットが `0` か `1`
かを判定することができます。

なお、細かいことを書いておくと今回のアルゴリズムでは単にビットのパターンだけ見ているので、ビッグエンディアン／リトルエンディアンの違いや、符号付き整数における
1 の補数／2 の補数の違いを気にする必要はありません。ビットが 1
つでも異なれば整数としても異なるということだけが保証されていれば良いです。たとえば逆に浮動小数点数だと `+0` と `-0`
は最上位ビットが異なるものの等しい数なので、今回のアルゴリズムをそのまま使うことができません。

## 入力用のファイルを生成する方法

でたらめな整数を重複を許して 40 億個生成するなら、単にランダムな整数の生成を 40 億回行いつつ、ファイルに追記していけば良いです。Python では
[`random.randint(a,
b)`](https://docs.python.org/ja/3/library/random.html#functions-for-integers)
を使うとランダムな整数を作れます。ファイルへ追記するには、`open()` する際のオプションを [`'a'`
にすると良いです](https://docs.python.org/ja/3/library/functions.html#open)。

以下がサンプルプログラムです。

[code]

    import random
    
    filename = 'input.txt'
    input_num = 40_0000_0000  # この数はもっと小さめにすることをオススメします。
    
    # Python 3 の整数は勝手に多倍長にされるので、以下の式は 32 bit 環境でも問題ないです。
    # 問題文には「32 bit 整数」が符号付きなのか符号無しなのか指定がありません。ここでは符号付きにしていますがどちらでも良さそうです。
    int32_min = - (1 << 31)
    int32_max = (1 << 31) - 1
    
    if __name__ == '__main__':
        random.seed()
    
        # もしファイルが存在していたら、中身を削除する。
        open(filename, 'w').close()
    
        # append モードでファイルを開き、乱数をたくさん書きこむ。
        with open(filename, 'a') as f:
            for i in range(input_num):
                n = random.randint(int32_min, int32_max)
                f.write(str(n) + '\n')
    
[/code]

実際には、40 億行のファイルを作るには時間がかかりますし、ファイルサイズも膨大になります（30 GB くらい？）。小さめの数で試すのが良いでしょう。


CC BY-SA 4.0
2019-04-02T19:07:57.757
53875
2019-04-02T19:07:57.757
19110
53825
answer


すみません、長い回答をした後で申し訳ないのですが一応「答え」のプログラムらしきものができましたので掲載しておきます。テストはあまりしていないのでバグがあるかもしれません。よろしくお願いします。

[code]

    import struct
    
    def filter(infile, outfile0, outfile1, bit_index):
        in1 = open(infile, "rb")
        out0 = open(outfile0, "wb")
        out1 = open(outfile1, "wb")
        cnt0 = 0
        cnt1 = 0
        mask = 1 << bit_index
        data = in1.read(4)
        while len(data) == 4:
            n, = struct.unpack('I', data)
            if n & mask == 0:
                out0.write(data)
                cnt0 += 1
            else:
                out1.write(data)
                cnt1 += 1
            data = in1.read(4)
        in1.close()
        out0.close()
        out1.close()
        return cnt0, cnt1
    
    cnt0, cnt1 = filter("in1.txt", "tmp0", "tmp1", 31)
    if cnt0 <= cnt1:
        state = 0
        pred = 0
    else:
        state = 1
        pred = 1
    
    for i in range(30, -1, -1):
        #print("i: " + str(i) + ", pred: " + str(pred) + ", state: " + str(state))
        if state == 0:
            cnt0, cnt1 = filter("tmp0", "tmp1", "tmp2", i)
            if cnt0 <= cnt1: state = 1
            else: state = 2
        elif state == 1:
            cnt0, cnt1 = filter("tmp1", "tmp2", "tmp0", i)
            if cnt0 <= cnt1: state = 2
            else: state = 0
        else:
            cnt0, cnt1 = filter("tmp2", "tmp0", "tmp1", i)
            if cnt0 <= cnt1: state = 0
            else: state = 1
        pred <<= 1
        if cnt0 > cnt1:
            pred += 1
    
    print(pred)
    
[/code]


CC BY-SA 4.0
2019-04-03T14:53:25.510
53896
2019-04-03T14:53:25.510
31654
53825
answer