functools: lru_cache, partial, reduce
Overview
`functools` bundles higher-order helpers. Three carry their weight: from functools import lru_cache, partial, reduce @lru_cache(maxsize=None) # memoize: cache results by args def fib(n): return n if n < 2 else fib(n-1) + fib(n-2) int2 = partial(int, base=2) # freeze an argument -> new callable int2('1010') # 10 reduce(lambda a, b: a*b, [1,2,3,4]) # 24 — fold a sequence to one value `lru_cache` turns exponential recursions (naive Fibonacci, top-down DP) into linear by remembering each result — the single most useful one. `partial` pre-binds arguments to make specialized callables (great for callbacks). `reduce` folds a sequence with a binary function, though an explicit loop or `sum`/`math.prod` is often clearer. Constraint: `lru_cache` requires **hashable** arguments, so it can't cache a function called with a list or dict.
Memoization is the difference between an O(2^n) and an O(n) solution — it's the backbone of top-down dynamic programming, which your DSA track leans on. partial and reduce round out a functional-style toolkit that shows up in real codebases.
Where used: Top-down dynamic programming (memoization), Caching expensive pure computations, Pre-binding arguments for callbacks (partial)
Why learn this
- `@lru_cache` converts exponential recursive solutions into linear ones — the core trick behind top-down DP.
- partial and reduce are common functional patterns you'll read in real code and use for callbacks and folds.
Code walkthrough
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
print(fib(30))
print(fib.cache_info())Focus: fib.cache_info() (hits show subproblems were reused, not recomputed)
Common mistakes
- Caching a function with unhashable arguments: `lru_cache` keys the cache on the arguments, so they must be hashable. Calling an lru_cached function with a `list` or `dict` raises `TypeError: unhashable type`. Pass tuples/frozensets instead.
- Memoizing an impure function: `lru_cache` returns the stored result for repeat args and never re-runs the body. If the function depends on time, randomness, or external state, you'll get stale answers. Only cache pure functions.
- Unbounded cache growth: `maxsize=None` caches every distinct argument forever, which can leak memory for functions called with many unique inputs. Use a finite `maxsize` (default 128) when the input space is large.
Glossary
- memoization
- Caching a function's results by its arguments so repeat calls with the same inputs return instantly. `@lru_cache` does this automatically.
Recall questions
- How does `@lru_cache` change the time complexity of naive recursive Fibonacci, and why?
- Why can't you call an `lru_cache`-decorated function with a list argument?
- What does `functools.partial(f, x)` return?
Understanding checks
A developer decorates `def now(): return datetime.now()` with `@lru_cache`. Why does it always return the same time after the first call?
lru_cache stores the first result and returns it for every later call with the same (here, empty) arguments, never re-executing the body.
Memoization assumes the function is pure — output depends only on arguments. `now()` depends on the clock (external state), so caching freezes it at the first value. Don't cache impure functions.
Why does this raise a TypeError?
The argument `[1, 2, 3]` is a list, which is unhashable, and lru_cache must hash arguments to key the cache.
lru_cache stores results keyed by arguments, requiring them to be hashable. A list can't be hashed; passing a tuple `(1, 2, 3)` would work.
Practice tasks
Memoize an expensive recursion
Add `@lru_cache` to the recursive `count_paths` grid-walk function so repeated subproblems aren't recomputed, then print `count_paths(15, 15)` (which is far too slow without caching).
Continue learning
Previous: Function Decorators