499

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?

7
  • 283
    When the second sentence of the relevant wikipedia article contains the phrase "mutually-recursive descent parsing[1] in a general top-down parsing algorithm[2][3] that accommodates ambiguity and left recursion in polynomial time and space," I think it is entirely appropriate to ask SO what is going on.
    – Clueless
    Jan 2, 2010 at 14:17
  • 14
    @Clueless: That phrase is preceded by "Memoization has also been used in other contexts (and for purposes other than speed gains), such as in". So it's just a list of examples (and need not be understood); it's not part of the explanation of memoization. Apr 4, 2014 at 6:12
  • Here is a good explanation with attached examples of memoization and how to incorporate it into a decorator: pycogsci.info/?p=221 May 24, 2014 at 19:08
  • 2
    New link to pdf file, since pycogsci.info is down: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf Dec 5, 2014 at 20:08
  • 1
    seeing how many people answered and are still answering this question makes be a believer in the "BIKE SHED EFFECT" en.wikipedia.org/wiki/Law_of_triviality
    – A_P
    Jan 5, 2019 at 19:41

14 Answers 14

430

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.

19
  • 2
    Thanks for this suggestion. The Memoize class is an elegant solution which can easily be applied to existing code without needing much refactoring. Apr 11, 2013 at 12:41
  • 13
    The Memoize class solution is buggy, it will not work the same as the factorial_memo, because the factorial inside def factorial still calls the old unmemoize factorial.
    – adamsmith
    Aug 6, 2013 at 7:35
  • 11
    By the way, you can also write if k not in factorial_memo:, which reads better than if not k in factorial_memo:. Apr 4, 2014 at 6:34
  • 5
    Should really do this as a decorator. Oct 8, 2014 at 4:23
  • 3
    @durden2.0 I know this is an old comment, but args is a tuple. def some_function(*args) makes args a tuple.
    – Adam Smith
    Dec 13, 2016 at 18:18
370

functools.cache decorator:

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

import functools
import time

@functools.cache
def calculate_double(num):
    time.sleep(1) # sleep for 1 second to simulate a slow calculation
    return num * 2

The first time you call caculate_double(5), it will take a second and return 10. The second time you call the function with the same argument calculate_double(5), it will return 10 instantly.

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.

(Edit: the previous example calculated a fibonacci number using recursion, but I changed the example to prevent confusion, hence the old comments.)

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 calculate_double(num):
    # etc

10
  • 2
    Tried fib(1000), got RecursionError: maximum recursion depth exceeded in comparison
    – Andreas K.
    Sep 28, 2017 at 12:04
  • 6
    @Andyk Default Py3 recursion limit is 1000. The first time fib is called, it will need to recur down to the base case before memoization can happen. So, your behavior is just about expected.
    – Quelklef
    Aug 19, 2018 at 2:07
  • 2
    If I'm not mistaken, it caches only until the process is not killed, right? Or does it cache regardless of whether the process is killed? Like, say I restart my system - will the cached results still be cached? Oct 22, 2018 at 2:20
  • 4
    Note that this speeds up even the first run of the function, since it's a recursive function and is caching its own intermediate results. Might be good to illustrate a non-recursive function that's just inherently slow to make it clearer to dummies like me. :D
    – endolith
    Aug 2, 2019 at 14:41
  • 2
    New in 3.9 is functools.cache which is (in cpython at least) a wrapper for lru_cache(maxsize=None) but with a shorter name.
    – Amndeep7
    Mar 17, 2021 at 6:14
63

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

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

I've found this extremely useful

from functools import wraps


def memoize(function):    
    memo = {}
        
    @wraps(function)
    def wrapper(*args):

        # add the new key to dict if it doesn't exist already  
        if args not in memo:
            memo[args] = function(*args)

        return memo[args]

    return wrapper
    
    
@memoize
def fibonacci(n):
    if n < 2: return n
    return fibonacci(n - 1) + fibonacci(n - 2)
    
fibonacci(25)
4
  • See docs.python.org/3/library/functools.html#functools.wraps for why one should use functools.wraps.
    – anishpatel
    Apr 25, 2017 at 2:29
  • 1
    Do I need to manually clear the memo so that memory is freed?
    – nos
    May 18, 2017 at 3:54
  • The whole idea is that the results are stored inside memo within a session. I.e. nothing are being cleared as it is
    – mr.bjerre
    May 18, 2017 at 7:21
  • is "args not in memo" literally enumerating the memo list of keys and checking if args matches? or is actually using the underlying dictionary and checking if the entry hashed(args) is present in memo dictionary's underlying array? if its the former then does this code run faster if we use defaultdictionaries to insist on checking the hash? Oct 22 at 0:36
20

Memoization is keeping the results of expensive calculations and returning the cached result rather than continuously recalculating it.

Here's an example:

def doSomeExpensiveCalculation(self, input):
    if input not in self.cache:
        <do expensive calculation>
        self.cache[input] = result
    return self.cache[input]

A more complete description can be found in the wikipedia entry on memoization.

0
19

Let's not forget the built-in hasattr function, for those who want to hand-craft. That way you can keep the mem cache inside the function definition (as opposed to a global).

def fact(n):
    if not hasattr(fact, 'mem'):
        fact.mem = {1: 1}
    if not n in fact.mem:
        fact.mem[n] = n * fact(n - 1)
    return fact.mem[n]
1
  • 2
    This seems like a very expensive idea. For every n, it not only caches the results for n, but also for 2 ... n-1. Jun 27, 2019 at 8:45
6

Memoization is basically saving the results of past operations done with recursive algorithms in order to reduce the need to traverse the recursion tree if the same calculation is required at a later stage.

see http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/

Fibonacci Memoization example in Python:

fibcache = {}
def fib(num):
    if num in fibcache:
        return fibcache[num]
    else:
        fibcache[num] = num if num < 2 else fib(num-1) + fib(num-2)
        return fibcache[num]
1
  • 4
    For more performance pre-seed your fibcache with the first few known values, then you can take the extra logic for handling them out of the 'hot path' of the code.
    – jkflying
    May 21, 2014 at 5:59
5

Memoization is the conversion of functions into data structures. Usually one wants the conversion to occur incrementally and lazily (on demand of a given domain element--or "key"). In lazy functional languages, this lazy conversion can happen automatically, and thus memoization can be implemented without (explicit) side-effects.

5

Well I should answer the first part first: what's memoization?

It's just a method to trade memory for time. Think of Multiplication Table.

Using mutable object as default value in Python is usually considered bad. But if use it wisely, it can actually be useful to implement a memoization.

Here's an example adapted from http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects

Using a mutable dict in the function definition, the intermediate computed results can be cached (e.g. when calculating factorial(10) after calculate factorial(9), we can reuse all the intermediate results)

def factorial(n, _cache={1:1}):    
    try:            
        return _cache[n]           
    except IndexError:
        _cache[n] = factorial(n-1)*n
        return _cache[n]
4

Here is a solution that will work with list or dict type arguments without whining:

def memoize(fn):
    """returns a memoized version of any function that can be called
    with the same list of arguments.
    Usage: foo = memoize(foo)"""

    def handle_item(x):
        if isinstance(x, dict):
            return make_tuple(sorted(x.items()))
        elif hasattr(x, '__iter__'):
            return make_tuple(x)
        else:
            return x

    def make_tuple(L):
        return tuple(handle_item(x) for x in L)

    def foo(*args, **kwargs):
        items_cache = make_tuple(sorted(kwargs.items()))
        args_cache = make_tuple(args)
        if (args_cache, items_cache) not in foo.past_calls:
            foo.past_calls[(args_cache, items_cache)] = fn(*args,**kwargs)
        return foo.past_calls[(args_cache, items_cache)]
    foo.past_calls = {}
    foo.__name__ = 'memoized_' + fn.__name__
    return foo

Note that this approach can be naturally extended to any object by implementing your own hash function as a special case in handle_item. For example, to make this approach work for a function that takes a set as an input argument, you could add to handle_item:

if is_instance(x, set):
    return make_tuple(sorted(list(x)))
5
  • 1
    Nice attempt. Without whining, a list argument of [1, 2, 3] can mistakenly be considered the same as a different set argument with a value of {1, 2, 3}. In addition, sets are unordered like dictionaries, so they would also need to be sorted(). Also note that a recursive data structure argument would cause an infinite loop.
    – martineau
    Jan 20, 2014 at 1:31
  • Yea, sets should be handled by special casing handle_item(x) and sorting. I shouldn't have said that this implementation handles sets, because it doesn't - but the point is that it can be easily extended to do so by special casing handle_item, and the same will work for any class or iterable object as long as you're willing to write the hash function yourself. The tricky part - dealing with multi-dimensional lists or dictionaries - is already dealt with here, so I've found that this memoize function is a lot easier to work with as a base than the simple "I only take hashable arguments" types. Jan 21, 2014 at 1:36
  • The problem I mentioned is due to the fact that lists and sets are "tupleized" into the same thing and therefore become indistinguishable from one another. The example code for adding support for sets described in your latest update doesn't avoid that I'm afraid. This can easily be seen by separately passing [1,2,3] and {1,2,3} as an argument to a "memoize"d test function and seeing whether it's called twice, as it should be, or not.
    – martineau
    Jan 21, 2014 at 2:07
  • yea, I read that problem, but I didn't address it because I think it is much more minor than the other one you mentioned. When was the last time you wrote a memoized function where a fixed argument could be either a list or a set, and the two resulted in different outputs? If you were to run into such a rare case, you would again just rewrite handle_item to prepend, say a 0 if the element is a set, or a 1 if it is a list. Jan 22, 2014 at 0:14
  • Actually, there's a similar issue with lists and dicts because it's possible for a list to have exactly the same thing in it that resulted from calling make_tuple(sorted(x.items())) for a dictionary. A simple solution for both cases would be to include the type() of value in the tuple generated. I can think of an even simpler way specifically to handle sets, but it doesn't generalize.
    – martineau
    Jan 22, 2014 at 2:49
3

Solution that works with both positional and keyword arguments independently of order in which keyword args were passed (using inspect.getargspec):

import inspect
import functools

def memoize(fn):
    cache = fn.cache = {}
    @functools.wraps(fn)
    def memoizer(*args, **kwargs):
        kwargs.update(dict(zip(inspect.getargspec(fn).args, args)))
        key = tuple(kwargs.get(k, None) for k in inspect.getargspec(fn).args)
        if key not in cache:
            cache[key] = fn(**kwargs)
        return cache[key]
    return memoizer

Similar question: Identifying equivalent varargs function calls for memoization in Python

3

Just wanted to add to the answers already provided, the Python decorator library has some simple yet useful implementations that can also memoize "unhashable types", unlike functools.lru_cache.

1
  • 2
    This decorator does not memoize "unhashable types"! It just falls back to calling the function without memoization, going against against the explicit is better than implicit dogma.
    – ostrokach
    Jun 1, 2016 at 19:47
2
cache = {}
def fib(n):
    if n <= 1:
        return n
    else:
        if n not in cache:
            cache[n] = fib(n-1) + fib(n-2)
        return cache[n]
0
1

If speed is a consideration:

  • @functools.cache and @functools.lru_cache(maxsize=None) are equally fast, taking 0.122 seconds (best of 15 runs) to loop a million times on my system
  • a global cache variable is quite a lot slower, taking 0.180 seconds (best of 15 runs) to loop a million times on my system
  • a self.cache class variable is a bit slower still, taking 0.214 seconds (best of 15 runs) to loop a million times on my system

The latter two are implemented similar to how it is described in the currently top-voted answer.

This is without memory exhaustion prevention, i.e. I did not add code in the class or global methods to limit that cache's size, this is really the barebones implementation. The lru_cache method has that for free, if you need this.

One open question for me would be how to unit test something that has a functools decorator. Is it possible to empty the cache somehow? Unit tests seem like they would be cleanest using the class method (where you can instantiate a new class for each test) or, secondarily, the global variable method (since you can do yourimportedmodule.cachevariable = {} to empty it).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.