What is memoization and how can I use it in Python? What is memoization and how can I use it in Python? python 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:

``@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``