lesson 185 Profiling & Optimization · advanced

Algorithmic optimization: change the work, not the details

No amount of micro-tuning makes a quadratic loop fast. Profiling points at the hot spot; an index, a sort or moving work out of a loop changes how the work grows; a comparison of old and new results proves nothing broke.

You'll be able to

Spot repeated scans and repeated setup work inside loops
Replace them with a dictionary or set built once, a single sort, or work moved out of the loop
Prove an optimisation by checking equal results and counting the operations saved

The idea

The previous lessons gave you the tools: Big O to reason (see Algorithms & Complexity), cProfile to find the hot spot, timeit to measure. The usual fixes, in order of how much they gain:

Build an index once instead of scanning inside a loop (O(n·m) → O(n + m)).
Sort once and walk or bisect, instead of searching repeatedly.
Hoist work that doesn't change out of the loop: building a set, compiling a pattern, computing a constant.

Every optimisation must keep the results identical. Keep the old version, run both on the same data, and compare.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Matching payments to orders: scan against index

def unpaid_slow(orders, payments):
    unpaid = []
    for order in orders:
        paid = False
        for payment in payments:
            if payment["order_id"] == order["order_id"]:
                paid = True
        if not paid:
            unpaid.append(order["order_id"])
    return unpaid

def unpaid_fast(orders, payments):
    paid_ids = {payment["order_id"] for payment in payments}
    return [order["order_id"] for order in orders if order["order_id"] not in paid_ids]

orders = [{"order_id": f"O{100000 + n}"} for n in range(3000)]
payments = [{"order_id": f"O{100000 + n}"} for n in range(0, 3000, 2)]
print(unpaid_slow(orders, payments) == unpaid_fast(orders, payments))
print(len(unpaid_fast(orders, payments)))
print(len(orders) * len(payments), len(orders) + len(payments))

Hoisting is the second common fix. A loop that rebuilds the same set, list or pattern on every pass multiplies its cost by the number of passes, even though the result never changes.

example-2.py · Work that doesn't belong inside the loop

import re

holidays = ["2025-01-01", "2025-01-20", "2025-02-17", "2025-05-26"]
deliveries = [("O1", "2025-01-20"), ("O2", "2025-01-21"), ("O3", "2025-05-26"), ("O4", "bad-date")]

def flagged_slow(deliveries):
    flagged = []
    for order_id, day in deliveries:
        valid = re.compile(r"\d{4}-\d{2}-\d{2}")
        closed = set(holidays)
        if valid.fullmatch(day) and day in closed:
            flagged.append(order_id)
    return flagged

def flagged_fast(deliveries):
    valid = re.compile(r"\d{4}-\d{2}-\d{2}")
    closed = set(holidays)
    flagged = []
    for order_id, day in deliveries:
        if valid.fullmatch(day) and day in closed:
            flagged.append(order_id)
    return flagged

print(flagged_slow(deliveries), flagged_fast(deliveries))

When to optimise: when a profile shows a real hot spot on realistic data, and the code is too slow for its job. How to prove it: equal results on the same inputs (including edge cases), then fewer operations or a better timing ratio. Mistakes to avoid: optimising code that isn't hot; changing behaviour by accident (order of results, duplicates, ties); and trading a clear O(n) loop for clever code that is no faster.

Review

Find the hot spot with a profile; fix the algorithm before the details.
Index once, sort once, hoist unchanging work out of loops.
Prove it: identical results on the same inputs, then fewer operations or a better ratio.
Next module: running work at the same time, with threads and processes.

Practise this