12.13 Performance

Membership testing: a list scans linearly, a set jumps straight to the hash slot.

Time Complexity

Memory Usage

A set typically uses more memory per element than a list or tuple (see 12.3 Internal Representation) — the hash table needs extra space to keep lookups fast and collisions rare. This is the trade-off for O(1) membership testing.

Membership Testing

The headline performance case: for repeated “is this in my collection?” checks, converting to a set first pays for itself almost immediately on any non-trivial collection size.

>>> import timeit
>>> big_list = list(range(10000))
>>> big_set = set(big_list)
>>> timeit.timeit(lambda: 9999 in big_list, number=1000)
0.08375     # seconds -- illustrative, will vary by machine
>>> timeit.timeit(lambda: 9999 in big_set, number=1000)
0.00005

Quick Interview Answer

“Membership testing is the number one reason to pick a set: x in s is O(1) average because it’s a direct hash lookup, versus O(n) for a list, which has to scan element by element until it finds a match or runs out. That advantage compounds with every repeated check, which is why converting a list to a set once, up front, before doing thousands of in checks against it, is one of the most reliable performance wins in ordinary Python code. The trade-off is memory: a set’s hash table reserves extra space to keep collisions rare, so it typically costs more per element than an equivalent list or tuple — a worthwhile trade whenever membership testing happens more than a handful of times.”

Common Mistakes

• Repeatedly checking x in my_list inside a loop against a list that never changes, instead of converting it to a set once beforehand (see 12.18 Best Practices).
• Assuming set operations like | and & are also O(1) — they’re O(len(s) + len(t)), since both sets must be scanned once to compute the result.
• Choosing a set purely for memory efficiency — for pure storage with no membership testing, a list or tuple is typically the more compact choice.