Efficient use of built-in data structures

The profile from lesson 2 left no doubt: Anita's month-end report spends almost all its time in find_product, which scans a list of 600 products for every one of 20,000 sales. The cure is not a faster loop. It is a different data structure. Python's built-in types, lists, dictionaries, sets and tuples, plus a handful of specialized containers in the standard library, each have operations that are fast and operations that are slow. Choosing the right container for the job is the single most effective performance skill in everyday Python.

This lesson goes through the cost of the common operations on each built-in type, shows how to build an index with a dictionary, uses sets for fast membership and duplicate removal, replaces slow queue code with collections.deque, counts with Counter and defaultdict, finds the top items with heapq, searches sorted data with bisect, and covers the small idioms, such as str.join and preferring built-in functions, that keep Python code fast without making it obscure.

The cost of list operations

A Python list is a dynamic array: the items sit in one block of memory in order, and the list keeps extra room at the end. That layout makes some operations very cheap and others expensive. Reading or replacing an item by index, appending to the end and popping from the end are O(1), constant time, whatever the list's length. Inserting or deleting at the front or in the middle is O(n), because every later item must move along by one place. Searching for a value with in, index() or count() is O(n), because Python has to look at the items one by one.

from collections import deque

def front_insert_moves(n):
    """How many item moves inserting n items at the front of a list costs."""
    moves = 0
    for size in range(n):
        moves += size            # every existing item shifts one place
    return moves

for n in [10, 1_000, 100_000]:
    print(f"{n:>7,} front inserts: {front_insert_moves(n):>13,} item moves; appends: 0 moves")

orders = []
for o in ["A-1", "A-2", "A-3"]:
    orders.append(o)             # O(1) at the end
print(orders, orders[-1], orders.pop())

     10 front inserts:            45 item moves; appends: 0 moves
  1,000 front inserts:       499,500 item moves; appends: 0 moves
100,000 front inserts: 4,999,950,000 item moves; appends: 0 moves
['A-1', 'A-2'] A-3 A-3

The count of item moves grows with the square of the number of inserts: five billion moves to build a list of 100,000 items by inserting each at the front, against none for appending. If you need to add at the front, either build the list by appending and reverse it once at the end, or use a deque, described below.

Dictionaries and sets: hashing

Dictionaries and sets are hash tables. When you store a key, Python computes its hash, a number derived from the value, and uses it to choose a slot in an internal table. To look a key up, Python computes the hash again and goes straight to the slot. Looking up, adding and deleting a key are therefore O(1) on average, no matter how many keys are stored. The price is memory, since hash tables keep spare slots, and the rule that keys must be hashable: immutable values such as strings, numbers and tuples of them, but not lists or dictionaries.

Jordan's fix for the report follows directly. Instead of scanning the product list for every sale, he builds a dictionary from sku to product once, which costs one pass over the 600 products, and then each sale is a single lookup. Counting the comparisons shows the difference, and the timing confirms it.

import random, time

rnd = random.Random(7)
PRODUCTS = [{"sku": f"RC-{n}", "price": 18 + n % 5} for n in range(101, 701)]
SALES = [(f"RC-{rnd.randint(101, 700)}", rnd.randint(1, 3)) for _ in range(20_000)]

def report_scan(sales):
    totals = {}
    for sku, qty in sales:
        product = next(p for p in PRODUCTS if p["sku"] == sku)   # O(n) scan
        totals[sku] = totals.get(sku, 0) + product["price"] * qty
    return totals

def report_index(sales):
    by_sku = {p["sku"]: p for p in PRODUCTS}                     # built once
    totals = {}
    for sku, qty in sales:
        totals[sku] = totals.get(sku, 0) + by_sku[sku]["price"] * qty
    return totals

for f in (report_scan, report_index):
    start = time.perf_counter()
    result = f(SALES)
    print(f"{f.__name__:13} {time.perf_counter() - start:.4f} s, grand total {sum(result.values()):,}")
print("same answer:", report_scan(SALES) == report_index(SALES))

report_scan   0.2014 s, grand total 798,819
report_index  0.0031 s, grand total 798,819
same answer: True

On a typical laptop the indexed version is dozens of times faster, and the gap widens as the product list grows. The result is identical, which the last line checks. This one change took the real report from minutes to a couple of seconds, comfortably inside the 10-second goal from lesson 1.

def build_index(products):
    return products

def order_total(lines, index):
    total = 0
    for sku, qty in lines:
        for p in index:
            if p['sku'] == sku:
                total += p['price'] * qty
    return total

idx = build_index(PRODUCTS)
print(order_total([('RC-101', 2), ('RC-104', 1)], idx))

Sets for membership and duplicates

When you only need to know whether something is present, use a set. Checking x in some_set is O(1) on average, while x in some_list is O(n). Sets also remove duplicates for free and support the operations of set algebra: union, intersection and difference, each of which runs in time proportional to the sizes involved rather than their product. A common slow pattern is filtering one list against another with a nested membership test; converting the second list to a set first turns an O(n × m) job into O(n + m).

loyalty_members = [f"555-{n:04d}" for n in range(0, 20_000, 3)]       # phone numbers
todays_phones = [f"555-{n:04d}" for n in range(0, 20_000, 7)]

def checks_list(phones, members):
    steps = 0
    found = 0
    for ph in phones:
        for m in members:                # what "ph in members" does for a list
            steps += 1
            if m == ph:
                found += 1
                break
    return found, steps

member_set = set(loyalty_members)
found_set = sum(1 for ph in todays_phones if ph in member_set)
found_list, steps = checks_list(todays_phones, loyalty_members)
print("members among today's customers:", found_set, found_list)
print(f"list version: {steps:,} comparisons; set version: {len(todays_phones):,} lookups")
print("first four unique roasts:", sorted(set(["B-0412", "B-0413", "B-0412", "B-0414"])))

members among today's customers: 953 953
list version: 15,876,984 comparisons; set version: 2,858 lookups
first four unique roasts: ['B-0412', 'B-0413', 'B-0414']

The order of items in a set is not defined, so print sorted(the_set) when you need repeatable output. If you need to remove duplicates but keep the original order, dict.fromkeys(items) does it in one pass, because dictionaries remember insertion order and their keys are unique.

collections.deque for queues

A queue takes items from the front and adds them at the back. With a list, list.pop(0) is O(n), because every remaining item moves forward. collections.deque, a double-ended queue, supports O(1) appends and pops at both ends. Theo's order-processing loop takes orders first in, first out; with thousands of orders a day, the deque version stays fast while the list version slows down as the backlog grows. A deque with maxlen also makes a convenient sliding window that discards the oldest item automatically.

from collections import deque

queue = deque(["A-1001", "A-1002", "A-1003"])
queue.append("A-1004")            # arrives at the back
first = queue.popleft()           # served from the front, O(1)
print("served:", first, "waiting:", list(queue))

# last five temperatures from the roaster, oldest dropped automatically
recent = deque(maxlen=5)
for t in [182, 186, 190, 195, 199, 204, 208]:
    recent.append(t)
print("window:", list(recent), "average:", sum(recent) / len(recent))

served: A-1001 waiting: ['A-1002', 'A-1003', 'A-1004']
window: [190, 195, 199, 204, 208] average: 199.2

from collections import deque

def rolling_average(readings, k):
    return readings

print(rolling_average([180, 190, 200, 210], 2))

Counting and grouping

Counting things is so common that the standard library has two containers for it. collections.Counter counts hashable items in one pass and has most_common() for the top entries. collections.defaultdict creates a missing key's value automatically, which removes the if key not in d checks that clutter grouping code. Both are dictionaries underneath, so they keep the O(1) lookups.

from collections import Counter, defaultdict

sales = [("RC-101", 2), ("RC-106", 1), ("RC-101", 1), ("RC-103", 2), ("RC-106", 3), ("RC-101", 1)]

bags = Counter()
for sku, qty in sales:
    bags[sku] += qty
print("bags sold:", dict(sorted(bags.items())))
print("top two:", bags.most_common(2))

by_qty = defaultdict(list)
for sku, qty in sales:
    by_qty[qty].append(sku)          # no need to create the list first
print("orders by quantity:", dict(sorted(by_qty.items())))

bags sold: {'RC-101': 4, 'RC-103': 2, 'RC-106': 4}
top two: [('RC-101', 4), ('RC-106', 4)]
orders by quantity: {1: ['RC-106', 'RC-101', 'RC-101'], 2: ['RC-101', 'RC-103'], 3: ['RC-106']}

heapq for the top items

Finding the ten best-selling coffees by sorting the whole list is O(n log n). When you only need the top or bottom k items, heapq.nlargest and heapq.nsmallest do it in O(n log k), which for k much smaller than n is close to a single pass. A heap is also the right structure for a priority queue, where you repeatedly need the smallest remaining item: heappush and heappop are O(log n).

import heapq

batches = [("B-0412", 14.2), ("B-0413", 12.8), ("B-0414", 15.6), ("B-0415", 13.1), ("B-0416", 16.0)]
print("two longest roasts:", heapq.nlargest(2, batches, key=lambda b: b[1]))
print("shortest roast:", heapq.nsmallest(1, batches, key=lambda b: b[1]))

jobs = []                                    # (priority, job): smaller number first
for job in [(3, "print labels"), (1, "ship express order"), (2, "update stock")]:
    heapq.heappush(jobs, job)
while jobs:
    print("next:", heapq.heappop(jobs)[1])

two longest roasts: [('B-0416', 16.0), ('B-0414', 15.6)]
shortest roast: [('B-0413', 12.8)]
next: ship express order
next: update stock
next: print labels

bisect for sorted data

If data is kept sorted, a binary search finds a position in O(log n). The bisect module provides it: bisect_left returns where a value would be inserted to keep the list sorted, and insort inserts it there. Mei's loyalty tiers are a classic use: a sorted list of thresholds and bisect turn a points total into a tier in a couple of comparisons, without a chain of if statements.

from bisect import bisect_right

THRESHOLDS = [100, 300]                     # points needed for Roast, Reserve
TIERS = ["Bean", "Roast", "Reserve"]

def tier(points):
    return TIERS[bisect_right(THRESHOLDS, points)]

for p in [0, 99, 100, 299, 300, 1200]:
    print(p, tier(p))

0 Bean
99 Bean
100 Roast
299 Roast
300 Reserve
1200 Reserve

Small idioms that add up

A few habits keep everyday Python fast. Build strings with str.join on a list of pieces rather than += in a loop, which can copy the growing string each time. Prefer built-in functions such as sum, min, max, any, all and sorted with a key over equivalent Python loops: they run in C and avoid the interpreter's per-iteration overhead. Look up attributes and global names once outside a hot loop if the loop runs millions of times. And use comprehensions, which are a little faster than the same loop with append, as well as clearer.

import timeit

words = ["roast"] * 5000

def with_plus():
    s = ""
    for w in words:
        s += w + ","
    return s

def with_join():
    return ",".join(words) + ","

def manual_sum():
    total = 0
    for n in range(10_000):
        total += n
    return total

print("same string:", with_plus() == with_join())
for f in (with_plus, with_join, manual_sum, lambda: sum(range(10_000))):
    t = min(timeit.repeat(f, number=50, repeat=3))
    print(f"{getattr(f, '__name__', 'builtin sum'):12} {t * 1000:.2f} ms for 50 runs")

same string: True
with_plus    13.45 ms for 50 runs
with_join    1.29 ms for 50 runs
manual_sum   12.74 ms for 50 runs
<lambda>     4.62 ms for 50 runs

def unique_in_order(ids):
    out = []
    for i in ids:
        if ids.count(i) >= 1 and i not in out:
            out.append(i)
    return out

print(unique_in_order(['B-12', 'B-13', 'B-12', 'B-14', 'B-13']))