-1

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]))
phaestos
  • 25
  • 4
  • 3
    You should use `timeit.default_timer` or `time.perf_counter` rather than `time.time` for this purpose; see [here](https://stackoverflow.com/a/25823885/12299000). – kaya3 Jun 25 '22 at 21:42

2 Answers2

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.

Norhther
  • 545
  • 3
  • 15
  • 35
  • Thanks. But i trying to calculate running time for each algorithm. And I saw a strange linear algorithm running time: <5sec for 100m list and >2hr for 1b list. Why it can be if in case of log(n) elapsed time must be x10(100m x10 = 1b) – phaestos Jun 25 '22 at 22:04
  • 2
    @phaestos Perhaps your list of length 1 billion was exceeding the available system memory and going into [swap](https://en.wikipedia.org/wiki/Memory_paging#Unix_and_Unix-like_systems), which is much slower than RAM. – kaya3 Jun 25 '22 at 22:15
  • Thank you sir. You're absolutely right. My program with list==1b eats 26gb of ram and 13gb of swap. It's 99.3% of ram and 85% of swap. Before the reboot, there were much fewer free resources and this led to an out of memory and swap. And now I have result of algorithms running: Binary search: 0.076235 sec. Linear search: 519.089405 sec. Awesome difference! Thanks for help! – phaestos Jun 26 '22 at 08:01
1

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

olegr
  • 1,999
  • 18
  • 23
  • I understand. But can't understand why linear search ran over than 50 sec for 1b if it ran 4.9 sec with 100m? – phaestos Jun 25 '22 at 21:58