Computer Science - Python - 探索とソート(二分探索と組み込みの探索、ソート)

初めてのコンピュータサイエンス
(オライリージャパン)
Jennifer Campbell Paul Gries
Jason Montojo Greg Wilson (著)
長尾 高弘 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Python (プログラミング言語)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-1.を解いてみる。

11.7(練習問題)、11-1.

探索する回数をn回、Nは十分に大きい正の整数とする。

N log2 N + n * log2 N < n * N
N log2 N < n * (N - log2 N)
(N log2 N) / (N - log2 N) < n
N -> ∞
log2 N < n

よって、おおよそlog2 N回以上探索した時に、組み込みの探索を使うよりも、ソートしてから探索した方が高速になる。

確認。

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

import math
import time

def binary_search(v, L):
    i = 0
    j = len(L) - 1
    
    while i != j + 1:
        m = (i + j) // 2
        if L[m] < v:
            i = m + 1
        else:
            j = m - 1
    
    if 0 <= i < len(L) and L[i] == v:
        return i
    else:
        return - 1

N = 100
l = [9,0,8,1,7,2,6,4,5] * N + [10]
count = math.floor(math.log2(10 * N + 1))
print('log2 {0} = {1}'.format(len(l), math.log2(len(l))))
print("回数、二分探索、組み込み関数(L.index)、比率(二分探索/組み込み関数)")
for n in range(1, count + 10):
    l_1 = l[:]
    start = time.time()
    l_1.sort()
    for x in range(n):
        binary_search(10, l_1)
    t1 = (time.time() - start) * 1000
    start = time.time()
    for x in range(n):
        l.index(10)
    t2 = (time.time() - start) * 1000
    print("{0:2}, {1:.10f}秒, {2:.10f}秒, {3:.4f}"
        .format(n, t1, t2, t1 / t2))

入出力結果(Terminal)

$ ./sample.py
log2 901 = 9.815383295813538
回数、二分探索、組み込み関数(L.index)、比率(二分探索/組み込み関数)
 1, 0.2930164337秒, 0.0391006470秒, 7.4939
 2, 0.2830028534秒, 0.0720024109秒, 3.9305
 3, 0.2877712250秒, 0.1029968262秒, 2.7940
 4, 0.2939701080秒, 0.1380443573秒, 2.1295
 5, 0.2968311310秒, 0.1699924469秒, 1.7461
 6, 0.3039836884秒, 0.2019405365秒, 1.5053
 7, 0.3018379211秒, 0.2338886261秒, 1.2905
 8, 0.3089904785秒, 0.2679824829秒, 1.1530
 9, 0.3209114075秒, 0.2930164337秒, 1.0952
10, 0.3180503845秒, 0.3249645233秒, 0.9787
11, 0.3230571747秒, 0.3559589386秒, 0.9076
12, 0.3309249878秒, 0.3888607025秒, 0.8510
13, 0.3349781036秒, 0.4208087921秒, 0.7960
14, 0.3418922424秒, 0.4529953003秒, 0.7547
15, 0.3471374512秒, 0.4839897156秒, 0.7172
16, 0.3521442413秒, 0.5218982697秒, 0.6747
17, 0.3581047058秒, 0.5478858948秒, 0.6536
18, 0.3650188446秒, 0.5910396576秒, 0.6176
$

だいたいlog2 Nの値の9.…くらいが境目になってるから考え方は合ってるっぽい。