Using @functools.lru_cache to Speed Up Dynamic‑Programming Algorithms in thealgorithms

Quick answer

Apply @functools.lru_cache(maxsize=None) (or @functools.cache in Python 3.9+) to any pure function whose results depend only on its arguments. The decorator stores each unique call‑argument pair and returns the cached value on subsequent calls, turning exponential‑time recursive algorithms into linear‑time look‑ups.

Worked example: Fibonacci with memoization

The naïve recursive Fibonacci recomputes the same sub‑problems many times. Adding @lru_cache eliminates the duplication.

import functools
import time

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

# Demo: measure time for n = 35
start = time.perf_counter()
result = fib(35)
elapsed = time.perf_counter() - start
print(f'fib(35) = {result}, took {elapsed:.6f}s')
# After the call, inspect cache info
print(fib.cache_info())

Running the snippet shows a dramatic drop in execution time compared with the same function without the decorator. The cache_info() output displays hits, misses, maxsize and current size, letting you verify that caching is working.

How the mechanism works

• When the decorated function is called, Python first looks up the argument tuple in an internal dictionary.
• If a match is found (a cache hit), the stored result is returned immediately.
• Otherwise (cache miss) the original function runs, its result is stored, and then returned.
• The cache lives for the lifetime of the process; each distinct argument combination consumes memory.

Limits and common pitfalls

Memory growth

With maxsize=None the cache retains every unique call. For algorithms that can receive a huge variety of inputs (e.g., a function that takes a large list as argument), memory usage can grow unbounded. Fix: set a reasonable maxsize (e.g., @lru_cache(maxsize=1024)) or periodically clear the cache with fib.cache_clear().

Unhashable arguments

The decorator requires all arguments to be hashable. Passing a list, dict, or set raises a TypeError. Convert mutable arguments to an immutable form before caching, e.g., @lru_cache def count_ways(amount, coins): where coins is a tuple.

Side effects

If the cached function performs I/O, updates global state, or relies on random numbers, caching will suppress those effects after the first call. Ensure the function is pure (output depends only on inputs) before applying @lru_cache.

Overhead for tiny inputs

For very cheap functions (e.g., a simple arithmetic operation) the dictionary lookup may cost more than the computation itself. Profile with time.perf_counter() to confirm a net gain.

Thread‑safety considerations

The built‑in LRU cache is thread‑safe for concurrent reads and writes, but under high contention it can become a bottleneck. In Python 3.9+ prefer @functools.cache (unbounded) or implement a custom lock‑striped cache if you need higher throughput.

Practical verification steps

1. Time the function with and without the decorator for a representative input range (e.g., Fibonacci 30‑50) using time.perf_counter().
2. After a series of calls with many distinct arguments, check sys.getsizeof(function.__wrapped__) or the cache’s internal size via function.cache_info() to observe memory growth.
3. Run the function from multiple threads (using threading.Thread) and log hits vs. misses; hits should increase without errors, confirming thread‑safety.