Question

Next, create a simple benchmark experiment using the timeit module as we did in class. • Run each of your functions 1 time (e.g. quad_timest timeit(number 1)) for list sizes ranging from 1,000 to 20,000 in increments of 1,000. You will notice that the quadratic time function really starts to slow down as the size of the list Increases Display a table the run times (should look something like this: ratio 906 Size Tinear 3000, 0.00000 15000 3000, 0.0001202000. 5000, 0.000196000, 7000, 0.0002693000, 5000, 0.00033840 , 11000, 0.0004093000. 3000, 0.0005009000, 30. 1.0005410000 170000.0006279000 19.000 0.0006926000, Quad 0.038. 0.287, 0.001 1.562, 2.124, 4072 5800 8349 9524 10801 12931 14263 16398 5.453, 6.996, 9.956, 11.357, • Save the run times in a list and plot the average result of your runs for the two functions. Use the matplatlib library in python to create your plot. • Overaly plots of y = scale*login), and yescaleniogin). Set the constant "scale" so that the lines start at approximately the same level when size = 1.000. You should get a chart something like this: Run times - Linear — Quadratic nog time run time 2500 5000 7500 10000 12500 15000 17500

Answer 1

NOTE: Since the list size is very large, output generation takes time, so wait patiently while running program.

Here the value of scale is set to 1, setting it to 0.0000000001 may produce the required result.

CODE:

import random
import timeit 

def f_linear(x):
    minimum = x[0]
    for i in x:
        if i < minimum:
            minimum = i
    return minimum

def f_quadratic(x):
    min = x[0]
    l = len(x)
    for i in range(l):
        for j in range(i+1,l):
            if x[i]<x[j] and x[i]<min:
                min = x[i]
    return min


linear = []
quad = []
s=[]
print("Size","Linear      ","Quad ","Ratio")
for size in range(1000,20000+1,2000):
    #Creating list of required size
    l = [random.randint(1,1000) for _ in range(size)]
    
    # Calling the above functions and saving their time
    t = timeit.Timer('f_linear(l)','from __main__ import f_linear,l')
    linear_time = t.timeit(number = 1)
    p = timeit.Timer('f_quadratic(l)','from __main__ import f_quadratic,l')
    quad_time = p.timeit(number = 1)
    
    # Calculate ratio
    ratio = quad_time/linear_time
    
    # Printing the data
    print(size,format(linear_time,'.10f'),format(quad_time,'.4f'),int(ratio))
    
    # Appending time to lists for further plotting
    linear.append(linear_time)
    quad.append(quad_time)
    s.append(size)
    
import matplotlib.pyplot as plt
import math
plt.plot(s,linear,'r-',label='Linear')
plt.plot(s,quad,'b-',label='Quadratic')
scale = 1
y1 = [scale*math.log(n) for n in linear]
y2 = [scale*n*math.log(n) for n in quad]
plt.plot(s,y1,'y-',label='Log time')
plt.plot(s,y2,'g-',label='nLog time')

                

OUTPUT:

import random import timeit def f linear(x): minimum = x[0] for i in x: if i < minimum: minimum = i return minimum def f_quadratic(x): min = x[0] 1 = len(x) for i in range(1): for j in range(i+1,1): if x[i]<x[j] and x[i]<min: min = x[i] return min

quad = [] S=[] print("Size", "Linear ", "Quad ", "Ratio") for size in range (1000, 20000+1, 2000): #Creating list of required size 1 = [random.randint(1,1000) for _ in range (size)] # Calling the above functions and saving their time t = timeit. Timer('f_linear(l)', 'from_main_ import f_linear,l') linear_time = t.timeit(number = 1) p = timeit. Timer('f_quadratic(l)', 'from_main_ import f_quadratic,l') quad_time = p.timeit(number = 1) # Calculate ratio ratio = quad_time/linear_time # Printing the data print(size, format(linear_time,'.10f), format(quad_time,'.4'), int(ratio)) # Appending time to lists for further plotting linear.append(linear_time) quad.append(quad_time) s.append(size) import matplotlib.pyplot as plt import math plt.plot(s, linear, 'r-', label='Linear') plt.plot(s, quad, 'b', label='Quadratic') scale = 1 y1 = [scale*math.log(n) for n in linear] y2 = [scale*n*math.log(n) for n in quad] plt.plot(s, y1, 'y-', label='Log time') plt.plot(s,y2,'g-', label='nLog time')

Size Linear Quad Ratio 1000 0.0000282000 0.0380 1347 3000 0.0001049000 0.3357 3200 5000 0.0001179000 0.9323 7907 7000 0.0001668000 2.3405 14032 9000 0.0002116000 3.1143 14717 11000 0.0002727000 5.4568 20010 13000 0.0003242000 6.4958 20036 15000 0.0003583000 9.0660 25302 17000 0.0003990000 11.7906 29550 19000 0.0004756000 14.4561 30395 : [<matplotlib.lines.Line 2D at Ox1ccde5dodd8>] 2500 5000 7500 10000 12500 15000 17500