Home > Software engineering >  Can't understand why algorithm work so fast
Can't understand why algorithm work so fast

Time:06-26

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]))

CodePudding user response:

Looks like there is no error in your code)

It simply finds a number in in 27 iterations

Call function binary_search with duration 0.000125

This is for 1B numbers. Probably you had an error a couple of hours ago when your PC froze

CodePudding user response:

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.

  • Related