Memoization is an optimization technique that speeds up programs by caching the results of previous function calls. This allows subsequent calls to reuse the cached results, avoiding time-consuming recalculation.
Memoization is commonly used in dynamic programming, where problems can be broken down into simpler sub-problems. One such dynamic programming problem is calculating the nth Fibonacci number.
The Fibonacci numbers are a sequence of integers where each number is the sum of the two preceding numbers, starting with the numbers 0 and 1.
F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2)
A function that calculates the nth Fibonacci number is often implemented recursively.
def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)
The function calls of
can be visualized with a recursion tree.
Notice that the function is called with the same input multiple times. Particularly
is calculated from scratch twice. As the input increases, the running time grows exponentially. This is suboptimal and can be improved significantly using memoization.
Memoization in Python
Python 3 makes it incredibly easy to memorize functions. The functools module included in Python’s standard library provides two useful decorators for memoization:
(new in Python 3.2) and
(new in Python 3.9). These decorators use a least recently used (LRU) cache, which stores items in order of use, discarding the least recently used items to make room for new items.
To avoid costly repeated function calls,
can be wrapped by
, which saves values that have already been calculated. The size limit of
can be specified with
, which has a default value of 128.
from functools import lru_cache @lru_cache(maxsize=64) def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)
Now the recursion tree for
does not have any nodes that occur more than twice. The running time now grows linearly, which is much faster than exponential growth.
decorator is equivalent to
from functools import cache @cache def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2)
Since it does not need to discard least recently used items,
is both smaller and faster than
with a size limit.
Memoization improves performance by caching the results of function calls and returning the cached result when the function is called with the same input(s) again.
Python 3 makes it easy to implement memoization. Simply import
and apply the decorator.
Create your free account to unlock your custom reading experience.