Performance, Big-O and the collections module

In this lesson you will learn

Read Big-O notation and know the cost of list, dict and set operations
Measure code speed with timeit and cProfile
Use Counter, defaultdict, deque, namedtuple and itertools where they fit

A program checks 100 000 orders against a list of 100 000 blocked customers. With a list it runs for tens of seconds; change one line to use a set, and it finishes in a fraction of a second. Speed in Python rarely comes from clever tricks — it comes from choosing the right data structure and algorithm and from measuring instead of guessing. This lesson gives you the tools for both.

Big-O: how the time grows

Big-O notation describes how the running time of an operation grows with the size of the data n, ignoring constant factors. O(1) — constant: it does not depend on n. O(log n) — grows very slowly (binary search). O(n) — proportional to n (one pass over a list). O(n log n) — good sorting. O(n²) — nested loops over the same data: 10 times more data means 100 times more work.

Operation	list	dict / set
`x in c`	O(n)	O(1)
access by index / key	O(1)	O(1)
`append`, `add`, `d[k] = v`	O(1)*	O(1)
`insert(0, x)`, `pop(0)`	O(n)	—
`pop()` from the end	O(1)	—
`sorted(c)`	O(n log n)	O(n log n)

* amortized, i.e. on average; the dict and set figures are the average case.

Why are dict and set so fast? They are hash tables: hash(key) tells almost directly where the element is stored, so in does not scan the data. A list has no such index and has to compare the elements one by one. And inserting at the start of a list shifts all the other elements, which is why insert(0, x) and pop(0) are O(n).

Measure, don't guess: timeit and cProfile

timeit runs a small piece of code many times and returns the total time, which smooths out random noise. Let's compare membership tests in a list and in a set of 100 000 numbers:

Python· Edit the code and run it again

import timeit

setup = 'data_list = list(range(100_000)); data_set = set(data_list)'
t_list = timeit.timeit('99_999 in data_list', setup=setup, number=200)
t_set = timeit.timeit('99_999 in data_set', setup=setup, number=200_000) / 1000
print(f'list: {t_list * 1000:.2f} ms for 200 lookups')
print(f'set:  {t_set * 1000:.4f} ms for 200 lookups')
print(f'the set is about {t_list / t_set:,.0f} times faster')

Typically the set turns out thousands of times faster; the exact numbers depend on the computer.

When a whole program is slow, find out where the time goes before changing anything. cProfile counts every function call and the time spent in it. Run it on a script from the command line and sort the report by cumulative time:

Terminal

$ python -m cProfile -s cumulative slow.py
28656
         92741 function calls (51 primitive calls) in 0.019 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.019    0.019 {built-in method builtins.exec}
        1    0.000    0.000    0.019    0.019 slow.py:1(<module>)
        1    0.000    0.000    0.019    0.019 slow.py:4(main)
        1    0.000    0.000    0.019    0.019 {built-in method builtins.sum}
       23    0.000    0.000    0.019    0.001 slow.py:5(<genexpr>)
 92712/22    0.019    0.000    0.019    0.001 slow.py:1(fib)

slow.py sums the Fibonacci numbers from 0 to 21 with naive recursion. The times depend on the computer; the call counts do not.

92712/22 means 92 712 calls in total, of which only 22 came from outside (the rest are recursive). The profiler can also be used from code; here we read only the call counts — and see how lru_cache from the lesson on decorators turns tens of thousands of calls into 21:

Python· Edit the code and run it again

import cProfile
import pstats
from functools import lru_cache

def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

@lru_cache(maxsize=None)
def fib_cached(n):
    return n if n < 2 else fib_cached(n - 1) + fib_cached(n - 2)

for func in (fib, fib_cached):
    profiler = cProfile.Profile()
    profiler.runcall(func, 20)
    stats = pstats.Stats(profiler).stats
    calls = sum(v[1] for (_, _, name), v in stats.items() if name == func.__name__)
    print(f'{func.__name__}(20): {calls} calls')

▸ Expected output

fib(20): 21891 calls
fib_cached(20): 21 calls

The collections module

**Counter** is a dictionary for counting: give it any iterable and it counts the elements. most_common(n) returns the n most frequent ones; a missing key gives 0 instead of KeyError; counters can even be added and subtracted:

Python· Edit the code and run it again

from collections import Counter

words = Counter('the cat and the hat and the bat'.split())
print(words.most_common(2))
print(words['the'], words['dog'])

votes = Counter(['plov', 'dolma', 'plov', 'kebab', 'plov', 'dolma'])
print(votes)
print(votes + Counter(['kebab', 'kebab']))

▸ Expected output

[('the', 3), ('and', 2)]
3 0
Counter({'plov': 3, 'dolma': 2, 'kebab': 1})
Counter({'plov': 3, 'kebab': 3, 'dolma': 2})

**defaultdict** creates a missing value automatically on first access, using the factory you pass: list, int, set. It is perfect for grouping. Be careful: even reading a missing key adds it to the dictionary:

Python· Edit the code and run it again

from collections import defaultdict

students = [('Aysel', '9A'), ('Murad', '9B'), ('Leyla', '9A'), ('Elvin', '9B'), ('Nigar', '9A')]
by_class = defaultdict(list)
for name, group in students:
    by_class[group].append(name)
print(dict(by_class))
print(by_class['10C'], len(by_class))

▸ Expected output

{'9A': ['Aysel', 'Leyla', 'Nigar'], '9B': ['Murad', 'Elvin']}
[] 3

by_class['10C'] created an empty group — the dictionary's length became 3.

**deque** (double-ended queue) adds and removes items at both ends in O(1), while for a list removing from the start is O(n). With maxlen it keeps only the last n items — ideal for “recently viewed” lists and sliding windows. **namedtuple** creates a light, immutable tuple whose fields also have names:

Python· Edit the code and run it again

from collections import deque, namedtuple

queue = deque(['Aysel', 'Murad'])
queue.append('Leyla')
queue.appendleft('Elvin')
print(queue.popleft(), queue)

recent = deque(maxlen=3)
for page in ['home', 'lessons', 'python', 'quiz', 'profile']:
    recent.append(page)
print(list(recent))

Point = namedtuple('Point', ['x', 'y'])
p = Point(3, 4)
print(p, p.x, p[1], p._replace(x=10))

▸ Expected output

Elvin deque(['Aysel', 'Murad', 'Leyla'])
['python', 'quiz', 'profile']
Point(x=3, y=4) 3 4 Point(x=10, y=4)

itertools and Pythonic speed

**itertools** is a set of fast, lazy building blocks for loops, written in C: joining sequences (chain), running totals (accumulate), neighbouring pairs (pairwise), combinations and Cartesian products, grouping:

Python· Edit the code and run it again

from itertools import accumulate, chain, combinations, groupby, pairwise, product

print(list(chain([1, 2], (3, 4), 'ab')))
print(list(accumulate([5, 3, 8, 2])))
print(list(pairwise([10, 12, 15, 11])))
print(list(combinations('ABC', 2)))
print(len(list(product(range(10), repeat=4))))
fruits = sorted(['cherry', 'apple', 'blueberry', 'avocado', 'banana'])
print({k: list(g) for k, g in groupby(fruits, key=lambda w: w[0])})

▸ Expected output

[1, 2, 3, 4, 'a', 'b']
[5, 8, 16, 18]
[(10, 12), (12, 15), (15, 11)]
[('A', 'B'), ('A', 'C'), ('B', 'C')]
10000
{'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry'], 'c': ['cherry']}

Python· Edit the code and run it again

numbers = [1, 2, 2, 3, 4, 4, 5]
for n in numbers:
    if n % 2 == 0:
        numbers.remove(n)
print(numbers)

numbers = [1, 2, 2, 3, 4, 4, 5]
numbers = [n for n in numbers if n % 2 != 0]
print(numbers)

▸ Expected output

[1, 2, 3, 4, 5]
[1, 3, 5]

Exercise

Print the 3 most frequent words of the text in the format word: count. Letter case and punctuation must be ignored. Use Counter.

Exercise · Python· Edit the code and run it again

from collections import Counter
import re

text = '''Python is fast to write. Python is fun.
Fast code is good, but correct code is better.'''
# 1) turn the text into a list of lower-case words
# 2) print the 3 most common words as 'word: count'

▸ Expected output

is: 4
python: 2
fast: 2

Exercise

Print the IDs that occur more than once, in ascending order, and then the number of unique IDs. Use a single pass with sets (O(n)), not nested loops (O(n²)).

Exercise · Python· Edit the code and run it again

ids = [105, 230, 105, 999, 412, 230, 7, 105]
seen = set()
duplicates = set()
# one pass: if an id is already in seen, it is a duplicate

print(sorted(duplicates))
print(len(seen), 'unique ids')

▸ Expected output

[105, 230]
5 unique ids

Key points

Big-O shows how time grows with n; avoid hidden O(n²), such as in on a list inside a loop.
in on a set or dict is O(1) on average and O(n) on a list; insert(0, x) and pop(0) on a list are O(n) — use deque.
Measure with timeit and cProfile before optimising.
Counter counts, defaultdict groups, deque is a fast queue, and namedtuple gives tuple fields names.
itertools provides lazy tools; groupby needs sorted data; never modify a list while iterating over it.

Check yourself

10 questions. Every correct answer earns XP.

1 / 10

What is the average cost of x in s for a set of n elements?