This notebook explores how fast determining if some value is in lists, tuples, sets, and dictionaries.

See simplified conclusion at bottom of notebook.

All Your Ducks In A Row: Data Structures in the Standard Library and Beyond



In [1]:

    
n = 10**7
a = list(range(n))
b = tuple(a)
c = set(a)
d = dict(zip(a, a))



In [2]:

    
5 in a, 5 in b, 5 in c, 5 in d









    Out[2]:





(True, True, True, True)



In [3]:

    
i = n/2



In [4]:

    
%timeit i in a









    



1 loop, best of 3: 730 ms per loop



In [5]:

    
%timeit i in b









    



1 loop, best of 3: 727 ms per loop

Determining if something is in the tuple takes about the same time as determining if something is in the list.



In [6]:

    
%timeit i in c









    



The slowest run took 26.32 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 289 ns per loop



In [7]:

    
730e-3 / 289e-9









    Out[7]:





2525951.5570934257

Determining if something is in the set was about 2.5 million times faster than determining if something is in the list.



In [8]:

    
%timeit i in d









    



The slowest run took 30.09 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 295 ns per loop



In [9]:

    
730e-3 / 295e-9









    Out[9]:





2474576.2711864407

Determining if something is a key in the dictionary was almost 2.5 million times faster than determining if something is in the list.

Simplified Conclusion:

Determining if something is in a set or is a key in a dictionary is smoking fast.

Determining if something is in a list or tuple can be slow.