Memoisation with cache and lru_cache

Memoisation turns exponential recursions into linear ones and avoids repeating expensive lookups.

Memoisation stores a function's results by arguments, so repeated calls with the same arguments return instantly. functools provides it as decorators:

@cache (3.9+) an unbounded cache. Simple and fast.
@lru_cache(maxsize=128) a bounded cache that evicts the least recently used entry when full. maxsize=None makes it unbounded, like cache.

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

Without the cache, fib(35) makes about 30 million calls; with it, 36.

Requirements and rules:

Only cache pure functions: the same arguments must always give the same result, with no side effects that matter. Caching datetime.now() or a database read gives stale data.
Arguments must be hashable: passing a list raises TypeError. Convert to a tuple first.
f(1, 2) and f(1, b=2) are cached separately because the arguments differ in form.
The decorated function gains cache_info() (hits, misses, sizes) and cache_clear().

Cached results are returned as the same object each time. If callers mutate a returned list or dict, they corrupt the cache for everyone; return immutable values (tuples, frozensets) from cached functions.

Example

from functools import cache, lru_cache

calls = 0
@cache
def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80), calls)            # 23416728348467685 81
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

@lru_cache(maxsize=2)
def lookup(code):
    print("computing", code)
    return code.upper()
lookup("a"); lookup("b"); lookup("a"); lookup("c"); lookup("b")
# computing a / computing b / computing c / computing b
try:
    fib([1])
except TypeError as e:
    print(e)                     # unhashable type: 'list'

Remember

@cache memoises without limit; @lru_cache(maxsize=n) evicts least recently used
Only cache pure functions with hashable arguments
Use cache_info() to check hit rates and cache_clear() to reset

Watch out for

Caching a function that returns a mutable list, then mutating the returned value.

Check yourself

@cache is applied to a function that reads a config file. What goes wrong when the file changes?

Official docs: docs.python.org/3/library/functools.html#functools.cache

Example

Remember

Watch out for

Check yourself

Builds on

Unlocks