1

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

と言う問題です。

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

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

と言うものです。

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

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

4
  • 質問の内容としては、 本に載っている解き方をPythonのコード化する方法 もしくは 本に載っている解き方以外でのPythonによる解き方 、ということでしょうか? > Pythonでコード化する方法もしくは答え
    – PicoSushi
    Commented 2019年3月30日 8:11
  • いえ、本に載っている解き方どおりのPythonでのコード化です。以外の方法では解けたのですが、掲載どおりのコード化ができません。本に掲載されている解答は説明文だけであるため、他の言語でも書かれていません。編集ありがとうございます。
    – user31353
    Commented 2019年3月30日 8:17
  • 解法を分解すると、「整数の先頭ビットを読み出す」「ファイルへの出力」「ファイルサイズの取得」「ファイル読み出し」「文字列を数字に変換する」のように分かれると思いますが、どの部分が分からないのでしょうか?
    – Liamovwv
    Commented 2019年3月30日 8:19
  • 1
    「整数の先頭ビットを読み出す」部分がわかりません。あとは、解法の分解のどこに入るのかわからないのですが、0と1のランダムに並んだ40億個の32ビット整数の入力ファイルの作り方と、分けたファイルを新しい入力ファイルとし、2番目のビットを見ていくと言う部分がわかりません。大量のリストを作っていく感じなのでしょうか?
    – user31353
    Commented 2019年3月30日 8:27

4 件の回答 4

1

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

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

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

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

              n = 0b_0010_1010
           mask = 0b_0000_1000
       n & mask = 0b_0000_1000
(n & mask) >> i = 0b_0000_0001

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

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

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

でたらめな整数を重複を許して 40 億個生成するなら、単にランダムな整数の生成を 40 億回行いつつ、ファイルに追記していけば良いです。Python では random.randint(a, b) を使うとランダムな整数を作れます。ファイルへ追記するには、open() する際のオプションを 'a' にすると良いです

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

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')

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

0

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

組み込み関数の binformat を使うと良いでしょう。
組み込み関数 — Python 3.7.3 ドキュメント

>>> format(2**32-1, '032b')
'11111111111111111111111111111111'

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

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

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

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

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

1
  • ありがとうございます。formatだと0b入らないんですね。ただ、ファイルの作り方や書き込みの仕方についてはやってみたのですがうまく実装できませんでした。※最初の入力ファイルは小規模にして手入力でしました。色々ありがとうございます。本当に申し訳ありませんが、もし可能であれば0000から1111の15個規模でサンプルを作っていただけないでしょうか?
    – user31353
    Commented 2019年3月30日 9:08
0

最初の回答(誤りが多い)

本のやりかたですと、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は整数型がイミュータブルなのでファイルを4バイトずつリードするといずれメモリがパンクします。これを回避するためには1バイトリードを4回行うのがよいでしょう。numpyを使うという手もあると思います。

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

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

import sys
import struct

out = open("out1.txt", "w")
out.write(struct.pack('B', 37))
out.close()

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

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

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

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

2回目の回答

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

for i in range(0, 1000000000):
    print(str(i))

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

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

#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;
}

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

$ 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

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

$ time ./write3

real    2m22.821s
user    0m16.391s
sys     2m6.141s
3
  • 2
    ファイルを40億個作る必要はありません。最大でも64個です。1回の操作でN個の整数が(N/2)個以下になり、1回の操作で毎回ファイルを2つ作成するからです。また、ファイル名は使いまわせるので、入力用に1つと出力用に2つの合計3つ決めれば充分です。
    – nekketsuuu
    Commented 2019年4月2日 17:43
  • そうですね、投稿してから気づきました。過ちはそのまま残しておきます。 Commented 2019年4月3日 0:07
  • 回答中に深さ優先探索を使う必要があると書かせていただきましたが不要でした。なぜならば2^32 > 4*10^9であり、ファイル中にない整数が存在することが分かっているためです。従って各ビットについて見ていくときに小さいほうのファイルにはビットiについて2^i個より少ないことが保証されます。従ってこのプログラムは再帰でなく単純なループで記述することができるでしょうし、必要なファイル数は最大64個、使いまわしをする必要はなく、使いまわす場合は3個でいけると思います。 Commented 2019年4月3日 0:18
0

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

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)
1
  • ちなみにこのプログラムに0x00000000...0xFFFFFFFFのバイナリファイルを入力して実行した場合、実行時間は96m7.574sでした。案外速く処理できるらしく興味深いです。題意を満たす入力であればこの時間よりも速く完了するはずです。 Commented 2019年4月4日 10:04

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。