Data Structure/ Ch02:AlgorithmAnalysis(2)

📚 The Start of Recording TIL Summer ‘24 : Why Did I Start This Project? 🚀

🔔 Don't Miss: Continous Records of TIL '25 (Still On-Going!) 🌟

✨ A New Chapter in TIL '25: Reflecting, Growing, and Moving Forward 📖

TIL :CH02. Algorithm Anlaysis (2)

Checking Big-O performance for the operations on Python lists and dictionaries To capture the time it takes for each of functions to execute, we will use Python’s timeit module. To use timeit you creat a Timer object whose parameters are two Python statements. The timeit modle will then time how long it takes to execute the statement some numbers of times. By default timeit will try to run the statement one million times.

def test1():
    l = []
    for i in range(1000):
        l = l + [i]
    
def test2():
    l = []
    for i in range(1000):
        l.append(i)
        
def test3():
    l = [i for i in range(1000)]
    
def test4():
    l = list(range(1000))

import timeit
t1 = Timer("test1()", "from __main__ import test1")
print("concat ", t1.timeit(number=1000), "milliseconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ", t2.timeit(number=1000), "milliseconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ", t3.timeit(number=1000), "milliseconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ", t4.timeit(number=1000), "milliseconds")

concat  0.7746614349889569 milliseconds
append  0.044617620995268226 milliseconds
comprehension  0.02456232500844635 milliseconds
list range  0.010341359011363238 milliseconds

the statement “from __main__ import test1 imports the function test1 from the __main__ namespace into the name space that timeit sets upthe list comprehension is twice as fast as a for loop with an append operation.

Listing 2.10 Timing the Performance of Pop

import timeit

popzero = timeit.Timer("x.pop(0)", "from __main__ import x")
popend = timeit.Timer("x.pop()", "from __main__ import x")

x = list(range(200000))
popzero.timeit(number=1000)

4.369899397715926e-05

x = list(range(200000))
popend.timeit(number=1000)

5.691900150850415e-05

Comparing performance of pop for Different Sizes

popzero = Timer("x.pop(0)", "from __main__ import x")
popend = Timer("x.pop()", "from __main__ import x")
print("pop(0)    pop()")
for i in range(1000000, 10000001, 1000000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    print("%15.5f, %15.5f" %(pz,pt))

You can see that as the list gets longer the time it takes to pop(0) also increses while the time for pop stays very flat. This exactly what we would expect to see for a O(n) and O(1) algorithm.

pop(0)    pop()
        0.19227,         0.00005
        0.78737,         0.00004
        1.62861,         0.00009
        2.22485,         0.00004
        2.90644,         0.00004
        3.62867,         0.00004

Comparing Performance of Contains for List and Dictionary

import timeit
import random

for i in range(10000, 1000001, 20000):
    t = timeit.Timer("random.randrange(%d) in x"%i, "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("%d, %10.3f, %10.3f" % (i, lst_time, d_time))    

10000,      0.059,      0.001
30000,      0.130,      0.000
50000,      0.211,      0.000
70000,      0.275,      0.001
90000,      0.361,      0.001
110000,      0.504,      0.001
130000,      0.575,      0.000
150000,      0.617,      0.001
170000,      0.722,      0.001
190000,      0.821,      0.001
210000,      0.928,      0.000
230000,      0.989,      0.001
250000,      1.076,      0.001
270000,      1.156,      0.001

You can see that the dictionary is consistently faster. As well as for the smallest size of 10,000 elements, for the largest list size of 990,000 elements the dictionary is over 10,000 times faster

Summary

1. Algorithm analysis is an implementation-independent way of measuring an algorithm.
2. Big-O notation allows algorithms to be classified by their dominant process with respect to the size of the problem.