python: list lookup vs dict lookup

Question

I wrote a piece of code where the list size increases with each iteration and iterations can reach almost 100000 times.

sample :

def do_something():
    Lst.append(k)

while N < 100000:
    if k not in Lst:
        do_something()

now, I noticed that this method took ages to finish . Please note, I did set setrecursionlimit() . Infact embarrassing enough, the program kept running for hrs.

later, while trying to find methods to optimise the code, i converted the Lst to a Dct. So the code looked something like:

def do_something():
    Dct[k] = True

while N < 100000:
    if Dct[k] == False:
        do_something()

the code ran drastically faster. After reading few conversations on SOF(Repeatedly appending to a large list (Python 2.6.6)) , I realised its not list which is slow, but rather how memory is handled for larger list data. This website https://wiki.python.org/moin/TimeComplexity , sheds light on list and dict look-up time complexity. for list its O(n) where as a Dct lookup is O(1). Is it why Dct performs better ? How exaclty are list lookup and Dict lookup performed?

Using a `set` for this rather than a `dict` would be much better. — kindall, May 31 '14 at 14:28

Martijn Pieters · Accepted Answer · 2014-05-31T14:26:13.777

Yes, dictionary lookups take constant time. Your if k not in Lst may have to scan the whole list to see if the number is not yet in the list, before appending. It is this scan that makes list containment tests take O(n) time, and is what is killing your algorithm.

A python dictionary on the other hand, uses a hash table to test for membership. Each key is hashed (reduced to a number), with the number then being turned into in index into the table. If the key found at that location is equal to the key you are testing with, a match is found. Hashing can lead to collisions (two values hashing to the same table index), but the Python dictionary implementation has an algorithm to then look for a next slot in an efficient manner. If an empty slot is found, the containment test has failed, the key is not present.

So, to test if k is in your dictionary, for most tests just 1 calculation is needed. For some, a few more tests could be required. But on average, the lookup time is constant.

If you are curious, and understand C well enough, take a look at the C implementation for all the (well documented) details. You could also watch this Pycon 2010 presentation by Brandon Rhodes about how CPython dict works, or pick up a copy of Beautiful Code, which includes a chapter on the implementation written by Andrew Kuchling.

You way want to look at the set() type; this is, like a dictionary, an unordered collection with O(1) membership tests, but just the values, no keys:

some_set = set()

def do_something():
    some_set.add(k)

while N < 100000:
    if k not in some_set:
        do_something()

Internally, set() objects use a hash table as well.

Thank you. I will refer to the resources you had mentioned. So can we consider, list loop-up as a linear search ? — durga, May 31 '14 at 14:32
@durga: membership testing on lists is a linear search, so `k not in Lst` is the problem here. — Martijn Pieters, May 31 '14 at 14:34
thank you, i think I get the point , appending doesnot really have to scan through the complete list, just the last index of list , but as you mentioned membership testing requires the list to be scanned once at least to check. I never worked with sets() before, I will give them a try. Thanks again! — durga, May 31 '14 at 14:48
Thanks for the link to the pycon talk Martijn. I had assumed before that dicks used buckets or b-trees. Good to know the actual implementation. — Gary van der Merwe, Jun 01 '14 at 05:17

python: list lookup vs dict lookup

1 Answers1