I wrote a piece of code where the list size increases with each iteration and iterations can reach almost 100000 times.
while N < 100000:
if k not in Lst:
Dct[k] = True
while N < 100000:
if Dct[k] == False:
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()
set() objects use a hash table as well.