線形探索VSバブルソート・２分探索

続き。
線形探索とバブルソート＋二分探索で勝負してみた。

要素の数をを100, 1000, 10000の時、そして、探索場所をリストの前・真ん中・後ろの３箇所で調べてみた。

# Compare two ways of Search

import time
import random

def Search(target, numList):
    for x in numList:
        if x == target:
            return True
    return False

def Search2(target, numList):
    bubble(numList)
    min_pos = 0
    max_pos = len(numList) - 1

    while min_pos <= max_pos:
        mid_pos = (min_pos + max_pos) / 2

        if target == numList[mid_pos]:
            return True
        elif target > numList[mid_pos]:
            min_pos = mid_pos + 1
        else: # target < numList[mind_pos]
            max_pos = mid_pos - 1
    return False

def bubble(numList):
    for i in range(len(numList)):
        for j in range(i+1, len(numList)):
            if numList[i] > numList[j]:
                tmp = numList[i]
                numList[i] = numList[j]
                numList[j] = tmp

def main():
    N = 10000
    
    numList = [random.randint(1,1000) for i in range(N)]
    numList2 = [x for x in numList]
    
    target1 = 5
    target2 = N/2
    target3 = N-5

    print N
    print

    print "Linear Search"
    start = time.clock()
    Search(target1, numList)
    finish = time.clock()
    print finish - start

    start = time.clock()
    Search(target2, numList)
    finish = time.clock()
    print finish - start

    start = time.clock()
    Search(target3, numList)
    finish = time.clock()
    print finish - start

    print 
    print "Search2"
    start = time.clock()
    Search2(target1, numList2)
    finish = time.clock()
    print finish - start

    start = time.clock()
    Search2(target2, numList2)
    finish = time.clock()
    print finish - start

    start = time.clock()
    Search2(target3, numList2)
    finish = time.clock()
    print finish - start

if __name__ == "__main__":
    main()

結果は以下のとおり

D:\workspace\Python>python comparison.py
100

Linear Search
1.03306717192e-005
9.74722184629e-006
9.44647448911e-006

Search2
0.00136934482188
0.000914317077939
0.000914957669809

D:\workspace\Python>python comparison.py
1000

Linear Search
8.22303424009e-005
8.16739597901e-005
2.31936361859e-005

Search2
0.119159937445
0.0779367949354
0.0622293980542

D:\workspace\Python>python comparison.py
10000

Linear Search
0.000190661794559
0.000826772529736
0.000796321859822

Search2
7.00275457512
6.45483894077
6.58490988105

線形探索の圧勝。
まあそりゃそうか。

かたや計算量が⇒に対して、
かたや計算量が⇒
だもんな。
xが要素の数、aは適当な係数。

単純作業に勝るものはなし？？
んなことはなくて、高速なソートのアルゴリズムがいっぱいありますからね。
クイックソートなんかを使えば２分探索が勝てるのかな？？
またやってみよう。