I’ve been trying to use parametrised decorators and time function for becnhmark binary search vs linear algorithms running time and I don't understand, why with list size == 100m binary search runs 0.000014 sec and linear search runs 4.904940 sec. Where is my mistake? Or is it a normal speed for modern cpus? A few hours ago I set list size to 1b and run script. My pc frozen on a few hours and I forced a reboot it. PS My CPU is 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]))
Binary search runs on log(n) and linear search runs on n. That means that the first one only has to do log(n) iterations, and log2(100000000) = 26.5754. So you are basically comparing 27 iterations vs 100m.