気になったこと
そう言えば昨日の実験では、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()って確かクイックソートが実装されてるんじゃなかったっけかな。
だとしたら、よほど大きな探索対象じゃない限りはとりあえず線形探索を使っておけば間違いないのかな。