Exercises - Performance optimisation

Built-ins vs Manual Loops

Exercise 1 — 🟢 Beginner Replace the manual loop with the appropriate built-in and measure the improvement using timeit:

data = list(range(10_000))

# ❌ manual loop
def manual_max(lst):
    result = lst[0]
    for x in lst:
        if x > result:
            result = x
    return result

# ✅ rewrite using a built-in
# expected:
# manual_max : ~0.5s
# built-in   : ~0.05s  ← 10x faster

Exercise 2 — 🟢 Beginner Replace the manual loop with any() and all() and verify they short-circuit correctly:

data = list(range(10_000))

# ❌ manual loops
def manual_any(lst, threshold):
    for x in lst:
        if x > threshold:
            return True
    return False

def manual_all(lst, threshold):
    for x in lst:
        if x < threshold:
            return False
    return True

# ✅ rewrite using any() and all()
# verify short-circuiting:
# any() should stop at the first element greater than threshold
# all() should stop at the first element less than threshold

# hint: add a print() inside a generator to verify early stopping
# any(print(x) or x > 5000 for x in data)

Exercise 3 — 🟡 Intermediate Measure the performance difference between "".join() and += for building a string, then explain why the gap grows with input size:

parts = ["word"] * 10_000

# ❌ += concatenation
def bad_concat(parts):
    result = ""
    for p in parts:
        result += p
    return result

# ✅ join
def good_concat(parts):
    return "".join(parts)

# tasks:
# 1. measure both with timeit for parts of size 1_000, 5_000, 10_000
# 2. does the gap grow linearly or faster as size increases?
# 3. explain why in terms of O(n) vs O(n²)

---

String Concatenation

Exercise 4 — 🟢 Beginner Rewrite these string concatenations using f-strings and verify the output is identical:

name  = "Alice"
age   = 30
score = 95.5

# ❌ manual concatenation
s1 = "Name: " + name + ", Age: " + str(age) + ", Score: " + str(score)
s2 = "Hello " + name + "! You scored " + str(score) + " out of 100."

# ✅ rewrite using f-strings
# verify:
# s1 == f_s1  → True
# s2 == f_s2  → True

Exercise 5 — 🟡 Intermediate Build a function that generates a large report string. Compare three approaches and measure each with timeit:

rows = [{"name": f"user_{i}", "score": i} for i in range(1_000)]

# approach 1 — += concatenation
def report_concat(rows):
    result = ""
    for row in rows:
        result += f"{row['name']}: {row['score']}\n"
    return result

# approach 2 — join with list
def report_join(rows):
    return "".join(f"{row['name']}: {row['score']}\n" for row in rows)

# approach 3 — join with list comprehension
def report_list_join(rows):
    return "".join([f"{row['name']}: {row['score']}\n" for row in rows])

# expected:
# concat    : X.XXXs  ← slowest
# join      : X.XXXs
# list_join : X.XXXs  ← likely fastest
# all three produce identical output — verify this

---

Data Structure Choice

Exercise 6 — 🟢 Beginner Measure the lookup time difference between a list and a set for different positions of the needle — best case (first element), middle, and worst case (last element):

import timeit

size = 1_000_000
lst  = list(range(size))
st   = set(range(size))

first  = 0              # best case for list
middle = size // 2      # middle case
last   = size - 1       # worst case for list

# tasks:
# 1. measure lst lookup for first, middle, last
# 2. measure st  lookup for first, middle, last
# 3. does position affect set lookup time?
# 4. does position affect list lookup time?
# expected:
# list first  : X.XXXs  ← fast   (found immediately)
# list middle : X.XXXs  ← slower (scans half the list)
# list last   : X.XXXs  ← slowest (scans entire list)
# set first   : X.XXXs  ← same
# set middle  : X.XXXs  ← same
# set last    : X.XXXs  ← same  (position irrelevant)

Exercise 7 — 🟡 Intermediate You are given a list of user IDs to check against a large dataset. Rewrite the lookup to use the correct data structure and measure the improvement:

import timeit

# large dataset
all_users = list(range(1_000_000))

# ids to check
to_check = [999_999, 500_000, 0, 123_456, 999_998]

# ❌ list lookup — O(n) per check
def check_users_list(to_check, all_users):
    return [uid for uid in to_check if uid in all_users]

# ✅ rewrite using the correct data structure
# expected:
# list version : X.XXXs  ← slow
# fixed version: X.XXXs  ← much faster
# both return identical results — verify this

Exercise 8 — 🟡 Intermediate Choose the correct data structure for each of these scenarios and explain your choice:

# scenario 1 — store a playlist of songs in order
songs = ["Bohemian Rhapsody", "Hotel California", "Stairway to Heaven"]
# which structure? list / set / dict — why?

# scenario 2 — track which users have logged in today
logged_in = ["alice", "bob", "charlie"]
# which structure? list / set / dict — why?
# hint: you only need to answer "has alice logged in?"

# scenario 3 — store user profiles keyed by user ID
profiles = [(1, "Alice"), (2, "Bob"), (3, "Charlie")]
# which structure? list / set / dict — why?

# scenario 4 — find unique words in a document
words = "the quick brown fox jumps over the lazy dog".split()
# which structure? list / set / dict — why?

---

Local Variables

Exercise 9 — 🟢 Beginner Rewrite this function to cache the global lookup as a local variable and measure the improvement:

import math
import timeit

# ❌ global lookup on every iteration
def slow_sqrt(n):
    result = 0
    for i in range(n):
        result += math.sqrt(i)
    return result

# ✅ cache as local variable
def fast_sqrt(n):
    # your implementation here
    pass

# expected:
# slow_sqrt : ~1.2s
# fast_sqrt : ~0.8s  ← ~33% faster

Exercise 10 — 🟡 Intermediate This function makes multiple global lookups inside the loop. Cache all of them as local variables and measure the total improvement:

import math
import timeit

# ❌ multiple global lookups on every iteration
def slow_compute(n):
    result = []
    for i in range(1, n):
        result.append(math.sqrt(i) + math.log(i) + math.floor(i))
    return result

# ✅ cache all global lookups as local variables
def fast_compute(n):
    # your implementation here
    pass

# expected:
# slow_compute : X.XXXs
# fast_compute : X.XXXs  ← measurably faster
# both return identical results — verify this

---

Generator vs List

Exercise 11 — 🟢 Beginner Rewrite these list comprehensions as generator expressions where appropriate and verify the results are identical:

import sys

data = range(1_000_000)

# rewrite as generator where it makes sense
total   = sum([x**2 for x in data])        # feeds directly into sum()
maximum = max([x**2 for x in data])        # feeds directly into max()
first5  = list([x**2 for x in data])[:5]  # needs a list — keep as list?

# for each rewrite:
# 1. verify the result is identical
# 2. measure memory with sys.getsizeof()
# 3. is a generator always the right choice?

Exercise 12 — 🟡 Intermediate Measure both the time and memory difference between a generator and a list for processing a large dataset:

import sys
import timeit
import tracemalloc

data = range(1_000_000)

# approach 1 — list comprehension
def with_list():
    return sum([x**2 for x in data])

# approach 2 — generator expression
def with_generator():
    return sum(x**2 for x in data)

# tasks:
# 1. measure time with timeit for both
# 2. measure peak memory with tracemalloc for both
# 3. are the results identical?
# 4. which trades time for memory and which trades memory for time?

Exercise 13 — 🟡 Intermediate Identify which of these cases benefit from a generator and which require a list, then explain why:

data = range(1_000_000)

# case 1 — feeding into sum()
result = sum([x**2 for x in data])

# case 2 — accessing by index
result = [x**2 for x in data][500_000]

# case 3 — iterating twice
squares = [x**2 for x in data]
total   = sum(squares)
maximum = max(squares)

# case 4 — passing to a function that iterates once
result = ",".join(str(x**2) for x in range(1_000))

# for each case:
# 1. can it be replaced with a generator?
# 2. what would break if you used a generator?
# 3. what is the memory saving if you do use a generator?

---

Combined Exercises

Exercise 14 — 🔴 Advanced This function has multiple performance problems. Use cProfile to find them, fix each one using the patterns from this section, and measure the total improvement:

import math

def analyse(data):
    # problem 1 — wrong data structure for membership testing
    seen = []
    unique = []
    for x in data:
        if x not in seen:
            seen.append(x)
            unique.append(x)

    # problem 2 — global lookup in tight loop
    result = []
    for x in unique:
        result.append(math.sqrt(x))

    # problem 3 — string concatenation
    report = ""
    for x in result:
        report += f"{x:.2f}\n"

    return report

data = list(range(10_000)) * 3  # contains duplicates

# tasks:
# 1. profile with cProfile — identify all bottlenecks
# 2. fix problem 1 — wrong data structure
# 3. fix problem 2 — global lookup
# 4. fix problem 3 — string concatenation
# 5. measure total improvement with timeit
# 6. verify output is identical before and after

Exercise 15 — 🔴 Advanced Build a benchmark suite that tests all five optimisation patterns on the same dataset and produces a summary report:

import timeit
import sys

data = list(range(10_000))

# benchmark all patterns:
# 1. manual loop vs built-in sum()
# 2. += vs join() for string building
# 3. list vs set for membership testing
# 4. global vs local variable lookup
# 5. list comprehension vs generator for sum()

# expected output:
# ┌─────────────────────────────────────────────────────┐
# │ Pattern              Slow        Fast    Improvement │
# ├─────────────────────────────────────────────────────┤
# │ built-ins            0.500s     0.050s      10.0x   │
# │ string concat        1.200s     0.080s      15.0x   │
# │ data structure       2.500s     0.000s   25000.0x   │
# │ local variables      1.200s     0.800s       1.5x   │
# │ generator vs list    0.300s     0.280s       1.1x   │
# └─────────────────────────────────────────────────────┘

---

Try fixing each exercise without looking at the solution first — the goal is to build the instinct for recognising these patterns in your own code, so that profiling results immediately suggest the right fix.