Memoization means saving the result of a function call, so the next call with the same arguments returns the saved result instead of working it out again. Here you build it yourself with a dictionary and a decorator.
The program
python
def memoize(func): cache = {} def wrapper(*args): if args not in cache: cache[args] = func(*args) return cache[args] return wrapper calls = 0 def slow_fib(n): global calls calls += 1 return n if n < 2 else slow_fib(n - 1) + slow_fib(n - 2) print("plain: ", slow_fib(20), "after", calls, "calls") calls = 0 @memoize def fast_fib(n): global calls calls += 1 return n if n < 2 else fast_fib(n - 1) + fast_fib(n - 2) print("memoized:", fast_fib(20), "after", calls, "calls") print("again: ", fast_fib(20), "after", calls, "calls")
setup added so this can run · defines args
# Lightweight mock for objects whose attributes/methods aren't critical class _AutoMock: def __init__(self, name='mock'): self._name = name def __getattr__(self, k): return _AutoMock(self._name + '.' + k) def __call__(self, *a, **kw): print('-> ' + self._name + '() called') return _AutoMock(self._name + '()') def __repr__(self): return '<mock ' + self._name + '>' def __str__(self): return '<mock ' + self._name + '>' def __bool__(self): return True def __iter__(self): return iter([]) def __len__(self): return 0 def __getitem__(self, k): return _AutoMock(self._name + '[...]') def __setitem__(self, k, v): pass def __enter__(self): return self def __exit__(self, *a): return False async def __aenter__(self): return self async def __aexit__(self, *a): return False def __add__(self, o): return self def __radd__(self, o): return self def __sub__(self, o): return self def __mul__(self, o): return self def __rmul__(self, o): return self def __truediv__(self, o): return self def __eq__(self, o): return isinstance(o, _AutoMock) def __hash__(self): return hash(self._name) def __lt__(self, o): return True def __le__(self, o): return True def __gt__(self, o): return False def __ge__(self, o): return False def __mro_entries__(self, bases): return (object,) args = _AutoMock('args')
output
plain: 6765 after 21891 calls memoized: 6765 after 21 calls again: 6765 after 21 calls
How it works
cacheis a dictionary created once, whenmemoizeruns.wrappercan still use it later: a function defined inside another function keeps access to its variables (this is called a closure).argsis a tuple of the arguments, such as(20,), and it is the dictionary key. A tuple can be a key; a list cannot.- The plain version works out
slow_fib(18),slow_fib(17)and the rest again and again, in 21,891 calls. The memoized version computes each value from 0 to 20 once: 21 calls. - The second
fast_fib(20)call adds no new calls at all. The answer comes straight from the cache.
Limits of this version
- It accepts positional arguments only. A call like
fast_fib(n=20)raises aTypeError. - Every argument must be hashable (usable as a dictionary key), so it fails for a list argument.
- The cache never gets smaller. For a function called with millions of different arguments, it keeps growing.
The standard library version, functools.cache (or functools.lru_cache(maxsize=...) with a size limit), handles keyword arguments and size limits. Use it in real code. Writing your own once shows what it does.
Related programs: Memoization with functools.cache.