🐍 Day 24: Code Optimization & Complexity Analysis

1. Learning Objectives

By the end of Day 24, you will be able to:

Understand time complexity and space complexity and why they matter
Read and write Big O notation to describe algorithm performance
Use Python's built‑in tools (timeit, cProfile, pstats) to profile and benchmark code
Identify common performance bottlenecks and apply practical optimizations
Choose the right data structure for the job (lists vs. sets vs. dictionaries)
Write memory‑efficient Python code using generators and comprehensions
Apply profiling‑driven optimization rather than premature optimization

2. Concept Explanation

2.1 Why Optimization? – Speed and Scalability

Not all code needs to be blazing fast. But when your program starts to handle thousands (or millions) of records, even small inefficiencies add up. Optimization is about making your code run faster and consume less memory without sacrificing readability (most of the time).

“Premature optimization is the root of all evil.” – Donald Knuth
But informed optimization is the hallmark of an engineer.

We will first learn how to measure performance, then look at algorithmic efficiency, and finally explore practical Python‑specific techniques.

2.2 Measuring Performance – The `timeit` Module

Python’s timeit module runs a snippet of code many times and gives you an average execution time, avoiding measurement noise.

import timeit

code = """
result = 0
for i in range(1000):
    result += i
"""
print(timeit.timeit(code, number=10000))  # Run 10,000 times

In IPython / Jupyter, you can use %timeit magic:

%timeit sum(range(1000))

For larger programs, use the cProfile module to see where time is spent:

python -m cProfile -s cumtime my_script.py

Or programmatically:

import cProfile, pstats

def slow_function():
    total = 0
    for i in range(10000):
        total += i ** 2
    return total

profiler = cProfile.Profile()
profiler.enable()
slow_function()
profiler.disable()
stats = pstats.Stats(profiler).sort_stats("cumtime")
stats.print_stats()

These tools show you the hot spots – the functions where your program spends most of its time.

2.3 Big O Notation – Describing Algorithmic Efficiency

Big O notation expresses how the runtime or memory usage grows relative to the input size n.

Complexity	Notation	Example
Constant	O(1)	Accessing a list element by index
Logarithmic	O(log n)	Binary search
Linear	O(n)	Scanning a list
Linearithmic	O(n log n)	Merge sort
Quadratic	O(n²)	Nested loops (bubble sort)
Exponential	O(2ⁿ)	Recursive Fibonacci (naive)

Visualizing with Python:

def constant_time(n):
    return n * n            # O(1)

def linear_time(n):
    for i in range(n):      # O(n)
        pass

def quadratic_time(n):
    for i in range(n):      # O(n²)
        for j in range(n):
            pass

Why care?
For n = 1,000,000, an O(n²) algorithm does ~10¹² operations – it will take minutes or hours instead of milliseconds.

2.4 Space Complexity – Memory Matters Too

Space complexity measures extra memory used by an algorithm (apart from the input). For example:

A function that creates a new list of size n has O(n) space.
An in‑place sort like list.sort() has O(1) extra space (well, O(log n) for recursion, but it’s called in‑place anyway).
A recursive function that calls itself n times uses O(n) stack space.

Python objects have overhead, so be mindful when storing millions of items.

2.5 Python‑Specific Optimizations

1. Use built‑in functions and standard library

# Slow
total = 0
for x in my_list:
    total += x

# Fast
total = sum(my_list)

Built‑ins are implemented in C and heavily optimized.

2. Choose the right data structure

If you need…	Use
Fast membership test (`in`)	`set` / `dict` (O(1) average)
Ordered collection	`list` / `tuple`
Key‑value mapping	`dict`
Uniqueness	`set`

3. Avoid unnecessary loops – use comprehensions

# Slow
squares = []
for x in range(1000):
    squares.append(x * x)

# Fast
squares = [x * x for x in range(1000)]

List comprehensions are both faster and more readable.

4. Lazy evaluation – generators

When processing large data, use generators to avoid building entire lists in memory (O(1) memory).

5. Cache results – functools.lru_cache

For expensive function calls with repeated arguments, use memoization:

from functools import lru_cache

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

6. Use local variables – they are faster to access than global ones.

7. Avoid + for string concatenation in loops; use ''.join(list).

8. Use collections module for specialized containers (deque, Counter, defaultdict).

2.6 Profiling-Driven Optimization Workflow

Measure – find the slowest parts with cProfile.
Optimize – apply algorithmic or Python‑specific improvements to the hotspots.
Verify – re‑measure to ensure you actually improved performance.
Repeat – only if needed.

Never optimize what you haven’t measured.

3. Code Examples

Example 1: Comparing Membership Tests

import timeit

# List membership (O(n))
list_test = """
my_list = list(range(10000))
result = 9999 in my_list
"""

# Set membership (O(1))
set_test = """
my_set = set(range(10000))
result = 9999 in my_set
"""

print("List:", timeit.timeit(list_test, number=10000))
print("Set:", timeit.timeit(set_test, number=10000))

You’ll see the set version is significantly faster.

Example 2: Cache a Recursive Function

from functools import lru_cache

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

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

# Compare times for n=35

Example 3: Generator vs. List Memory

import sys

# List
big_list = [x for x in range(1_000_000)]
print("List memory:", sys.getsizeof(big_list))

# Generator
big_gen = (x for x in range(1_000_000))
print("Generator memory:", sys.getsizeof(big_gen))

4. Hands-On Exercises

Exercise 1: Timeit Comparison

Write a small script that uses timeit to compare the speed of a list comprehension versus a normal for loop for creating a list of squares from 1 to 10,000.

Exercise 2: Profiling Practice

Create a function that reads a large text file line by line and counts occurrences of each word (case‑insensitive). Use cProfile to profile the function and identify the slowest part.

Exercise 3: Data Structure Choice

Given a list of one million integers, write a function that returns all unique elements. First implement it using only lists (if x not in list) and measure the time with timeit. Then rewrite using a set and compare the times.

Exercise 4: Space Complexity Analysis

Examine this code and determine its space complexity in Big O notation. Then suggest an improvement.

def duplicate_list(items):
    new_list = []
    for item in items:
        new_list.append(item)
    return new_list

Exercise 5: Optimize a Simple Function

The following function calculates the sum of the first n squares. It works correctly but is inefficient. Optimize it using built‑ins and measure the improvement.

def sum_squares(n):
    total = 0
    i = 1
    while i <= n:
        total = total + i * i
        i = i + 1
    return total

5. Applied Challenge Task 🏗️

Performance‑Tuned Text Analyzer

You’re given a directory containing multiple large text files (simulate them). Build a command‑line tool that:

Reads all .txt files in the directory.
Tokenizes all words (case‑insensitive).
Counts the frequency of each word across all files.
Reports the top 10 most common words and their counts.
Measures and displays total execution time and peak memory usage.

Optimization requirements:

Use generators to read files line‑by‑line (avoid loading entire files into memory).
Use collections.Counter or a dictionary to count.
Use time.perf_counter() for timing and tracemalloc or psutil to get memory usage.
Profile the initial naive implementation, then optimize using the techniques learned today.

Stretch goals:

Implement a concurrent version using concurrent.futures to process files in parallel.
Compare performance of Counter vs. manually incrementing a defaultdict.

6. Brief Review Summary

Concept	Key Points
Big O notation	Describes how runtime/memory grows with input size
Common complexities	O(1), O(log n), O(n), O(n log n), O(n²)
`timeit`	Micro‑benchmark small code snippets
`cProfile`	Identify bottlenecks in larger programs
Python optimizations	Use built‑ins, comprehensions, sets/dicts, generators, caching
Workflow	Measure → Optimize → Verify
Premature optimization	Don’t guess – measure first!

7. Preview of Next Topic — Day 25

Tomorrow we dive into the heart of computer science:

Data Structures and Algorithms in Python – not just theory, but practical implementations
Stacks, queues, linked lists, hash maps
Recursion, sorting, searching algorithms
When to roll your own vs. use the standard library

🎯 Your Action Items for Day 24:

✅ Complete all 5 exercises
✅ Build the Performance‑Tuned Text Analyzer
✅ Use cProfile on one of your previous projects and find a hotspot
✅ Memorize the Big O complexities of common Python operations

Search This Blog

Python Adventures