Choosing a Structure

Data Structures in Practice 🏆

Chapter 1 · Choosing a Structure

Two programs can give exactly the same answers and still differ by a factor of ten thousand in speed. The usual cause is not clever code but the data structure underneath: the way the values are arranged in memory and the operations that arrangement makes cheap or expensive. This course is practical. Each chapter takes one family of structures, shows what it costs, and gives you a rule for when to reach for it. All examples are Python 3.

What was run, and what was not

The comparison counts in this chapter come from running the code shown and are exact. Timings depend on the machine and Python version, so only the pattern (which is slower, and how the gap grows) is claimed, not the exact seconds.

Cost Is a Property of the Operation

A structure is never simply "fast" or "slow". It is fast at some operations and slow at others. The honest question is always: what will my code do most often? Append at the end? Look up by key? Check "is this already here?" Remove from the front? The answer picks the structure.

Operation	list	set	dict	deque
x in c	scans every item	one hash lookup	one hash lookup (keys)	scans every item
add at the end	cheap (amortised)	cheap	cheap	cheap
add at the front	moves every item	no front	no front	cheap
item by position	direct	no positions	no positions	slow in the middle
keeps order	yes	no	yes (insertion order)	yes

Counting Work: Linear Versus Binary Search

Instead of timing, count. The function below walks a list from the start and counts how many times it compares an item with the target. That count is the work, and it does not depend on the machine.

def linear_count(items, target):
    comparisons = 0
    for x in items:
        comparisons += 1
        if x == target:
            return True, comparisons
    return False, comparisons
    

If the list is sorted, you can do far better. Look at the middle item. If it is too small, the target can only be in the upper half; if too large, in the lower half. Each comparison throws away half of what is left.

def binary_count(items, target):
    lo, hi, comparisons = 0, len(items) - 1, 0
    while lo <= hi:
        mid = (lo + hi) // 2
        comparisons += 1
        if items[mid] == target:
            return True, comparisons
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return False, comparisons

for n in (10, 1000, 1000000):
    data = list(range(n))
    print(n, linear_count(data, -1), binary_count(data, -1))
    

Output, for a target that is not present (the worst case):

10 (False, 10) (False, 3)
1000 (False, 1000) (False, 9)
1000000 (False, 1000000) (False, 19)
    

A thousand times more data costs linear search a thousand times more work, but binary search only a few more steps. That growth pattern is what "Big-O" describes: linear search is O(n), binary search is O(log n). You do not need the maths yet, only the habit of asking how the cost grows when the data does.

The price of binary search

Binary search only works on sorted data. Sorting costs work too, so it pays off when you search many times, not once.

The Hash Shortcut: set and dict

A set and a dict use a hash table: the value is turned into a number that points almost straight at where it is stored, so the lookup does not scan. No sorting is required either. The rule of thumb that follows is one of the most useful in everyday Python: if you ask "is x in here?" more than a few times, use a set or dict, not a list.

import timeit

def measure(n):
    items = list(range(n))
    as_set = set(items)
    return (timeit.timeit(lambda: -1 in items, number=100),
            timeit.timeit(lambda: -1 in as_set, number=100))

for n in (1_000, 100_000):
    t_list, t_set = measure(n)
    print(n, "list is", round(t_list / t_set), "times slower")
    

On the author's machine the gap was roughly 100 times at a thousand items and roughly ten thousand times at a hundred thousand items. Your numbers will differ; what will not differ is that the gap widens as the data grows.

The Front of a Queue: list Versus deque

Removing from the front of a list forces every other item to shuffle along one place, so it costs work proportional to the length. collections.deque (pronounced "deck", a double-ended queue) is built for both ends. For first-in-first-out queues, use it.

from collections import deque

q = deque()
for i in range(3):
    q.append(i)          # join at the back
print(q.popleft(), list(q))   # leave from the front: 0 [1, 2]
    

A decision habit

Before you write a loop that searches or removes, say which operation is most frequent and look it up in the table above. Choosing the structure first usually removes the need to optimise later.

Challenges

Exercise 1

Run linear_count and binary_count on list(range(n)) for n = 100 and n = 100000, searching for a target that is present at the very end (n - 1). Predict the counts first, then compare them with the results.

📄 View solution

Exercise 2

Write dedupe(items) that removes duplicates but keeps the first occurrence of each value in its original order. Make it fast for long inputs, and say which two structures you used and why.

📄 View solution

Exercise 3

A program keeps a queue of waiting jobs held in a list and removes the oldest with pop(0). Rewrite it with deque, then time both for 100,000 jobs. State what you expect before you run it.

📄 View solution

Quick Reference

Count work rather than relying on raw timings
Linear search: O(n); binary search: O(log n), needs sorted data
Membership test: use set or dict, not list
Queue: use deque, not list.pop(0)
Ask first: which operation will my code do most often?

Coming next

Data Structures in Practice 2 looks inside the list: how Python stores it, why appending is cheap on average, and what slicing and copying really cost.