CPython Container Internals: list, dict, set, heapq, sorted and bisect

A librarian gets a box of new books each week. If she buys a shelf exactly as long as her books, every new book means a new shelf and a move of every old book. So she buys a shelf longer than she needs and fills it slowly. Python's built-in containers are full of choices like this one. This lesson opens them up. Every claim is shown by counting steps, never by a stopwatch.

Learning Objectives

After this lesson, you will be able to:

Explain why a list over-allocates, simulate its growth with different rules, and show that a proportional rule gives O(1) amortized appends while a fixed step does not
State the hash and equality contract a dict depends on, and show how a key that changes after insertion gets lost
Say what insertion order guarantees in a dict, and what happens to it on update, delete and re-insert
Explain why a set prints in an order you cannot rely on, and why a tuple is hashable only if its items are
Describe a deque as a chain of blocks and a heapq heap as a plain list, and count the comparisons of heapify, push and pop
Explain runs, binary insertion, merging and galloping in Timsort, and show its adaptivity and stability with a comparison counter
Say what interning and the small-integer cache promise (little) and use bisect with a clear idea of where its time goes

Prerequisites

Before You Start

Review

This lesson builds on Build a Hash Table, Sorting Algorithms and Asymptotics and Amortized Analysis. We do not repeat them. We ask a different question: what does CPython promise, what does it merely happen to do, and where can you get hurt?

"CPython" is the standard Python interpreter, written in C. A language promise is behavior the documentation guarantees, such as dict order. An implementation detail is behavior CPython has today but may change, such as a growth ratio. We mark each one, and we give no numbers for details. The lesson on how CPython works covers bytecode, objects and the garbage collector, so we leave those out.

#The Picture Under Every Container

Every value in Python is an object that lives somewhere in memory. A container does not hold values. It holds pointers, also called references: small addresses that say where each object lives. A list of a million strings is a million pointers in a row. The strings sit elsewhere.

Two facts follow from this. First, a[i] is one step, because the address is the start of the row plus i times the size of a pointer. Second, copying a container copies pointers, not objects.

pythonrunnable cell

rows = [[1], [2]]
copy = rows[:]            # a new row of pointers
copy[0].append(9)         # but both rows still point at the same inner list
print(rows)
# Output:
# [[1, 9], [2]]

Keep this picture. A list is a row of pointers, a dict is a table of pointers, and a heap is a row of pointers with a rule about their order. Every cost in this lesson is a cost of moving or comparing pointers.

#list: A Row of Pointers That Over-Allocates

A list stores its pointers in one block of memory. The block has a capacity, the number of pointers it has room for, and a length, the number in use. When you append to a full list, CPython asks for a bigger block, copies the pointers over, and frees the old one. That step is a reallocation.

Now the key choice. Make the new block exactly one slot bigger and every append reallocates. So CPython over-allocates: it asks for more room than it needs. Here is a hand trace of a model that doubles the capacity when full. It starts with capacity 0.

Append number	Length before	Capacity before	Reallocate?	Pointers copied
1	0	0	yes, to 1	0
2	1	1	yes, to 2	1
3	2	2	yes, to 4	2
4	3	4	no	0
5	4	4	yes, to 8	4

Appends 6, 7 and 8 fit without any copy. The next copy comes at append 9. Copies get rarer as the list grows. Before we count them, make a prediction about a different rule.

What Do You Think?

A model list adds room for 8 more pointers each time it is full. You compare building a list of 10,000 items with building one of 100,000 items. About how does the copying work per append change?

The cell below simulates four growth rules. It builds no real list. It only counts how many pointers the reallocations copy.

pythonrunnable cell

def simulate_appends(n, grow):
    """Return (reallocations, copies) for n appends. grow(capacity) gives the new capacity."""
    capacity, size, reallocs, copies = 0, 0, 0, 0
    for _ in range(n):
        if size == capacity:
            capacity = grow(capacity)
            copies += size                  # a full block is copied into the bigger one
            reallocs += 1
        size += 1
    return reallocs, copies


rules = {
    "add 8 slots": lambda c: c + 8,
    "times 1.25": lambda c: max(c + 1, int(c * 1.25)),
    "times 1.5": lambda c: max(c + 1, int(c * 1.5)),
    "times 2": lambda c: max(1, c * 2),
}
for n in (1_000, 100_000):
    for name, grow in rules.items():
        reallocs, copies = simulate_appends(n, grow)
        print(f"n={n:>7} {name:<12} reallocations={reallocs:>6} copies per append={copies / n:.2f}")
# Output:
# n=   1000 add 8 slots  reallocations=   125 copies per append=62.00
# n=   1000 times 1.25   reallocations=    31 copies per append=4.49
# n=   1000 times 1.5    reallocations=    18 copies per append=2.14
# n=   1000 times 2      reallocations=    11 copies per append=1.02
# n= 100000 add 8 slots  reallocations= 12500 copies per append=6249.50
# n= 100000 times 1.25   reallocations=    52 copies per append=4.82
# n= 100000 times 1.5    reallocations=    30 copies per append=2.77
# n= 100000 times 2      reallocations=    18 copies per append=1.31

With a fixed step the copies per append grow with n: 62 at a thousand items, 6,249 at a hundred thousand. With a proportional rule they stay flat. Here is why. Say each growth multiplies the capacity by r, a number above 1. The copy sizes are at most n, then n/r, then n/r², and so on. That geometric series sums to at most n times r/(r-1), so the copies per append never pass r/(r-1), whatever n is. For r = 2 the bound is 2, and for r = 1.25 it is 5, which fits the 4.82 above.

With a fixed step the copy sizes are 8, 16, 24 and so on. They add up to about n²/16, which is O(n²) for n appends.

There is a price. After a growth the capacity can be r times the length, so up to (r-1) times the length is unused room. A big r wastes memory and a small r copies more often. CPython uses a small ratio, well under 2, and the exact rule is an implementation detail that has changed between versions.

A real allocator can sometimes extend a block in place without copying, so our counts are the worst case. The next cell checks the real list for the same behavior without printing any size.

pythonrunnable cell

import sys


def allocation_changes(n):
    """How many times does the size of a list's block change over n appends?"""
    items, last, changes = [], sys.getsizeof([]), 0
    for i in range(n):
        items.append(i)
        size = sys.getsizeof(items)
        if size != last:
            changes += 1
            last = size
    return changes


few, many = allocation_changes(1_000), allocation_changes(100_000)
print("changes happen on only a few appends:", many < 100_000 // 100)
print("100 times more appends, fewer than 3 times more changes:", many < 3 * few)
# Output:
# changes happen on only a few appends: True
# 100 times more appends, fewer than 3 times more changes: True

The number of changes grows with the logarithm of n, which is the signature of a proportional rule. A list also does not give room back the moment you remove an item. It shrinks only when it is far below capacity, so a loop that appends and pops near a boundary does not reallocate each time.

The costs, with reasons. append is O(1) amortized, because of the geometric series above, and one single append can cost O(n). a[i] is O(1) by the address arithmetic. insert(i, x) and pop(i) are O(n - i), because every pointer after position i must shift by one. x in a is O(n), because it compares each pointer's object in turn. The space is O(n) pointers plus the spare room.

#tuple: The Same Row, With No Spare Room

A tuple is also a row of pointers, but its length is fixed when it is made. It has no spare room and no append, so it needs no capacity field and no reallocation. That makes it smaller than a list of the same items and cheap to build.

"Immutable" has a precise meaning here: the tuple's slots can never point somewhere else. It does not mean the objects behind the pointers are frozen.

pythonrunnable cell

t = (1, [2, 3])
t[1].append(4)                # allowed: the slot still points at the same list
print(t)
try:
    hash(t)
except TypeError as error:
    print("TypeError:", error)
print(hash((1, 2)) == hash((1, 2)))
# Output:
# (1, [2, 3, 4])
# TypeError: unhashable type: 'list'
# True

A tuple's hash is computed from the hashes of its items, in order. So (1, 2) is hashable and (1, [2, 3]) is not, because the list inside has no hash. A tuple works as a dict key only when everything inside it is hashable. Hashing costs O(length). Comparison goes item by item and stops at the first difference, which matters in the heap section.

#dict: Order, Equality and the Hashing Contract

Build a Hash Table showed the compact layout: a small table of positions, and an entries array that holds each key, value and stored hash in insertion order. We take that picture as known. Three consequences of it are new here.

Order is a language promise. Since Python 3.7, a dict iterates in insertion order. Updating an existing key keeps its place. Deleting a key and inserting it again puts it at the end. Equality between dicts ignores order. The next cell shows all three, and a fourth rule: adding a key during iteration is an error, because the iteration walks the entries array by position and the array may be rebuilt.

pythonrunnable cell

d = {}
d["a"], d["b"], d["c"] = 1, 2, 3
d["a"] = 10                      # update: the key keeps its place
print(list(d))
del d["a"]
d["a"] = 11                      # delete, then insert again: the key goes to the end
print(list(d))
print({1: "x", 2: "y"} == {2: "y", 1: "x"})
try:
    for key in d:
        d[key + "!"] = 0
except RuntimeError as error:
    print("RuntimeError:", error)
# Output:
# ['a', 'b', 'c']
# ['b', 'c', 'a']
# True
# RuntimeError: dictionary changed size during iteration

A lookup follows a fixed recipe. CPython hashes the key once and goes to a slot. For each candidate entry it asks three things in order. Is it the very same object? Then it is a hit, and == is never called. If not, does the stored hash match the key's hash? If not, skip it with no == call. If it matches, call ==, and a true answer is a hit. Otherwise it probes on.

Two rules come out of that recipe. If a == b then hash(a) must equal hash(b), or equal keys land in different places and the dict stores both. And a key's hash must not change while it is in the dict. This is why list, dict and set are unhashable: they compare by contents and can change, so no stable hash could obey the first rule.

The cell counts == calls to show the recipe. It also shows a famous exception, a key that is not equal to itself.

pythonrunnable cell

class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return hash(self.v)

    def __eq__(self, other):
        Key.eq_calls += 1
        return self.v == other.v


first = Key(5)
table = {first: "five"}


def eq_calls_for(probe):
    Key.eq_calls = 0
    table.get(probe)
    return Key.eq_calls


print("the same object:", eq_calls_for(first))
print("an equal object:", eq_calls_for(Key(5)))
print("a different hash:", eq_calls_for(Key(6)))
nan = float("nan")
print({nan: 1}[nan], float("nan") in {nan: 1})
# Output:
# the same object: 0
# an equal object: 1
# a different hash: 0
# 1 False

Not-a-number is never equal to itself, yet {nan: 1}[nan] works, because the identity check comes before ==. A different nan object fails. The same shortcut explains why interning strings helps, which we return to below.

Now predict what happens when a key changes after it is stored.

What Do You Think?

A class hashes and compares by its field x. class Point: def __init__(self, x): self.x = x def __hash__(self): return hash(self.x) def __eq__(self, other): return self.x == other.x p = Point(1) seen = {p: "here"} p.x = 2 print(p in seen)

The cost of a dict, with reasons. Lookup, insert and delete are O(1) on average, because the hash spreads keys and the table stays under about two thirds full. In the worst case they are O(n), when many keys share a slot path. CPython randomizes str and bytes hashes for each process, so an attacker cannot easily pick colliding keys, and you must never print or save hash("text"). Space is O(n).

Deleting never shrinks a dict by itself. It leaves a hole in the entries array. The next insert that finds the array full triggers a rebuild sized for the keys that are left. You will model this in the last problem of the Try It section.

#set: A Dict Without Values

A set uses the same hashing recipe and the same contract, with entries that hold only a key. Its costs match a dict: O(1) on average for add, remove and in, and O(n) in the worst case.

Set operations have costs worth knowing. a & b looks each item of the smaller set up in the larger one, so it costs O(min(len a, len b)) on average. a | b costs O(len a + len b). a - b costs O(len a).

A set is not ordered, and what it prints is an accident of slot positions.

pythonrunnable cell

print({3, 1, 2})
print({8, 1})
print(frozenset({1, 2}) == frozenset({2, 1}), {frozenset({1, 2}): "ok"}[frozenset({2, 1})])
# Output:
# {1, 2, 3}
# {8, 1}
# True ok

Small integers hash to themselves, and a small table puts each in the slot given by the remainder after division by the table size. So 3, 1, 2 sit in slots 3, 1 and 2 and print in slot order, which looks sorted. The 8 goes to slot 0 of an 8-slot table, so it prints first. Never rely on this order. A frozenset cannot change, so it can be hashed and used as a key.

#deque: A Chain of Blocks

A collections.deque is a doubly linked chain of fixed-size blocks. Each block holds many pointers, and the chain keeps a pointer to the first and last block. Adding or removing at either end touches one block, so it is O(1). The block size is an implementation detail.

Why not a list? list.pop(0) shifts every remaining pointer one slot left. Taking all n items off the front this way costs (n-1) + (n-2) + ... + 0 = n(n-1)/2 moves, which is O(n²). For n = 4 that is 3 + 2 + 1 + 0 = 6 moves. A deque does none of them.

What a deque gives up is cheap indexing. To reach item i it walks the chain from the nearer end, so d[i] is O(n) in the middle, and there are no slices.

pythonrunnable cell

from collections import deque

window = deque(range(5), maxlen=3)      # a full deque drops from the other end
print(window)
d = deque([1, 2, 3])
d.rotate(1)
d.appendleft(0)
print(d, d[0], d[-1])
try:
    d[1:3]
except TypeError as error:
    print("TypeError:", error)
# Output:
# deque([2, 3, 4], maxlen=3)
# deque([0, 3, 1, 2]) 0 2
# TypeError: sequence index must be integer, not 'slice'

With maxlen a deque becomes a sliding window: appending to a full one drops the item at the opposite end, in O(1). That is a good fit for "the last 100 loss values" in a training loop. Space is O(n) pointers plus a little per block.

#heapq: A Heap Is Just a List

The heapq module has no heap class. A heap is an ordinary list that obeys one rule, the heap invariant: for every index k, heap[k] <= heap[2k + 1] and heap[k] <= heap[2k + 2]. Read the list as a tree where the children of index k sit at 2k + 1 and 2k + 2.

No child is smaller than its parent, so heap[0] is the smallest item. The list is not sorted.

Push. Append the item at the end, then sift up: swap it with its parent while it is smaller. The tree has about log n levels, so a push is O(log n) in the worst case.

Pop. Take heap[0], move the last item to the root, and fix the order downward. CPython does this in a clever way. The moved item is usually large, so CPython walks it all the way down to a leaf, always choosing the smaller child without comparing against the moving item, and then sifts it back up. That saves comparisons on average. A pop is O(log n).

Heapify. To build a heap from n items, sift down each parent from the last one back to the root. Trace it on [7, 3, 9, 1]. The last parent is index 1, the item 3, and its child holds 1. That is smaller, so swap: [7, 1, 9, 3].

Now index 0, the item 7, has children 1 and 9. Swap with the smaller one: [1, 7, 9, 3]. The 7 now sits at index 1 with a smaller child 3, so swap again: [1, 3, 9, 7]. Done, and the list is not sorted.

Why is this O(n) and not O(n log n)? Half the nodes are leaves and move zero levels. A quarter move at most one level, an eighth at most two. The total moves are n times (1/4 + 2/8 + 3/16 + ...), a series that adds up to n, so the work is O(n), at most about 2n comparisons. Now try one yourself.

What Do You Think?

What does this print? import heapq h = [5, 3, 8, 1, 9, 2] heapq.heapify(h) print(h)

The next cell counts comparisons for each operation on 10,000 items. Only facts that do not depend on the version are printed.

pythonrunnable cell

import heapq
import math
import random


class Counted:
    """A number that counts every < it takes part in."""
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


def count(action):
    Counted.compares = 0
    action()
    return Counted.compares


n = 10_000
random.seed(5)
values = random.sample(range(10 * n), n)
objects = [Counted(v) for v in values]
print("heapify uses fewer than 2n comparisons:", count(lambda: heapq.heapify(objects)) < 2 * n)

heap = []
print("n ascending pushes:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in range(n)]))
heap = []
print("n descending pushes, more than 5n:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in range(n, 0, -1)]) > 5 * n)
heap = []
print("n random pushes, fewer than 3n:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in values]) < 3 * n)
print("n pops, fewer than n log2 n:", count(lambda: [heapq.heappop(heap) for _ in range(n)]) < n * math.log2(n))
# Output:
# heapify uses fewer than 2n comparisons: True
# n ascending pushes: 9999
# n descending pushes, more than 5n: True
# n random pushes, fewer than 3n: True
# n pops, fewer than n log2 n: True

Ascending pushes cost one comparison each, because every new item is larger than its parent. Descending pushes are the worst case, since each new item climbs to the root. A random push costs a small constant on average, because most items stay near the bottom. That average is O(1), while the worst case is O(log n).

Popping all n items gives them in order, which is heapsort: O(n log n) time. heapq offers only a min-heap, so for a max-heap push negated numbers. heapq.nsmallest(k, items) and nlargest keep a heap of size k, so they cost O(n log k) time and O(k) space. If k is close to n, sorting is simpler.

A heap is not a search structure. x in heap is O(n), because the invariant says nothing about where x is. If you need the items in order, pop them or sort a copy.

#sorted and list.sort: Timsort in Detail

The earlier lesson told the story in one paragraph. Here are the parts, with their reasons.

Find runs. A run is a stretch already in order, rising or strictly falling. The scan reads the list once and reverses each falling run in place. The strictness matters: reversing equal items would swap them, and the sort must be stable. A single run of n items costs n - 1 comparisons to find.

Extend short runs. A run shorter than a small minimum, a few dozen items, is extended by binary insertion: take the next item, find its place in the sorted run with a binary search, and insert it. That uses O(log k) comparisons per item but still O(k) moves, so it pays off when comparing is the expensive part.

Merge runs. The runs wait on a stack, and CPython merges neighbors by a rule that keeps merges balanced, so each item takes part in only O(log r) merges for r runs. Since version 3.11 the rule is called powersort. A merge copies only the smaller of the two runs into a temporary array, so the extra space is at most half the list, which is O(n).

Gallop. Before merging runs A and B, Timsort searches for where the first item of B belongs in A, and where the last item of A belongs in B. Everything outside that window is already in place and is skipped.

Inside the merge, if one run wins several times in a row, the merge switches to galloping: it probes 1, 2, 4, 8 items ahead to find where the streak ends, then does a binary search. Skipping a streak of k items costs about log k comparisons, not k.

What it proves. The worst case is O(n log n) comparisons, and no comparison sort can do better on all inputs, since n items have n! orders and each comparison halves at best. The best case is O(n), for one run. In between, the cost depends on how many runs there are, roughly n log r. That is what adaptive means. Try a prediction before the numbers.

What Do You Think?

A list has 10,000 items in rising order, followed by 5 extra items that belong somewhere inside that run. About how many comparisons does sorted need?

pythonrunnable cell

import math
import random


class Counted:
    """A number that counts every < it takes part in."""
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


def sort_cost(values):
    Counted.compares = 0
    sorted(Counted(v) for v in values)
    return Counted.compares


n = 10_000
ordered = list(range(n))
random.seed(1)
shuffled = ordered[:]
random.shuffle(shuffled)

print("one rising run:", sort_cost(ordered), "| n - 1 =", n - 1)
print("one falling run:", sort_cost(ordered[::-1]))
print("shuffled, below n log2 n:", sort_cost(shuffled) < n * math.log2(n))
print("shuffled, above 5n:", sort_cost(shuffled) > 5 * n)

blocks = [list(range(i * 1_000, (i + 1) * 1_000)) for i in range(10)]
random.shuffle(blocks)
flat = [x for block in blocks for x in block]
print("10 sorted blocks in random order, below 1.1 n:", sort_cost(flat) < 1.1 * n)

stragglers = list(range(0, 20_000, 2)) + [5, 7, 9, 10_001, 15_001]
extra = sort_cost(stragglers) - (len(stragglers) - 1)
print("a long run plus 5 stragglers, extra comparisons under 200:", 0 < extra < 200)
# Output:
# one rising run: 9999 | n - 1 = 9999
# one falling run: 9999
# shuffled, below n log2 n: True
# shuffled, above 5n: True
# 10 sorted blocks in random order, below 1.1 n: True
# a long run plus 5 stragglers, extra comparisons under 200: True

Ten sorted blocks in random order cost barely more than one pass, because galloping finds that each block fits whole before or after its neighbor. The exact counts for a shuffled list change between Python versions, so the cell tests only bounds.

Stability needs one more look, because reverse=True has a subtle rule. CPython does not sort and then flip the list, which would reverse ties. It reverses the list, sorts, and reverses back, so ties keep their input order. One more documented detail: while a sort runs, the list appears empty to any code that looks at it.

pythonrunnable cell

rows = [("b", 1), ("a", 1), ("c", 0), ("d", 1)]
by_score = lambda row: row[1]
print(sorted(rows, key=by_score))
print(sorted(rows, key=by_score, reverse=True))
print(sorted(rows, key=by_score)[::-1])

items = [3, 1, 2]
seen = []
items.sort(key=lambda x: seen.append(len(items)) or x)
print(seen, items)
# Output:
# [('c', 0), ('b', 1), ('a', 1), ('d', 1)]
# [('b', 1), ('a', 1), ('d', 1), ('c', 0)]
# [('d', 1), ('a', 1), ('b', 1), ('c', 0)]
# [0, 0, 0] [1, 2, 3]

The second line keeps b, a, d in input order. The third line, which flips the sorted list, reverses the ties and breaks stability. Sorting needs only <, so define __lt__ on your class and nothing else. The key function runs once per item. Total cost: O(n log n) time worst case, O(n) when the data is one run, and O(n) extra space.

#Interning and Small Integers: What You May Rely On

Interning means keeping one shared copy of a value so equal values are the same object. CPython keeps ready-made objects for a small range of integers near zero, and it interns many strings, such as names and short constants that look like identifiers. These are implementation details. Two integers or strings that are equal may or may not be the same object, and the answer can differ between versions and between a constant and a computed value.

So the rule is simple: compare values with ==, and use is only for None and for sentinels you made yourself. There is one documented tool. sys.intern(s) returns the one shared copy of a string, and that part is a promise.

pythonrunnable cell

import sys

built = "".join(["he", "llo"])
literal = "hello"
print(built == literal)
print(sys.intern(built) is sys.intern(literal))
# Output:
# True
# True

Why would you intern on purpose? Look back at the lookup recipe. When the lookup key and the stored key are the same object, the dict stops at the identity check and never compares the characters. A program that builds millions of dict lookups from a few repeated long strings, such as column names read from a file, can intern them once. For ordinary code, do not bother.

#bisect: Binary Search on a List

The bisect module searches a sorted list in O(log n) comparisons. bisect_left(a, x) returns the first position where x could go while keeping order, so everything before it is smaller than x. bisect_right returns the position after any items equal to x. The module does not check that the list is sorted, and on unsorted data it returns nonsense without any error.

The cell counts comparisons, using the key= argument (Python 3.10 and later) to wrap each probed item in a counting class.

pythonrunnable cell

import bisect


class Counted:
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


for n in (1_000, 1_000_000):
    data = list(range(n))
    Counted.compares = 0
    spot = bisect.bisect_left(data, Counted(777), key=Counted)
    print(n, spot, Counted.compares)

a = [1, 2, 2, 2, 3]
print(bisect.bisect_left(a, 2), bisect.bisect_right(a, 2))
bisect.insort(a, 2)            # insort means insort_right: the new 2 goes after the old ones
print(a)
# Output:
# 1000 777 10
# 1000000 777 20
# 1 4
# [1, 2, 2, 2, 2, 3]

A thousand times more items costs ten more comparisons. The count of items equal to x in a sorted list is bisect_right(a, x) - bisect_left(a, x), in O(log n).

insort is where people get surprised. Finding the place costs O(log n) comparisons, but inserting into a list shifts every later pointer, so insort costs O(n) in all. Keeping a list sorted with insort is fine for thousands of items and slow for millions. If you only ever need the smallest item, a heap does the job in O(log n). If you need order plus fast inserts at large scale, you need a balanced tree, which the lesson on balanced trees builds.

#Choosing: Costs with Reasons

Costs are for CPython, "avg" means average case, and "amort." means amortized.

You need	Use	Cost	Why
Add or remove at the end	`list`	O(1) amort.	spare room, and no pointer after it moves
Add or remove at the front	`deque`	O(1)	a chain of blocks, no shifting
Is this item present?	`set` or `dict`	O(1) avg	hash to a slot, then the lookup recipe
Items in the order they arrived, with lookup	`dict`	O(1) avg	the entries array keeps the order
The smallest item again and again	`heapq`	O(log n) per pop	heap invariant in a list
The k best of a stream	`heapq.nlargest`	O(n log k)	a heap of size k
Sort once	`sorted`	O(n log n), O(n) if mostly ordered	Timsort finds runs
A sorted list with a few inserts	`bisect.insort`	O(n) per insert	search is log n, but the shift is n
How many items lie in a range of a sorted list	two `bisect` calls	O(log n)	two binary searches

When not to use each. Do not use a list as a queue for large n, since pop(0) is O(n). Do not use a deque when you index into the middle. Do not use a heap to test membership.

Do not use insort to build a million-item sorted list one item at a time: append everything and sort once, which is O(n log n) rather than O(n²).

#Where These Show Up

CPython is built from these containers. Module globals and the attributes of most objects live in dicts, so attribute lookup is a hash lookup. The asyncio event loop keeps its scheduled callbacks in a heapq heap, so the next timer is always at the front.

In machine learning code, a deque(maxlen=k) is a natural window of recent losses, heapq.nlargest picks the top-k predictions without sorting the whole output, and bisect maps a score to a bucket in a sorted list of thresholds. These are examples, not a full list.

#Common Mistakes

Watch Out

Changing a key's hash after it is in a dict or set

Fix: Hash only on fields that never change after the object is stored, or use an immutable type such as a tuple or a frozen dataclass.

pythonrunnable cell

class Point:
    def __init__(self, x):
        self.x = x

    def __hash__(self):
        return hash(self.x)

    def __eq__(self, other):
        return self.x == other.x


p = Point(1)
seen = {p}
p.x = 2
print(Point(1) in seen, Point(2) in seen, p in seen, len(seen))
# Output:
# False False False 1

The entry sits in the slot for hash 1 with the old stored hash. A lookup with the old value finds the slot, but == now says the stored point has x = 2, not 1. A lookup with the new value goes to a different slot. The entry still counts in len and still shows up in a loop, but no lookup finds it, so you cannot remove it either.

Watch Out

Pushing pairs that can tie onto a heap

Fix: Push (priority, counter, item), where the counter is a number that only goes up, so a tie never reaches the item.

pythonrunnable cell

import heapq
from itertools import count

heap = []
heapq.heappush(heap, (1, {"job": "a"}))
try:
    heapq.heappush(heap, (1, {"job": "b"}))
except TypeError as error:
    print("TypeError:", error)

ticket = count()
safe = []
heapq.heappush(safe, (1, next(ticket), {"job": "a"}))
heapq.heappush(safe, (1, next(ticket), {"job": "b"}))
print([entry[2]["job"] for entry in (heapq.heappop(safe), heapq.heappop(safe))])
# Output:
# TypeError: '<' not supported between instances of 'dict' and 'dict'
# ['a', 'b']

Tuples compare item by item and stop at the first difference. When the priorities tie, Python moves on to compare the dicts, which cannot be ordered. The counter breaks every tie, and as a bonus it makes equal priorities come out in the order they were pushed.

#Try It

Work the ladder in order. Rung 1 simulates list growth, rung 2 builds a heap by hand with a comparison counter, rung 3 keeps the k best items of a stream, rung 4 merges with galloping, and rung 5 builds a small insertion-ordered dict. Every rung has a counter, so you can see the cost, and the last few include inputs that try to break your code.

pythonplayground.py · Pyodide

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

import heapq
import random

# Rung 1: model a list that over-allocates. Time O(n) for n appends, space O(1).
# grow(capacity) returns the new capacity. Count reallocations and items copied.
# State in a comment why "times 2" copies O(1) items per append, but "add 8" does not.
def simulate_appends(n, grow):
  # TODO: when size == capacity, call grow, add size to copies, add 1 to reallocs.
  # Raise ValueError if the new capacity is not bigger than the old one. Return (reallocs, copies).
  pass

double = lambda c: max(1, c * 2)
add_eight = lambda c: c + 8
print(simulate_appends(1000, double), simulate_appends(1000, add_eight))
print(simulate_appends(0, double), simulate_appends(1, double))
print(simulate_appends(100_000, double)[1] < 2 * 100_000, simulate_appends(100_000, add_eight)[1] > 1000 * 100_000)
# Expected: (11, 1023) (125, 62000)
#           (0, 0) (1, 0)
#           True True

# Rung 2: heapify by hand. counter[0] counts every comparison between two items.
# Time O(n): half the nodes are leaves, a quarter move one level, and so on.
def sift_down(a, i, n, counter):
  # TODO: while i has a child, pick the smaller child (count 1 comparison if there are two),
  # then compare it with a[i] (count 1). Swap and move down if the child is smaller, else stop.
  pass

def my_heapify(a, counter):
  # TODO: sift down every parent, from index len(a) // 2 - 1 back to 0
  pass

def is_heap(a):
  return all(a[(i - 1) // 2] <= a[i] for i in range(1, len(a)))

for data in ([9, 4, 7, 1, 8, 2], list(range(10, 0, -1)), [5] * 8, [], [3]):
  a, c = list(data), [0]
  my_heapify(a, c)
  print(is_heap(a), c[0], a)
random.seed(3)
a, c = random.sample(range(10_000), 5000), [0]
my_heapify(a, c)
print(is_heap(a), c[0] < 2 * 5000)
# Expected: True 7 [1, 4, 2, 9, 8, 7]
#           True 14 [1, 2, 4, 3, 6, 5, 8, 10, 7, 9]
#           True 7 [5, 5, 5, 5, 5, 5, 5, 5]
#           True 0 []
#           True 0 [3]
#           True True

# Rung 3: the k best (highest score) pairs of a stream, using a heap of size k.
# Ties keep the earlier pair. Time O(n log k), space O(k). stats[0] counts heap pushes and replaces.
def top_k(stream, k, stats):
  # TODO: keep (score, -position, pair) entries in a min-heap, so the root is the weakest kept pair.
  # Push while len(heap) < k. After that, replace the root only if the new entry is bigger.
  # Return the pairs from best to worst. Watch k = 0 and k bigger than the stream.
  pass

def reference(stream, k):
  return sorted(stream, key=lambda p: p[0], reverse=True)[:k]

pairs = [(5, "a"), (9, "b"), (5, "c"), (9, "d"), (1, "e"), (5, "f")]
for k in (0, 1, 3, 10):
  s = [0]
  got = top_k(pairs, k, s)
  print(k, got == reference(pairs, k), s[0])
rising = [(i, "x") for i in range(1000)]
falling = [(-i, "x") for i in range(1000)]
s1, s2 = [0], [0]
top_k(rising, 10, s1)
top_k(falling, 10, s2)
print(s1[0], s2[0])
# Expected: 0 True 0
#           1 True 2
#           3 True 4
#           10 True 6
#           1000 10

# Rung 4: merge two sorted lists, stable (equal values: left list first), and count comparisons.
# After 4 wins in a row by one side, gallop: probe 1, 2, 4... ahead, then binary search.
# Time O(n) comparisons worst case, about m log n when one list has only m items.
def gallop(seq, lo, take, counter):
  """First index k >= lo where take(seq[k]) is False. take is True, then False, along a sorted seq."""
  # TODO: doubling steps from lo while take is True (count 1 per call to take),
  # then a binary search between the last True and the first False (count 1 per call)
  pass

def merge_counted(a, b, use_gallop, counter):
  out, i, j = [], 0, 0
  streak_a = streak_b = 0
  while i < len(a) and j < len(b):
      counter[0] += 1
      if a[i] <= b[j]:
          out.append(a[i])
          i += 1
          streak_a, streak_b = streak_a + 1, 0
      else:
          out.append(b[j])
          j += 1
          streak_b, streak_a = streak_b + 1, 0
      # TODO: if use_gallop and a side has won 4 in a row and both lists still have items,
      # call gallop to find how many more items of the winning list come before the other list's
      # head (a wins ties: take values <= b[j]; b takes values < a[i]), extend out, and reset the streak
  return out + a[i:] + b[j:]

def cost(a, b, use_gallop):
  c = [0]
  assert merge_counted(a, b, use_gallop, c) == sorted(a + b)
  return c[0]

long_run = list(range(0, 20_000, 2))
print(cost(long_run, [5, 7, 9, 10_001, 15_001], False), cost(long_run, [5, 7, 9, 10_001, 15_001], True))
odds = list(range(1, 20_000, 2))
print(cost(long_run, odds, False), cost(long_run, odds, True))
print(cost([], [1, 2], True), cost([1, 2], [], True), cost([], [], True))

class Item:
  """A value with a tag. Comparisons look at the value only, so the tag shows which equal item came first."""
  def __init__(self, value, tag):
      self.value, self.tag = value, tag

def __le__(self, other):
      return self.value <= other.value

def __lt__(self, other):
      return self.value < other.value

left = [Item(1, "L1"), Item(1, "L2"), Item(2, "L3")]
right = [Item(1, "R1"), Item(2, "R2"), Item(2, "R3")]
print([m.tag for m in merge_counted(left, right, True, [0])])
# Expected: 7506 68
#           19999 19999
#           0 0 0
#           ['L1', 'L2', 'R1', 'L3', 'R2', 'R3']

# Rung 5: a dict in miniature. indices holds EMPTY, DELETED, or a position in entries.
# entries holds [key, value] lists in insertion order, or None where a key was deleted.
# Linear probing keeps the code short (CPython perturbs). Time O(1) average, O(n) worst case.
# self.probes counts every slot looked at.
EMPTY, DELETED = None, -1

class MiniDict:
  def __init__(self, hash_fn=hash):
      self.hash_fn = hash_fn
      self.indices = [EMPTY] * 8
      self.entries = []
      self.live = 0
      self.probes = 0

def _find(self, key):
      """Return (slot holding key or -1, first slot where key could be placed)."""
      # TODO: start at hash_fn(key) & mask and probe slot + 1. Count a probe per slot.
      # EMPTY ends the search (not found; place at the first DELETED slot seen, else here).
      # DELETED must NOT end the search: remember the first one and keep going.
      pass

def get(self, key, default=None):
      # TODO: use _find; return default when the slot is -1
      pass

def set(self, key, value):
      # TODO: update in place if found (the position in entries must not change).
      # Otherwise, if (len(entries) + 1) * 3 > len(indices) * 2, call _rebuild and find again.
      # Then store len(entries) in the free slot and append [key, value]. Count live.
      pass

def delete(self, key):
      # TODO: raise KeyError if missing. Set the entry to None, the slot to DELETED, and fix live.
      pass

def _rebuild(self):
      """Drop deleted entries, keep order, and size the table for the live entries."""
      old = [e for e in self.entries if e is not None]
      size = 8
      while size * 2 < (len(old) + 1) * 3:
          size *= 2
      self.indices = [EMPTY] * size
      self.entries = []
      for key, value in old:
          slot, free = self._find(key)
          self.indices[free] = len(self.entries)
          self.entries.append([key, value])

def keys(self):
      return [e[0] for e in self.entries if e is not None]

d = MiniDict()
for k in (10, 20, 30):
  d.set(k, k * 2)
d.set(10, 99)
d.delete(20)
d.set(20, 1)
print(d.keys(), d.get(10), d.get(20), d.get(404, "none"))

clash = MiniDict()
for k in (0, 8, 16, 24, 32):            # all have home slot 0 in a table of 8, so they pile up
  clash.set(k, k)
clash.probes = 0
clash.get(32)
print("probes to find the last key:", clash.probes)
clash.delete(8)
print("after deleting a middle key:", clash.get(32), clash.get(24))

churn = MiniDict()
for round_ in range(200):
  churn.set(round_, round_)
  churn.delete(round_)
print(len(churn.entries) < 20, churn.live, churn.keys())
big = MiniDict()
for k in range(1000):
  big.set(k, k)
print(big.keys() == list(range(1000)), all(big.get(k) == k for k in range(1000)), len(big.indices))
# Expected: [10, 30, 20] 99 1 none
#           probes to find the last key: 5
#           after deleting a middle key: 32 24
#           True 0 []
#           True True 2048

Tests · Rung 1: (11, 1023) (125, 62000) for 1,000 appends; n = 0 gives (0, 0); a rule that does not grow raises ValueError. Rung 2: every result is a valid heap; the empty and one-item lists cost 0; all-equal and descending lists must not break it; 5,000 random items use fewer than 10,000 comparisons. Rung 3: ties keep the earlier pair, k = 0 gives an empty list, k above the stream length returns every pair, a rising stream replaces 1,000 times and a falling one only 10. Rung 4: with 5 stragglers inside a 10,000-item run the plain merge counts 7506 and the galloping merge 68; interleaved input costs 19999 either way; empty inputs cost 0; equal values come out left list first. Rung 5: insertion order survives update, delete and re-insert, a DELETED marker keeps a collided key findable, 200 insert and delete rounds leave under 20 entries, and 1,000 keys give a 2,048-slot table.

Read the counters before you move on. The galloping merge needs 68 comparisons where the plain merge needs 7,506, and it loses nothing on interleaved input. The last rung shows why del leaves holes until a rebuild.

#Recap

A list, a tuple, a dict and a set all hold pointers. A list grows by a ratio r above 1, so appends are O(1) amortized with at most r/(r-1) copies each. A dict lookup checks identity, then the stored hash, then ==, so equal keys need equal hashes and a stored key must never change its hash. Dict order is a promise. Set order is an accident.

A deque is a chain of blocks with O(1) ends. A heapq heap is a list where each parent is at most its children: O(log n) push and pop, O(n) heapify. Timsort finds runs, merges them in balanced order and gallops over streaks, so it is O(n log n) worst case and O(n) on one run. Interning is an implementation detail, and bisect.insort finds in O(log n) but shifts in O(n).

Quick Check1 / 6

A model list grows its capacity by multiplying by 1.5 each time it is full. About how many items are copied per append, at most, over a long run of appends?

Recap

Key Takeaways

Every container holds pointers, so copies are shallow and each cost is a cost of moving or comparing pointers
A list grows by a ratio above 1, which bounds copies per append by r/(r-1); a fixed step costs O(n) per append and O(n²) overall
A dict lookup checks identity, then the stored hash, then ==, so equal keys need equal hashes and a stored key must not change its hash
Dict order is a language promise (update keeps the place, delete then insert goes to the end); set order is an accident of slots
A deque is a chain of blocks, a heapq heap is a list with the parent-at-most-children rule, and heapify is O(n) because most nodes sit near the bottom
Timsort finds runs, binary-inserts short ones, merges in balanced order and gallops over streaks: O(n log n) worst case, O(n) on one run, and stable
Compare values with ==, never rely on interning, and remember that bisect.insort finds in O(log n) but shifts in O(n)

CPython Container Internals: list, dict, set, heapq, sorted and bisect

Learning Objectives

After this lesson, you will be able to:

Explain why a list over-allocates, simulate its growth with different rules, and show that a proportional rule gives O(1) amortized appends while a fixed step does not
State the hash and equality contract a dict depends on, and show how a key that changes after insertion gets lost
Say what insertion order guarantees in a dict, and what happens to it on update, delete and re-insert
Explain why a set prints in an order you cannot rely on, and why a tuple is hashable only if its items are
Describe a deque as a chain of blocks and a heapq heap as a plain list, and count the comparisons of heapify, push and pop
Explain runs, binary insertion, merging and galloping in Timsort, and show its adaptivity and stability with a comparison counter
Say what interning and the small-integer cache promise (little) and use bisect with a clear idea of where its time goes

Prerequisites

Before You Start

Review

#The Picture Under Every Container

Two facts follow from this. First, a[i] is one step, because the address is the start of the row plus i times the size of a pointer. Second, copying a container copies pointers, not objects.

pythonrunnable cell

rows = [[1], [2]]
copy = rows[:]            # a new row of pointers
copy[0].append(9)         # but both rows still point at the same inner list
print(rows)
# Output:
# [[1, 9], [2]]

#list: A Row of Pointers That Over-Allocates

Append number	Length before	Capacity before	Reallocate?	Pointers copied
1	0	0	yes, to 1	0
2	1	1	yes, to 2	1
3	2	2	yes, to 4	2
4	3	4	no	0
5	4	4	yes, to 8	4

Appends 6, 7 and 8 fit without any copy. The next copy comes at append 9. Copies get rarer as the list grows. Before we count them, make a prediction about a different rule.

What Do You Think?

A model list adds room for 8 more pointers each time it is full. You compare building a list of 10,000 items with building one of 100,000 items. About how does the copying work per append change?

The cell below simulates four growth rules. It builds no real list. It only counts how many pointers the reallocations copy.

pythonrunnable cell

def simulate_appends(n, grow):
    """Return (reallocations, copies) for n appends. grow(capacity) gives the new capacity."""
    capacity, size, reallocs, copies = 0, 0, 0, 0
    for _ in range(n):
        if size == capacity:
            capacity = grow(capacity)
            copies += size                  # a full block is copied into the bigger one
            reallocs += 1
        size += 1
    return reallocs, copies


rules = {
    "add 8 slots": lambda c: c + 8,
    "times 1.25": lambda c: max(c + 1, int(c * 1.25)),
    "times 1.5": lambda c: max(c + 1, int(c * 1.5)),
    "times 2": lambda c: max(1, c * 2),
}
for n in (1_000, 100_000):
    for name, grow in rules.items():
        reallocs, copies = simulate_appends(n, grow)
        print(f"n={n:>7} {name:<12} reallocations={reallocs:>6} copies per append={copies / n:.2f}")
# Output:
# n=   1000 add 8 slots  reallocations=   125 copies per append=62.00
# n=   1000 times 1.25   reallocations=    31 copies per append=4.49
# n=   1000 times 1.5    reallocations=    18 copies per append=2.14
# n=   1000 times 2      reallocations=    11 copies per append=1.02
# n= 100000 add 8 slots  reallocations= 12500 copies per append=6249.50
# n= 100000 times 1.25   reallocations=    52 copies per append=4.82
# n= 100000 times 1.5    reallocations=    30 copies per append=2.77
# n= 100000 times 2      reallocations=    18 copies per append=1.31

With a fixed step the copy sizes are 8, 16, 24 and so on. They add up to about n²/16, which is O(n²) for n appends.

A real allocator can sometimes extend a block in place without copying, so our counts are the worst case. The next cell checks the real list for the same behavior without printing any size.

pythonrunnable cell

import sys


def allocation_changes(n):
    """How many times does the size of a list's block change over n appends?"""
    items, last, changes = [], sys.getsizeof([]), 0
    for i in range(n):
        items.append(i)
        size = sys.getsizeof(items)
        if size != last:
            changes += 1
            last = size
    return changes


few, many = allocation_changes(1_000), allocation_changes(100_000)
print("changes happen on only a few appends:", many < 100_000 // 100)
print("100 times more appends, fewer than 3 times more changes:", many < 3 * few)
# Output:
# changes happen on only a few appends: True
# 100 times more appends, fewer than 3 times more changes: True

#tuple: The Same Row, With No Spare Room

"Immutable" has a precise meaning here: the tuple's slots can never point somewhere else. It does not mean the objects behind the pointers are frozen.

pythonrunnable cell

t = (1, [2, 3])
t[1].append(4)                # allowed: the slot still points at the same list
print(t)
try:
    hash(t)
except TypeError as error:
    print("TypeError:", error)
print(hash((1, 2)) == hash((1, 2)))
# Output:
# (1, [2, 3, 4])
# TypeError: unhashable type: 'list'
# True

#dict: Order, Equality and the Hashing Contract

pythonrunnable cell

d = {}
d["a"], d["b"], d["c"] = 1, 2, 3
d["a"] = 10                      # update: the key keeps its place
print(list(d))
del d["a"]
d["a"] = 11                      # delete, then insert again: the key goes to the end
print(list(d))
print({1: "x", 2: "y"} == {2: "y", 1: "x"})
try:
    for key in d:
        d[key + "!"] = 0
except RuntimeError as error:
    print("RuntimeError:", error)
# Output:
# ['a', 'b', 'c']
# ['b', 'c', 'a']
# True
# RuntimeError: dictionary changed size during iteration

The cell counts == calls to show the recipe. It also shows a famous exception, a key that is not equal to itself.

pythonrunnable cell

class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return hash(self.v)

    def __eq__(self, other):
        Key.eq_calls += 1
        return self.v == other.v


first = Key(5)
table = {first: "five"}


def eq_calls_for(probe):
    Key.eq_calls = 0
    table.get(probe)
    return Key.eq_calls


print("the same object:", eq_calls_for(first))
print("an equal object:", eq_calls_for(Key(5)))
print("a different hash:", eq_calls_for(Key(6)))
nan = float("nan")
print({nan: 1}[nan], float("nan") in {nan: 1})
# Output:
# the same object: 0
# an equal object: 1
# a different hash: 0
# 1 False

Now predict what happens when a key changes after it is stored.

What Do You Think?

#set: A Dict Without Values

A set uses the same hashing recipe and the same contract, with entries that hold only a key. Its costs match a dict: O(1) on average for add, remove and in, and O(n) in the worst case.

A set is not ordered, and what it prints is an accident of slot positions.

pythonrunnable cell

print({3, 1, 2})
print({8, 1})
print(frozenset({1, 2}) == frozenset({2, 1}), {frozenset({1, 2}): "ok"}[frozenset({2, 1})])
# Output:
# {1, 2, 3}
# {8, 1}
# True ok

#deque: A Chain of Blocks

What a deque gives up is cheap indexing. To reach item i it walks the chain from the nearer end, so d[i] is O(n) in the middle, and there are no slices.

pythonrunnable cell

from collections import deque

window = deque(range(5), maxlen=3)      # a full deque drops from the other end
print(window)
d = deque([1, 2, 3])
d.rotate(1)
d.appendleft(0)
print(d, d[0], d[-1])
try:
    d[1:3]
except TypeError as error:
    print("TypeError:", error)
# Output:
# deque([2, 3, 4], maxlen=3)
# deque([0, 3, 1, 2]) 0 2
# TypeError: sequence index must be integer, not 'slice'

#heapq: A Heap Is Just a List

No child is smaller than its parent, so heap[0] is the smallest item. The list is not sorted.

Push. Append the item at the end, then sift up: swap it with its parent while it is smaller. The tree has about log n levels, so a push is O(log n) in the worst case.

What Do You Think?

What does this print? import heapq h = [5, 3, 8, 1, 9, 2] heapq.heapify(h) print(h)

The next cell counts comparisons for each operation on 10,000 items. Only facts that do not depend on the version are printed.

pythonrunnable cell

import heapq
import math
import random


class Counted:
    """A number that counts every < it takes part in."""
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


def count(action):
    Counted.compares = 0
    action()
    return Counted.compares


n = 10_000
random.seed(5)
values = random.sample(range(10 * n), n)
objects = [Counted(v) for v in values]
print("heapify uses fewer than 2n comparisons:", count(lambda: heapq.heapify(objects)) < 2 * n)

heap = []
print("n ascending pushes:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in range(n)]))
heap = []
print("n descending pushes, more than 5n:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in range(n, 0, -1)]) > 5 * n)
heap = []
print("n random pushes, fewer than 3n:", count(lambda: [heapq.heappush(heap, Counted(v)) for v in values]) < 3 * n)
print("n pops, fewer than n log2 n:", count(lambda: [heapq.heappop(heap) for _ in range(n)]) < n * math.log2(n))
# Output:
# heapify uses fewer than 2n comparisons: True
# n ascending pushes: 9999
# n descending pushes, more than 5n: True
# n random pushes, fewer than 3n: True
# n pops, fewer than n log2 n: True

A heap is not a search structure. x in heap is O(n), because the invariant says nothing about where x is. If you need the items in order, pop them or sort a copy.

#sorted and list.sort: Timsort in Detail

The earlier lesson told the story in one paragraph. Here are the parts, with their reasons.

What Do You Think?

A list has 10,000 items in rising order, followed by 5 extra items that belong somewhere inside that run. About how many comparisons does sorted need?

pythonrunnable cell

import math
import random


class Counted:
    """A number that counts every < it takes part in."""
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


def sort_cost(values):
    Counted.compares = 0
    sorted(Counted(v) for v in values)
    return Counted.compares


n = 10_000
ordered = list(range(n))
random.seed(1)
shuffled = ordered[:]
random.shuffle(shuffled)

print("one rising run:", sort_cost(ordered), "| n - 1 =", n - 1)
print("one falling run:", sort_cost(ordered[::-1]))
print("shuffled, below n log2 n:", sort_cost(shuffled) < n * math.log2(n))
print("shuffled, above 5n:", sort_cost(shuffled) > 5 * n)

blocks = [list(range(i * 1_000, (i + 1) * 1_000)) for i in range(10)]
random.shuffle(blocks)
flat = [x for block in blocks for x in block]
print("10 sorted blocks in random order, below 1.1 n:", sort_cost(flat) < 1.1 * n)

stragglers = list(range(0, 20_000, 2)) + [5, 7, 9, 10_001, 15_001]
extra = sort_cost(stragglers) - (len(stragglers) - 1)
print("a long run plus 5 stragglers, extra comparisons under 200:", 0 < extra < 200)
# Output:
# one rising run: 9999 | n - 1 = 9999
# one falling run: 9999
# shuffled, below n log2 n: True
# shuffled, above 5n: True
# 10 sorted blocks in random order, below 1.1 n: True
# a long run plus 5 stragglers, extra comparisons under 200: True

pythonrunnable cell

rows = [("b", 1), ("a", 1), ("c", 0), ("d", 1)]
by_score = lambda row: row[1]
print(sorted(rows, key=by_score))
print(sorted(rows, key=by_score, reverse=True))
print(sorted(rows, key=by_score)[::-1])

items = [3, 1, 2]
seen = []
items.sort(key=lambda x: seen.append(len(items)) or x)
print(seen, items)
# Output:
# [('c', 0), ('b', 1), ('a', 1), ('d', 1)]
# [('b', 1), ('a', 1), ('d', 1), ('c', 0)]
# [('d', 1), ('a', 1), ('b', 1), ('c', 0)]
# [0, 0, 0] [1, 2, 3]

#Interning and Small Integers: What You May Rely On

pythonrunnable cell

import sys

built = "".join(["he", "llo"])
literal = "hello"
print(built == literal)
print(sys.intern(built) is sys.intern(literal))
# Output:
# True
# True

#bisect: Binary Search on a List

The cell counts comparisons, using the key= argument (Python 3.10 and later) to wrap each probed item in a counting class.

pythonrunnable cell

import bisect


class Counted:
    compares = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.compares += 1
        return self.value < other.value


for n in (1_000, 1_000_000):
    data = list(range(n))
    Counted.compares = 0
    spot = bisect.bisect_left(data, Counted(777), key=Counted)
    print(n, spot, Counted.compares)

a = [1, 2, 2, 2, 3]
print(bisect.bisect_left(a, 2), bisect.bisect_right(a, 2))
bisect.insort(a, 2)            # insort means insort_right: the new 2 goes after the old ones
print(a)
# Output:
# 1000 777 10
# 1000000 777 20
# 1 4
# [1, 2, 2, 2, 2, 3]

A thousand times more items costs ten more comparisons. The count of items equal to x in a sorted list is bisect_right(a, x) - bisect_left(a, x), in O(log n).

#Choosing: Costs with Reasons

Costs are for CPython, "avg" means average case, and "amort." means amortized.

You need	Use	Cost	Why
Add or remove at the end	`list`	O(1) amort.	spare room, and no pointer after it moves
Add or remove at the front	`deque`	O(1)	a chain of blocks, no shifting
Is this item present?	`set` or `dict`	O(1) avg	hash to a slot, then the lookup recipe
Items in the order they arrived, with lookup	`dict`	O(1) avg	the entries array keeps the order
The smallest item again and again	`heapq`	O(log n) per pop	heap invariant in a list
The k best of a stream	`heapq.nlargest`	O(n log k)	a heap of size k
Sort once	`sorted`	O(n log n), O(n) if mostly ordered	Timsort finds runs
A sorted list with a few inserts	`bisect.insort`	O(n) per insert	search is log n, but the shift is n
How many items lie in a range of a sorted list	two `bisect` calls	O(log n)	two binary searches

When not to use each. Do not use a list as a queue for large n, since pop(0) is O(n). Do not use a deque when you index into the middle. Do not use a heap to test membership.

Do not use insort to build a million-item sorted list one item at a time: append everything and sort once, which is O(n log n) rather than O(n²).

#Where These Show Up

#Common Mistakes

Watch Out

Changing a key's hash after it is in a dict or set

Fix: Hash only on fields that never change after the object is stored, or use an immutable type such as a tuple or a frozen dataclass.

pythonrunnable cell

class Point:
    def __init__(self, x):
        self.x = x

    def __hash__(self):
        return hash(self.x)

    def __eq__(self, other):
        return self.x == other.x


p = Point(1)
seen = {p}
p.x = 2
print(Point(1) in seen, Point(2) in seen, p in seen, len(seen))
# Output:
# False False False 1

Watch Out

Pushing pairs that can tie onto a heap

Fix: Push (priority, counter, item), where the counter is a number that only goes up, so a tie never reaches the item.

pythonrunnable cell

import heapq
from itertools import count

heap = []
heapq.heappush(heap, (1, {"job": "a"}))
try:
    heapq.heappush(heap, (1, {"job": "b"}))
except TypeError as error:
    print("TypeError:", error)

ticket = count()
safe = []
heapq.heappush(safe, (1, next(ticket), {"job": "a"}))
heapq.heappush(safe, (1, next(ticket), {"job": "b"}))
print([entry[2]["job"] for entry in (heapq.heappop(safe), heapq.heappop(safe))])
# Output:
# TypeError: '<' not supported between instances of 'dict' and 'dict'
# ['a', 'b']