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”
Great post. This is the computing I love.