# What is memoization and how can I use it in Python?

## What is memoization and how can I use it in Python?

Memoization effectively refers to remembering (memoization → memorandum → to be remembered) results of method calls based on the method inputs and then returning the remembered result rather than computing the result again. You can think of it as a cache for method results. For further details, see page 387 for the definition in Introduction To Algorithms (3e), Cormen et al.

A simple example for computing factorials using memoization in Python would be something like this:

``````factorial_memo = {}
def factorial(k):
if k < 2: return 1
if k not in factorial_memo:
factorial_memo[k] = k * factorial(k-1)
return factorial_memo[k]
``````

You can get more complicated and encapsulate the memoization process into a class:

``````class Memoize:
def __init__(self, f):
self.f = f
self.memo = {}
def __call__(self, *args):
if not args in self.memo:
self.memo[args] = self.f(*args)
#Warning: You may wish to do a deepcopy here if returning objects
return self.memo[args]
``````

Then:

``````def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)

factorial = Memoize(factorial)
``````

A feature known as decorators was added in Python 2.4 which allow you to now simply write the following to accomplish the same thing:

``````@Memoize
def factorial(k):
if k < 2: return 1
return k * factorial(k - 1)
``````

The Python Decorator Library has a similar decorator called `memoized` that is slightly more robust than the `Memoize` class shown here.

## `functools.cache` decorator:

Python 3.9 released a new function `functools.cache`. It caches in memory the result of a functional called with a particular set of arguments, which is memoization. Its easy to use:

``````import functools

@functools.cache
def fib(num):
if num < 2:
return num
else:
return fib(num-1) + fib(num-2)
``````

This function without the decorator is very slow, try `fib(36)` and you will have to wait about ten seconds.

Adding the `cache` decorator ensures that if the function has been called recently for a particular value, it will not recompute that value, but use a cached previous result. In this case, it leads to a tremendous speed improvement, while the code is not cluttered with the details of caching.

## `functools.lru_cache` decorator:

If you need to support older versions of Python, `functools.lru_cache` works in Python 3.2+. By default, it only caches the 128 most recently used calls, but you can set the `maxsize` to `None` to indicate that the cache should never expire:

``````@functools.lru_cache(maxsize=None)
def fib(num):
# etc
``````

#### What is memoization and how can I use it in Python?

The other answers cover what it is quite well. Im not repeating that. Just some points that might be useful to you.

Usually, memoisation is an operation you can apply on any function that computes something (expensive) and returns a value. Because of this, its often implemented as a decorator. The implementation is straightforward and it would be something like this

``````memoised_function = memoise(actual_function)
``````

or expressed as a decorator

``````@memoise
def actual_function(arg1, arg2):
#body
``````