Reuse Earlier Results with cache and lru_cache

A recursive Fibonacci function repeats the same work many times. Computing fib(30) the plain way runs the function 2,692,537 times. Add @cache and it runs 31 times:

from functools import cache

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

print(fib(30))           # 832040
print(fib.cache_info())  # CacheInfo(hits=28, misses=31, maxsize=None, currsize=31)

A cache stores results so that later calls can reuse them. The @cache decorator keeps a dictionary from arguments to results. When you call fib(10), it looks up 10. On a hit, the result is already there, and it returns the result at once. On a miss, it runs the function and stores the result. Caching a function's results this way is also called memoization.

Choose cache or lru_cache

The @cache decorator keeps every result until the program ends or you call fib.cache_clear(). Use it when the set of possible arguments is small, as it is for fib.

The @lru_cache(maxsize=128) decorator keeps at most 128 results. When it is full, it throws out the least recently used one, hence the name LRU. Use it when callers keep sending new arguments, as in a long-running web service, so the cache cannot grow without limit. The limit counts results, not bytes, so 128 large results still take a lot of memory. Writing @cache is the same as writing @lru_cache(maxsize=None).

Put a typed function in front of the cache

mypy checks less on a cached function. It checks the return type, and it rejects a list argument, but it does not check the parameter types. So fib("nope") and fib() pass mypy and fail only when they run.

Keep the cache on a private helper, and give callers a plain function with full types. That function can also check its input:

from functools import cache

@cache
def _fibonacci(n: int) -> int:
    return n if n < 2 else _fibonacci(n - 1) + _fibonacci(n - 2)

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be 0 or more")
    return _fibonacci(n)

print(fibonacci(30))  # 832040

Now mypy checks every call to fibonacci, and the cache stays a private detail. The exercise uses this shape.

Check your understanding The exercise's public function is edit_distance(a: object, b: object). Why object and not str? Show answer

Its job includes rejecting bad input. The tests send numbers, lists and None, and expect a TypeError for each one. With object parameters, solve can pass any value, and an isinstance check inside rejects the wrong ones and tells mypy that the rest are strings. When all your callers have type annotations, use str instead, and mypy rejects wrong calls before the code runs.

Common mistakes

Passing a list. The arguments become dictionary keys, so each one must be hashable. A list argument raises TypeError: unhashable type: 'list'. Pass a tuple instead.

Caching a function with side effects. A cached function that sends an email sends it only on a miss. Cache only functions whose result depends on their arguments alone.

Check your understanding You cache load_tags(user_id: int) -> list[str]. One caller appends a tag to the list it gets back. What does the next caller see? Show answer

The extra tag. The cache stored that list object, and it hands the same object to every caller with the same user_id. Return a tuple[str, ...] instead, so no caller can change the cached value.

Use it for edit distance

The exercise computes edit distance, the fewest one-character insertions, deletions and substitutions that turn one string into another. A recursive version compares the first characters and recurses on the rest of the strings. The same pairs of string endings come up again and again, and there are at most (len(a) + 1) * (len(b) + 1) different pairs, so a cache makes it fast.

Two limits apply. Each recursive call goes one level deeper, and Python stops at about 1,000 levels by default, so this approach suits short strings. A loop that fills in a table handles long ones. And a module-level cache keeps every string ending it has seen until the program ends or you clear it.

Going further

The cache keeps its own data consistent when several threads call the function at once. Two threads that miss on the same arguments at the same time can still both run it. So a cache does not promise to compute each result only once. The concurrency track covers threads.