KeyError checking magnitud on Python

Admin 1
Viewed 71

In Python, analyzing same operations(same methods) i observe that in different types of data, list and dictionary in this case, they have different efficiency (Big-O). For example:

# dictionary O(1) vs list O(n)

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")
    # not defining function, use the list x object in our test

    x = list(range(i))
    tempo_list = t.timeit(number=1000)
    x = {j: None for j in range(i)}
    tempo_dictionary = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, tempo_list, tempo_dictionary))

Similarly but with the operator del

remove = timeit.Timer("del x[0]", "from __main__ import x")
for i in range(1000000, 100000001, 1000000):
    x = list(range(i))
    rlist = remove.timeit(number=1000)
    x = {j: None for j in range(i)}
    rdict = remove.timeit(number=1000)
    print("%15.5f, %15.5f" % (rlist, rdict))

But I have a problem...

Traceback (most recent call last):
  File "/home/jrr/.config/sublime-text 3/Packages/User/Python/example.py", line 9, in <module>
    rdict = remove.timeit(number=1000)
  File "/usr/lib/python2.7/timeit.py", line 202, in timeit
    timing = self.inner(it, self.timer)
  File "<timeit-src>", line 6, in inner
KeyError: 0
big-o python
1 Answers

It's because you've deleted 0 from the dictionary, so on subsequent calls, there is no x[0]:

x = {0: None, 1: None}
del x[0]
# x = {1: None}
del x[0]
# KeyError

I'd suggest doing some sort of function where you go through a list of keys x.keys() and you delete each one subsequently. Whether or not you can do that in Timer, I'm sure someone much more skilled with that module can speak to better than I can.

As a note, a list lookup with an index like x[1115] is of O(1), not O(N)

user_78679680
Related