Testing for membership speed

[brianc at temple.edu]

I just ran this stuff for my own knowledge. Though it might be
useful to some other people to know and maybe spark a discussion. 

I needed a fast way to test for membership, so naturally the
choices were the builtin containers: lists, dictionaries, and
tuples. The following is the test code and results:

import timeit

lst_i=timeit.Timer('random.randrange(10000) in l','import
random; l=range(10000)')
dct_i=timeit.Timer('l.has_key(random.randrange(10000))','import
random; l=dict([(i,None) for i in xrange(10000)])')
tup_i=timeit.Timer('random.randrange(10000) in l','import
random; l=tuple(range(10000))')

lst_str=timeit.Timer('md5.md5(str(random.randrange(10000))).hexdigest()
in l','import random,md5; l=[md5.md5(str(i)).hexdigest() for i
in xrange(10000)]')
dct_str=timeit.Timer('l.has_key(md5.md5(str(random.randrange(10000))).hexdigest())','import
random,md5; l=dict([(md5.md5(str(i)).hexdigest(),None) for i
in xrange(10000)])')
tup_str=timeit.Timer('md5.md5(str(random.randrange(10000))).hexdigest()
in l','import random,md5; l=tuple([md5.md5(str(i)).hexdigest()
for i in xrange(10000)])')

print 'Integer lookup'
r=lst_i.repeat(100,100); print 'list:',min(r),max(r);
r=dct_i.repeat(100,100); print 'dict:',min(r),max(r);
r=tup_i.repeat(100,100); print 'tupl:',min(r),max(r);
print 'String lookup'
r=lst_str.repeat(100,100); print 'list:',min(r),max(r);
r=dct_str.repeat(100,100); print 'dict:',min(r),max(r);
r=tup_str.repeat(100,100); print 'tupl:',min(r),max(r);

[[[Ran on IRIX64 6.5, 24 processors, 12G Memory, 4G Swap, this
code only uses one processor at %100 the full length of the run]]]
Python 2.2.3 (#1, Nov 25 2003, 18:58:21) [C] on irix646-n32
Type "help", "copyright", "credits" or "license" for more
information.
>>> ## working on region in file
/usr/tmp/python-119959673PMu.py...
Integer lookup
list: 0.126830816269 0.160212993622
dict: 0.00362300872803 0.00385618209839
tupl: 0.119297981262 0.161748170853
String lookup
list: 0.142526865005 0.188524961472
dict: 0.00711393356323 0.00760197639465
tupl: 0.143892049789 0.186873912811
>>> 

The results are conclusive, go for dictionaries. But this
surprised me a little, anyone have insight as to why? 

I was also surprised that tuples and lists scored exactly the
same. I was hoping that immutable tuples might earn it some
speed over lists. 

I will eventually need this for testing strings. So the
doubling of speed for strings over integers for dictionaries
is a little alarming. Lists and tuples only saw a modest increase.

Thank you in advance for any clever tricks you suggest.

-Brian