Time Analysis in python

Question

import math
import time
import random


def sequential_search(key,sorted_list):
    for element in sorted_list:
        if element==key:
            return True
        else :
            return False


def binary_search(key,sorted_list):
    l=0
    r=len(sorted_list)-1
    while l<=r:
        m=int(math.floor((l+r)/2))
        if key==sorted_list[m]:
            return m
        elif key<sorted_list[m]:
            r=m-1
        else:
            l=m+1


def ternary_search(key,sorted_list):
    length = len(sorted_list)
    left = 0
    right = length
    index = 0
    x = True
    while x and left <= right:
    #focal = (high + low) //3
        if left == right:
                #check similarity between values and key
                return left

        elif right - left > 0:
                index1 = ((right+2*(left))//3)
                index2 = ((2*(right)+left)//3)
                if sorted_list[index1] == key:
                        return index1
                elif sorted_list[index2] == key:
                        return index2
                else:
                        if key<sorted_list[index1]:
                                        right = index1 - 1
                        elif key > sorted_list[index1] and key <sorted_list[index2]:
                                        right = index2 - 1
                                        left = index1 - 1
                        elif key > sorted_list[index2]:
                                        left = index2+1
    return index
def interpolation_search(key, sorted_list):
    low = 0
    high = len(sorted_list) - 1

    while sorted_list[low] <= key and sorted_list[high] >= key:
        mid = low + ((key - sorted_list[low]) * (high - low)) \
              / (sorted_list[high] - sorted_list[low])
              # out of range is possible

        if sorted_list[mid] < key:
            low = mid + 1
        elif sorted_list[mid] < key:
            high = mid - 1
        else:
            return mid

    if sorted_list[low] == key:
        return low
    return None

def run_experiment():
    sorted_list=random.sample(range(1000000), 1000)
    sorted_list.sort()
    key=random.randint(0,1000001)
    key=1000001
    time_ss=time.time()
    sequential_search(key,sorted_list)
    time_ss_end=time.time()
    print time_ss_end-time_ss
    time_bs=time.time()
    binary_search(key,sorted_list)
    print time.time()-time_bs
    time_ts=time.time()
    ternary_search(key,sorted_list)
    print time.time()-time_ts
    time_is=time.time()
    interpolation_search(key,sorted_list)
    print time.time()-time_is



if __name__ == '__main__':
    run_experiment()
    raw_input("Stop")

I am new to Python. I want to measure time for these algorithms so I am using the "time" method. But the output looks like:

>>> 
0.0
0.0
0.0
0.0
>>>

Sometimes the first measurement changes. How can I change these outputs? Should I change my code for time analysis?

possible duplicate of [Accurate timing of functions in python](http://stackoverflow.com/questions/889900/accurate-timing-of-functions-in-python) — Justin R., Apr 01 '14 at 21:41

score 1 · Answer 1 · answered Apr 01 '14 at 21:42

your code is too fast to profile that way (chances are its speed is fine)

if you really want to speed profile it try this

def run_experiment():
    print timeit.timeit("sequential_search(key,sorted_list)",
                        "import random;from main import sequential_search; 
                         key=10000001;sorted_list=sorted(random.sample(range(100000),1000))")

or make the list you are testing against much larger ...

score 0 · Answer 2 · edited May 23 '17 at 12:11

0

From what I tested, your script runs very fast, in the same millisecond.

You can follow this answer and convert your time to milliseconds to get a better accurate timing.

edited May 23 '17 at 12:11

Community

1
1

answered Apr 01 '14 at 21:44

aldux

2,774
2
25
36

score 0 · Answer 3 · answered Apr 01 '14 at 21:56

The reason is that there are very little operations going on (from a computer perspective) in order to find the key and so the action completes almost immediately (thus the zero or close to zero time).

If you want to check the relative efficiency of the different methods, call each function many times in a loop like so:

    loops = 2000

    for i in range(loops):
        sequential_search(key,sorted_list)

Do this for each type of search. If you still get results that are close to zero, just make loops a larger number

Time Analysis in python

3 Answers3