Choosing a Container

Most performance bugs in ordinary code come from the wrong container, not a slow algorithm: a list searched inside a loop, a dictionary asked for a range, a scan repeated to find the smallest item. The fix is a habit rather than a trick. Write down what the code asks of the data and how often, and let that choose the structure.

This topic is that habit as a decision guide, closing the chapter. It is also the question most coding interviews are really asking underneath the puzzle: given these operations, which structure makes the hot one cheap?

Start From the Operations

List what the code asks of its data. Is x present? What goes with key k? What is the smallest item? Everything between a and b? The items in the order they arrived? How many of each? Then mark which of those questions run inside a loop, and at what n.

The operation that runs most often, at the largest n, decides the structure. Every other operation only has to be tolerable. A structure chosen for the operation that runs once at start-up, while the hot one scans, is the most common way a correct program ends up slow.

Membership and Lookup

"Is it there" and "what goes with it" belong to a set or a dictionary (see Hash Tables): one probe instead of a scan. The two versions of the code look almost identical, which is why the wrong one survives review.

unique = []
for x in ids:
    if x not in unique:     # a scan of the list so far
        unique.append(x)
seen, unique = set(), []
for x in ids:
    if x not in seen:       # one probe
        seen.add(x)
        unique.append(x)

Both loops keep the first occurrence of each id in its original order. The first checks each id against the list built so far, which is a scan; for 100,000 distinct ids that is about five billion comparisons. The second checks a set, one probe per id. On CPython 3.15, the list version took 1.8 seconds for only 20,000 ids and grows with the square of n, while the set version took under 8 milliseconds for 100,000.

Three Kinds of Order

Insertion order, sorted order and priority order are three different promises. A list, a deque and a Python dictionary keep insertion order. A sorted list maintained with binary search (Chapter 7), a balanced tree (Chapter 6) and a B-tree (Chapter 6) keep sorted order. A heap (Chapter 6) keeps priority order: it always knows its smallest item and nothing more.

Keeping the order you need is cheaper than restoring it. Finding the smallest of a million items after every insert costs a million comparisons each time with a scan, and one look with a heap, whose insert costs about 20 comparisons. On CPython 3.15, an append followed by a minimum over a million-item list took about 10 milliseconds; a heap push followed by a look at its top took under half a microsecond.

Ranges, Prefixes and Neighbours

"Between a and b", "starts with" and "the next one after x" all need keys kept in order. A hash table cannot answer any of them, because it scattered the keys on purpose. A sorted structure answers each with one search and a short walk from the place the search lands.

Python ships no sorted map. A sorted list maintained with the standard binary-search module serves while inserts are modest: each insert is one search and one block move of pointers (see Arrays and Dynamic Arrays). On CPython 3.15 an insert took about 1 microsecond into 10,000 items, about 5 into 50,000, and about 110 into a million. Past that point a tree-shaped structure is the answer: the third-party sortedcontainers package, or a database index (Chapter 6).

Duplicates and Counts

A set silently drops duplicates. A list keeps them, in order. A dictionary of counts, such as the Counter in the standard collections module, keeps how many of each. These are three different answers to "what did we see", and the right one depends on whether repetition carries meaning.

Replacing a list with a set where duplicates matter is a correctness bug, not a performance fix. Two orders for the same book, two identical log lines, two votes from the same branch: no test that uses unique data will catch the change, and production data is never unique.

The Cost of the Wrong Choice

The wrong container is invisible at a hundred items and becomes the page that times out at a million (Chapter 1). It is a memory decision too (Chapter 1). Measured on CPython 3.15, a million integers cost 8 megabytes as a packed array, about 40 as a list, about 66 as a set, and about 106 as a dictionary mapping them to a million other integers.

The table below is the chapter on one page. For membership, a list or deque scans in O(n), a set answers in O(1) on average, a heap also has to scan, a sorted list or a balanced tree takes O(log n), and a trie, the prefix tree of Chapter 6, takes time proportional to the key's length. For the smallest item, a heap and a sorted list answer at once, a balanced tree walks down its left edge in O(log n), a trie walks down its first branch, and the rest scan.

Adding an item is O(1) at the end of a list and at either end of a deque, O(1) on average for a set, O(log n) for a heap or a balanced tree, proportional to the key's length for a trie, and a search plus an O(n) shift for a sorted list. Ranges and "the next key" need a sorted list or a balanced tree, which find the start in O(log n) and then walk the k items in the answer; a trie answers prefixes only, and a set or a heap cannot answer them at all.