Search code examples
pythonlistgraphset

Which is faster and why? Set or List?

Lets say that I have a graph and want to see if b in N[a]. Which is the faster implementation and why?

a, b = range(2)
N = [set([b]), set([a,b])]

OR 

N= [[b],[a,b]]

This is obviously oversimplified, but imagine that the graph becomes really dense.

Solution

  • Membership testing in a set is vastly faster, especially for large sets. That is because the set uses a hash function to map to a bucket. Since Python implementations automatically resize that hash table, the speed can be constant (O(1)) no matter the size of the set (assuming the hash function is sufficiently good).

    In contrast, to evaluate whether an object is a member of a list, Python has to compare every single member for equality, i.e. the test is O(n).