我一直在嘗試將引數化裝飾器和時間函式用于 becnhmark 二進制搜索與線性演算法的運行時間，但我不明白，為什么串列大小 == 100m 二進制搜索運行 0.000014 秒而線性搜索運行 4.904940 秒。我的錯誤在哪里？還是現代cpu的正常速度？幾個小時前，我將串列大小設定為 1b 并運行腳本。我的電腦凍結了幾個小時，我強行重新啟動它。PS 我的 CPU 是 I5 9th Gen。
import time
def second_outer(*dargs, **dkwargs):
def outer(func):
def inner(*args, **kwargs):
print(*dargs, **dkwargs)
start = time.time()
func_result = func(*args, **kwargs)
print('Call function %s with duration %f' % (func.__name__, time.time() - start))
return func_result
return inner
return outer
arr = [i for i in range(1, 100000000)]
@second_outer('binary search')
def binary_search(arr, item):
start = 0
end = len(arr) - 1
while start <= end:
middle = (start end) // 2
guess = arr[middle]
if guess == item:
return middle
elif guess > item:
end = middle - 1
else:
start = middle 1
return None
@second_outer('linear search')
def linear_search(arr, item):
start = 0
end = len(arr)
for i in range(start, end):
if arr[i] == item:
return i
return None
print(binary_search(arr, arr[-1]))
print(linear_search(arr, arr[-1]))
uj5u.com熱心網友回復：
二分搜索在 .上運行log(n)，線性搜索在n. 這意味著第一個只需要進行log(n)迭代，并且log2(100000000) = 26.5754. 所以你基本上是在比較 27 次迭代和 100m。
uj5u.com熱心網友回復：
看起來您的代碼中沒有錯誤）
它只是在 27 次迭代中找到一個數字
Call function binary_search with duration 0.000125
這是針對 1B 號碼的。幾個小時前，當您的 PC 死機時，您可能遇到了錯誤
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/496608.html
上一篇：多邊形和圓形演算法
下一篇：根據最大值和最小值生成間隔