Profiling, complexity & caching

Make it fast: measure, then fix the right thing

Slow code costs money and latency in production, and the human instinct for where it is slow is almost always wrong. Engineers waste hours micro-optimizing a loop that runs once while an accidental O(n²) scan buried three functions away eats the request budget. The discipline is: measure first, fix algorithmic complexity, then cache repeated work. Only after that do you tune lines.

Profile before you touch anything

cProfile runs your code and reports, per function, how many times it was called and how much time it took. timeit runs a tiny snippet many times for a stable microbenchmark.

import cProfile
cProfile.run("slow_function()")
# ncalls  tottime  cumtime  filename:lineno(function)
#  1  0.002  0.900  app.py:12(slow_function)
# 900000  0.850  0.850  app.py:30(lookup)   <- the real hot path

Read tottime (time in that function itself) and ncalls. A function called 900,000 times is your target, not the one that merely looks heavy.

Complexity is the biggest lever

No micro-tuning beats a better data structure. A set and a dict are hash maps: membership is average O(1). A list scan is O(n).

if x in big_set:    # O(1) average
if x in big_list:   # O(n), linear scan every time

Turning an O(n²) nested loop into an O(n) pass with a set lookup is the difference between a request that returns and one that times out.

Memory is a lever too: __slots__

By default every instance carries its own __dict__, a hash map holding its attributes. That is what makes obj.anything = 1 work at runtime, and it costs memory on every object you create. Declaring __slots__ replaces that dict with a fixed set of descriptors:

class Point:
    __slots__ = ("x", "y")

    def __init__(self, x, y):
        self.x = x
        self.y = y

Measured on CPython 3.11 for a two-attribute object, sys.getsizeof reports 48 bytes with __slots__ against 56 bytes plus a separate per-instance dict without it. Across a million objects that gap is the difference between fitting in memory and not. Attribute access also gets slightly faster, because it is an array offset rather than a dict lookup.

The cost is flexibility, and it is worth naming precisely:

• Assigning an undeclared attribute raises AttributeError, not a silent success. That is often a feature: typos in attribute names become errors instead of new attributes.
• There is no __dict__, so code that introspects one (some serializers, some mocking) breaks.
• A subclass that does not declare its own __slots__ gets a __dict__ back, and the saving with it.

Reach for it when you have many small, fixed-shape objects (points, rows, events, graph nodes). Skip it for the handful of long-lived service objects, where the memory is irrelevant and the flexibility is not.

Interview nuance: CPython already softens the default case with key-sharing dictionaries (PEP 412): instances of the same class share one copy of their key layout, so the marginal per-instance dict is smaller than a standalone dict of the same size. That is why the honest claim is "slots remove the per-instance dict entirely", not a fixed multiplier. If someone quotes you a flat "slots saves 50 percent", the useful follow-up is: measured on which Python, with how many attributes, and against shared keys or not?

Cache repeated work with lru_cache

When a pure function is called repeatedly with the same arguments, functools.lru_cache stores results keyed by the arguments. Naive fib recomputes fib(n-1) and fib(n-2) down overlapping trees, so it runs in roughly O(φⁿ) time, where φ ≈ 1.618 is the golden ratio (fib(35) already triggers tens of millions of calls). Memoization computes each distinct n exactly once:

from functools import lru_cache

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

print(fib(10))   # 55
print(fib(30))   # 832040, instant thanks to the cache

@lru_cache(maxsize=None) keeps every result; in Python 3.9+ the shorthand is @functools.cache. This is exactly what the exercises ask for: a memoized fib where each n is computed once.

Generators for memory

A generator streams values instead of building a list, so it uses constant memory over huge sequences:

total = sum(x * x for x in range(10_000_000))   # no 10M-element list

Pitfalls

• lru_cache keys on the arguments, so every argument must be hashable. fib(2) is fine; passing a list or dict raises TypeError: unhashable type.
• With maxsize=None the cache never evicts. That is perfect for fib, but calling a cached function with millions of distinct arguments leaks memory.
• Recursive fib recurses n frames deep, so a cold fib(3000) hits Python's default recursion limit (RecursionError) before the cache helps. Warm it incrementally (fib(500), then fib(1000), ...) so each call only recurses to the first uncached n, or convert to a loop.

Interview nuance: memoization works because fib has overlapping subproblems. There are only n + 1 distinct inputs (0 through n), each solved once, so the cache collapses exponential time to O(n) time and O(n) space. Being able to name that space cost, and the recursion-depth limit, is what separates "I added a decorator" from understanding why it works.