Optimize Python Collections

Choosing the right Python collection for the job is worth more than a hundred micro-optimizations. A list membership test in a loop is O(n squared), while a set membership test is O(n).

The difference between 10 milliseconds and 10 seconds often comes down to one wrong collection choice.

Each Python collection has a different performance profile. Knowing which operation is fast on which type lets you pick the right one before you write the loop.

The big four: cost per operation

This table tells you everything: if your loop does membership tests, use a set or dict, and if it appends and pops from the left, use deque.

If it accesses by index, use a list.

Membership testing: set crushes list

The most common performance mistake is using a list for membership tests inside a loop.

python

ids = list(range(100_000))
target = 99_999
 
# List: scans all elements one by one.
found = target in ids

The list version compares target against each element until it finds a match. Worst case: 100,000 comparisons. For the same test with a set, the result is instant.

python

ids = set(range(100_000))
target = 99_999
 
# Set: one hash computation, one lookup.
found = target in ids

The set version computes target's hash and checks one bucket. One step regardless of size.

For tiny collections, lists can be faster. Under about 50 items, the hash computation overhead of sets outweighs the linear scan cost. Measure with your actual data size.

Dictionary lookups vs list scanning

When you need to find a value by key, a dict is the answer. A list of tuples that you scan linearly is wrong for anything beyond a handful of items.

python

# O(n): scan list of tuples
users_list = [("alice", 30), ("bob", 25), ("carol", 28)]
for name, age in users_list:
    if name == "carol":
        found = age
        break
 
# O(1): dict lookup
users_dict = {"alice": 30, "bob": 25, "carol": 28}
found = users_dict["carol"]

The dict version is a direct hash table lookup. The list version is a linear scan. With 10,000 users, the dict does one operation; the list does up to 10,000.

Deque for queue operations

Using list.pop(0) to remove the first element is O(n) because every remaining element shifts left. Use collections.deque for O(1) operations at both ends.

python

from collections import deque
 
queue = deque(["task1", "task2", "task3"])
queue.append("task4")      # O(1) right side
first = queue.popleft()    # O(1) left side
print(first)               # "task1"

A list would take O(n) for pop(0). A deque is implemented as a doubly-linked list of blocks, optimized for both-end operations.

Sorting: list.sort vs sorted

list.sort() sorts in place and is slightly faster than sorted() because it does not allocate a new list. Use sorted() when you need the original unsorted list preserved.

python

data = [5, 2, 9, 1, 5]
 
# In-place: modifies data, returns None.
data.sort()
 
# New list: original preserved, returns new list.
sorted_data = sorted(data)

For large lists, the key parameter matters more than the sort method. Pass a key function to avoid expensive comparisons:

python

# Sort by a computed value, computed once per element.
words.sort(key=len)

Counting and grouping

collections.Counter is a specialized dict optimized for counting. It is faster and cleaner than a manual loop with a regular dict.

python

from collections import Counter
 
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
counts = Counter(words)
print(counts.most_common(2))
# [("apple", 3), ("banana", 2)]

Counter is implemented in Python but uses C-optimized dict operations internally. For grouping items by a key, use itertools.groupby after sorting, or collections.defaultdict for unsorted data.

python

from collections import defaultdict
 
groups = defaultdict(list)
for item in data:
    groups[item.category].append(item)

When the overhead of the right structure beats the wrong one

Sets and dicts have higher memory overhead than lists. Each set entry stores a hash value and a pointer, and the hash table itself is kept sparse to keep lookups fast. A set of 100,000 integers uses about 4 MB; a list uses about 800 KB for the same integers' pointers.

If your collection is small and you never do membership tests, the list's lower overhead wins. If you do membership tests, the set's O(1) lookup wins at any non-trivial size. The break-even point depends on your data, but for membership tests it is usually around 20 to 50 items.

The article on common Python performance bottlenecks covers how data structure choices interact with other patterns. For profiling which collection operations dominate your runtime, the article on cProfile walks through the measurement workflow.