気になったこと

そう言えば昨日の実験では、Pythonの組み込み関数sort()を使ってなかったなぁ
なのでやってみた。

# Compare some 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):
    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 Measurement(DefNum, target, numList):
    if DefNum == 1:
        print "Search"
        start = time.clock()
        Search(target, numList)
        print time.clock() - start
        
    elif DefNum == 2:
        print "Search2(Bubble)"
        start = time.clock()
        Bubble(numList)
        Search2(target, numList)
        print time.clock() - start

    elif DefNum == 3:
        print "Search3(sort())"
        start = time.clock()
        numList.sort()
        Search2(target, numList)
        print time.clock() - start

def main():
    NList = [100, 1000, 10000, 100000]

    for num in NList:
        numList = [random.randint(1,1000) for i in range(num)]
        numList2 = [x for x in numList]  # copy numList
        numList3 = [x for x in numList]  # copy numList
    
        targetList = [5, num/2, num-5]

        for target in targetList:
            print num, target
            Measurement(1, target, numList)
            # Measurement(2, target, numList2)
            Measurement(3, target, numList3)
            print 

if __name__ == "__main__":
    main()


結果

E:\study>python searches.
100 5
Search
1.43521097485e-005
Search3(sort())
4.73140719185e-005

100 50
Search
1.34953232176e-005
Search3(sort())
1.34392018291e-005

100 95
Search
1.33269590522e-005
Search3(sort())
1.32745790896e-005

1000 5
Search
0.000112830180836
Search3(sort())
0.000483212637705

1000 500
Search
0.000101153190605
Search3(sort())
5.03371440449e-005

1000 995
Search
7.44207025566e-005
Search3(sort())
4.67865308668e-005

10000 5
Search
4.59896071503e-005
Search3(sort())
0.0047834204947

10000 5000
Search
0.000689675743089
Search3(sort())
0.000348210766992

10000 9995
Search
0.000691711078778
Search3(sort())
0.000348843067969

100000 5
Search
0.000211248389108
Search3(sort())
0.054637827063

100000 50000
Search
0.00665795344003
Search3(sort())
0.00277092246934

100000 99995
Search
0.00661934940761
Search3(sort())
0.00275640573685

リストの要素が100,1000,10000,100000で実験。
その中の5番目,真ん中,後ろから5番目を探索することに。
意外に線形探索が頑張ったような気がする。
sort()って確かクイックソートが実装されてるんじゃなかったっけかな。
だとしたら、よほど大きな探索対象じゃない限りはとりあえず線形探索を使っておけば間違いないのかな。

追記

ソースコード中のコメントアウトは、バブルソート+二分探索。
リストの要素数が100000の時に時間がかかり過ぎるので、途中で挫折した証。