[time/timeit] Measure the time efficiency of the code

1. What is Algorithm Analysis?

An algorithm is a generic, step-by-step list of instructions for solving a problem. It is a method for solving any instance of the problem such that given a particular input, the algorithm produces the desired result.

 

Algorithm analysis is concerned with comparing algorithms based on upon the amount of computing resources that each algorithm uses.

 

We can measure the execution time of algorithm using time and timeit module.

 

The time module provides various time-related functions. And the timeit module is designed to allow Python developers to make cross-platform timing measurements by running functions.

 

2. Measure the time efficiency using time module

2.1 Methods of time module

time.time()

 

This function return the time in seconds since the epoch as a floating point number.

 

We run the time.time() method to set the start time, and run time.time() method once more to measure the end time. The difference between the ending time and the starting time is considered as the execution time of the algorithm.

 

2.2 Evaluate the time efficiency

 

# Sum of N : Algorithm1 
import time 

def sumofN(n): 
    start = time.time() 

    theSum = 0
    for i in range(1, n+1): 
        theSum += i

    end = time.time() 
    return theSum, end - start 

# Sum of N : Algorithm2 
def sumofN2(n): 
    start = time.time() 
    theSum = (n*(n+1))/2
    end = time.time() 
    return theSum, end - start 

# In case of n = 10,000,000, the execution time of two algorithms are same as below : 
# Algorithm 1 : 0.1729250 seconds
# Algorithm 2 : 0.00000095 seconds

 

3. Measure the time efficiency using timeit module

3.1 Methods of timeit module

timeit.Timer(stmt='pass', setup='pass')

 

The timeit Class is the Class for timing execution speed of small code snippets. This will return Timer object and can measure the execution time using timeit() method.

 

• stmt : Code or function to be executed
• setup : Declare code or function required in advance to execute stmt. The run time of setup is excluded from the overall measurement run time.

 

timeit.timeit(number=1000000)

 

Time number execution of the main statement. This executes the setup statement once, and then the time it takes to execute the main statement a number of times.

 

3.2 Evaluate time efficiency

def test1(): 
    l = [] 
    for i in range(1000): 
        l += [i] 
        
def test4(): 
    l = list(range(1000)) 
    
import timeit 
t1 = timeit.Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "milliseconds")
t4 = timeit.Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "milliseconds")

# concat  6.54352807999 milliseconds
# list range  0.0655000209808 milliseconds

 

3.3 Evaulate time efficiency of object

import timeit 
import random 

for i in range(10000, 1000001, 20000): 
    t = timeit.Timer(f"random.randrange({i}) in x", "from __main__ import random, x")
    x = list(range(i)) 
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)} 
    d_time = t.timeit(number=1000)
    print(f"{i}, {lst_time:.3f}, {d_time:.3f}")

 

The statement from __main__ import x, will make us to use the list object x in our test. We can evaulate the time efficiency of single operator in this way.

 

 

 

Source from :

• https://docs.python.org/3/library/timeit.html   
• https://runestone.academy/ns/books/published/pythonds/AlgorithmAnalysis/Lists.html 
• https://docs.python.org/3/library/time.html