# 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?

1
344
10/29/2011 10:53:05 AM

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.

333
4/8/2018 12:06:32 AM