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:

@Memoizedef 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.

New to Python 3.2 is functools.lru_cache. 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:

import functools@functools.lru_cache(maxsize=None)def fib(num):    if num < 2:        return num    else:        return fib(num-1) + fib(num-2)

This function by itself is very slow, try fib(36) and you will have to wait about ten seconds.

Adding lru_cache annotation 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.

Python 3.9 released a new function functools.cache which is equivalent to lru_cache(maxsize=None) but with a shorter name:

@functools.cachedef fib(num):    # etc

The other answers cover what it is quite well. I'm 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, it's 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

@memoisedef actual_function(arg1, arg2):   #body