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?
-
283When 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.– CluelessJan 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.– ShreevatsaRApr 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– Stefan GruenwaldMay 24, 2014 at 19:08
-
2New link to pdf file, since pycogsci.info is down: people.ucsc.edu/~abrsvn/NLTK_parsing_demos.pdf– Stefan GruenwaldDec 5, 2014 at 20:08
-
1seeing 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_PJan 5, 2019 at 19:41
14 Answers
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.
-
2Thanks 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
-
13The Memoize class solution is buggy, it will not work the same as the
factorial_memo
, because thefactorial
insidedef factorial
still calls the old unmemoizefactorial
. Aug 6, 2013 at 7:35 -
11By the way, you can also write
if k not in factorial_memo:
, which reads better thanif not k in factorial_memo:
. Apr 4, 2014 at 6:34 -
5
-
3@durden2.0 I know this is an old comment, but
args
is a tuple.def some_function(*args)
makes args a tuple. Dec 13, 2016 at 18:18
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
-
2Tried fib(1000), got RecursionError: maximum recursion depth exceeded in comparison 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.– QuelklefAug 19, 2018 at 2:07 -
2If 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
-
4Note 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– endolithAug 2, 2019 at 14:41
-
2New in 3.9 is
functools.cache
which is (in cpython at least) a wrapper forlru_cache(maxsize=None)
but with a shorter name.– Amndeep7Mar 17, 2021 at 6:14
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
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)
-
See docs.python.org/3/library/functools.html#functools.wraps for why one should use
functools.wraps
. Apr 25, 2017 at 2:29 -
1
-
The whole idea is that the results are stored inside memo within a session. I.e. nothing are being cleared as it is 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
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.
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]
-
2This 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
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]
-
4For 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.– jkflyingMay 21, 2014 at 5:59
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.
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]
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)))
-
1Nice attempt. Without whining, a
list
argument of[1, 2, 3]
can mistakenly be considered the same as a differentset
argument with a value of{1, 2, 3}
. In addition, sets are unordered like dictionaries, so they would also need to besorted()
. Also note that a recursive data structure argument would cause an infinite loop. 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
list
s andset
s are "tupleized" into the same thing and therefore become indistinguishable from one another. The example code for adding support forsets
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. 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
list
s anddict
s because it's possible for alist
to have exactly the same thing in it that resulted from callingmake_tuple(sorted(x.items()))
for a dictionary. A simple solution for both cases would be to include thetype()
of value in the tuple generated. I can think of an even simpler way specifically to handleset
s, but it doesn't generalize. Jan 22, 2014 at 2:49
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
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
.
-
2This 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. Jun 1, 2016 at 19:47
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]
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).