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

Question

I just started Python and I've got no idea what memoization is and how to use it. Also, may I have a simplified example?

Answer 1

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.

Answer 2

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. It's 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 

---