0〜1024までのラベルがついた箱が左から一列に並んでおり、それぞれの箱には0か1の数字が書かれたボールが一つずつ入っている。0の箱には0のボールが、1024の箱には1のボールが入っていて、右隣の箱のボールの数字は左隣の箱のボールの数字より必ず大きいか等しい。すなわち、次のようになっている。
0 … 0 1 … 1
このとき、どこから1になっているかを調べる。ただし、箱を調べるとき、必ず左(0の箱)から歩いていってその箱の前に行ってからボールを取り出して調べることになる。すなわち、アクセス時間はラベルに比例する。このとき、どのようにすれば速く調べられるだろうか。
これは、メモリリークのタイミングを調べているときに思いついた。メモリリークはプログラムが終了してみないとわからないので。
アクセス時間が一定の場合、2分探索だと次のようになるだろうか。
def find(start, end, x):
if end - start == 1:
return 0
else:
half = (start + end) / 2
if half < x:
return find(half, end, x) + 1
else:
return find(start, half, x) + 1n = 1024
sum = 0
for x in range(1, n + 1):
sum += find(0, n, x)print sum / float(n)
1にはじめてなるのが、1〜1024のときにそれぞれ2分探索で何回箱にアクセスしているか調べている。平均10となった。というか、すべての場合に10である。
では、アクセス時間が上のhalfの場合どうなるだろうか。