Python: list vs. set

In Python we have several types of objects for storing values in a
array-like way: lists, tuples, dictionaries (they are really more like
hash tables) and sets. Lists and sets might look alike but they are
different. Lets do a quick test:


In the above snippet, we can see that iterating over all items in a

list takes just a little longer tan a a set: 8.99us vs 6.87us we are
talking micro-seconds here!

Now, if we look at how long it takes to verify is the list or set
contains an object, we can see the difference: 1.99us vs 140ns. Sets
are an order of magnitude faster!

Why is that? We can think that a python list is like a C linked list.
It’s time complexity when checking for a value is O(n). Sets, on the
other hand, are implemented as hash tables, so the key is hashed and
instantaneously found (or not) with a time complexity of O(1).

For the curious, this is the list object declaration in Include/listobject.h


and this is the set object declaration, in Include/setobject.h


More on python and hash tables here:


One thought on “Python: list vs. set

Leave a Reply

Your email address will not be published. Required fields are marked *