clock function reporting 0.00

[AdampskiB]

# 619480
import time
from random import *

def main():
    lst = []
    result, length = 0, 500000
    while result <= 0.50:
        for i in range(length):
            lst.append(randint(1, length))
        value = randint(1, length)
        t0 = time.clock()
        linearSearch(value, lst)
        result = time.clock() - t0
        print("This LINEAR SEARCH took {0:4.2f}seconds with a length of".format(result), length)
        lst.sort()
        t0 = time.clock()
        binarySearch(value, lst)
        result = time.clock() - t0
        print("This BINARY SEARCH took {0:4.2f}seconds with a length of".format(result), length, "\n")
        lst = []
        length = length + 500000

def binarySearch(value, lst):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        item = lst[mid]
        if value == item:
            return mid
        elif value < item:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def linearSearch(value, lst):
    for i in range(len(lst)):
        if value == lst[i]:
            return i
    return -1

main()

I'm trying to time the two algorithms at the bottom using the clock function. The linearSearch get's timed fine, it gives me a value, however, when it comes to timing the binarySearch, it always reports 0.00. Why? What am I doing wrong? :s

[TrustyTony]

Seconds resolution is too coarse for binary search, move to milliseconds:

def main():
    lst = []
    result, length = 0, 500000
    while result <= 0.50:
        for i in range(length):
            lst.append(randint(1, length))
        value = randint(1, length)
        t0 = time.clock()
        linearSearch(value, lst)
        result = (time.clock() - t0) * 1000
        print("This LINEAR SEARCH took {0:4.2f} milliseconds with a length of".format(result), length)
        lst.sort()
        t0 = time.clock()
        binarySearch(value, lst)
        result = (time.clock() - t0) * 1000
        print("This BINARY SEARCH took {0:4.2f} milliseconds with a length of".format(result), length, "\n")
        lst = []
        length = length + 500000

You might also find it handy to use timing decorator like this (just write @timing at line before definition of the function you want to time)

import time
from functools import update_wrapper

def timestr(t):
    return ( ("%i min %.3f s" % divmod(t, 60)) if t > 60
            else  (("%.3f s" % t) if t > 1
                   else "%.3f ms" % (t * 1000) ) )

def timing(func):
    def wrapper(*arg, **kwargs):
        t1 = time.clock()
        res = func(*arg, **kwargs)
        t2 = time.clock()
        print('%s took %s' % (func.__name__, timestr(t2-t1)))
        return res

    return update_wrapper(wrapper, func)

or you might start to use the timeit module

I recommend also to take look at http://paulbutler.org/archives/python-debugging-with-decorators/ or similar decorators from net to make your life easier.

[Gribouillis]

Here is a version with timeit

# 619480
import time
from random import *
from timeit import Timer
timer = Timer("binarySearch(Spam.value, Spam.lst)", "from __main__ import Spam, binarySearch")
class Spam:
    pass

def main():
    lst = []
    result, length = 0, 500000
    while result <= 0.50 and length < 10**7:
        for i in range(length):
            lst.append(randint(1, length))
        value = randint(1, length)
        t0 = time.clock()
        linearSearch(value, lst)
        result = time.clock() - t0
        print("This LINEAR SEARCH took {0:4.2f}seconds with a length of".format(result), length)
        lst.sort()
        number = 1000
        Spam.value, Spam.lst = value, lst
        result = timer.timeit(number)
        #t0 = time.clock()
        #binarySearch(value, lst)
        #result = time.clock() - t0
        print("This BINARY SEARCH took {0:4.2e}seconds with a length of".format(result/number), length, "\n")
        lst = []
        length = length + 500000

def binarySearch(value, lst):
    low, high = 0, len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        item = lst[mid]
        if value == item:
            return mid
        elif value < item:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def linearSearch(value, lst):
    for i in range(len(lst)):
        if value == lst[i]:
            return i
    return -1

main()

""" my output --->
('This LINEAR SEARCH took 0.03seconds with a length of', 500000)
('This BINARY SEARCH took 6.54e-06seconds with a length of', 500000, '\n')
('This LINEAR SEARCH took 0.07seconds with a length of', 1000000)
('This BINARY SEARCH took 5.83e-06seconds with a length of', 1000000, '\n')
('This LINEAR SEARCH took 0.24seconds with a length of', 1500000)
('This BINARY SEARCH took 7.55e-06seconds with a length of', 1500000, '\n')
('This LINEAR SEARCH took 0.59seconds with a length of', 2000000)
...
"""

[AdampskiB]

Brilliant thank you guys!