Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

Recipe 18.5. Memoizing (Caching) the Return Values of Functions

Credit: Paul Moore, Mitch Chapman, Hannu Kankaanp

Problem

You
have a pure function that is often called with the same arguments
(particularly a recursive function) and is slow to compute its
results. You want to find a simple way to gain substantial
improvement in performance.

Solution

The key idea behind memoizing is to store a
function's results in a dictionary, keyed by the
arguments that produce each result. This approach makes sense only
for a pure function (i.e., one that yields the same result when
called more than once with the same arguments). It's
easy to memoize a function by hand. For example, using the recursive
Fibonacci function, here is a manually memoized function:

fib_memo = {  }
def fib(n):
if n < 2: return 1
if n not in fib_memo:
fib_memo[n] = fib(n-1) + fib(n-2)
return fib_memo[n]

Having to code the memoization inside each function to be memoized is
repetitive and degrades the function's readability.
An alternative is to encapsulate the memoization mechanics into a
closure:

def memoize(fn):
memo = {  }
def memoizer(*param_tuple, **kwds_dict):
# can't memoize if there are any named arguments
if kwds_dict:
return fn(*param_tuple, **kwds_dict)
try:
# try using the memo dict, or else update it
try:
return memo[param_tuple]
except KeyError:
memo[param_tuple] = result = fn(*param_tuple)
return result
except TypeError:
# some mutable arguments, bypass memoizing
return fn(*param_tuple)
# 2.4 only: memoizer._ _name_ _ = fn._ _name_ _
return memoizer

Using this memoize closure to memoize
fib, the function definition becomes obvious,
without caching boilerplate to obscure the algorithm. You must assign
the memoize result to the same name,
fib, as the recursive function; otherwise, the
recursive calls bypass the memoizing:

def fib(n):
if n < 2: return 1
return fib(n-1) + fib(n-2)
fib = memoize(fib)

This latest snippet shows that memoize is meant to
be used exactly as a Python 2.4 decorator, so
in Python 2.4, you could use decorator syntax (instead of the
explicit call to memoize):

@memoize
def fib(n):
if n < 2: return 1
return fib(n-1) + fib(n-2)

giving exactly the same semantics as the previous snippet.

Discussion

The memoize function is called with just one
argument, a function f. It returns a
closure memoizer that acts just like
f but memoizes its arguments and result if
the actual arguments to a call are hashable and positional. Calls
with mutable or keyword arguments bypass the memoizing. If
you're worried that such bypassing happens too
often, making memoizing counterproductive, you should do a few dry
runs that are representative of your intended production usage, with
a closure that's modified to collect statistics.
Then you can decide whether memoization is worth using for your
specific application. Here's the modified
memoize for this purpose:

def memoize(fn):
memo = {  }
def memoizer(*param_tuple, **kwds_dict):
if kwds_dict:
memoizer.namedargs += 1
return fn(*param_tuple, **kwds_dict)
try:
memoizer.cacheable += 1
try:
return memo[param_tuple]
except KeyError:
memoizer.misses += 1
memo[param_tuple] = result = fn(*param_tuple)
return result
except TypeError:
memoizer.cacheable -= 1
memoizer.noncacheable += 1
return fn(*param_tuple)
memoizer.namedargs = memoizer.cacheable = memoizer.noncacheable = 0
memoizer.misses = 0
return memoizer

Functions to be memoized must be pure (i.e., they must have no side
effects and must always return the same value whenever they are
called with the same arguments). More significantly,
memoize returns a closure that does not
memoize calls that receive mutable arguments, such as
len on a list, nor functions that receive named
parameters.

memoize cannot really check the semantics of the
functions you wrap. The notions of same value
and same arguments are vaguely defined in many
cases, so take care. memoize does try to field
occasional calls with keyword and mutable arguments (with an
interesting mix of checking and
try/except), but performance
will suffer unless such cases are rare. This is why
it's worth having around a version of
memoize that keeps counts of the various
possibilities, so that you can check their rarity.

See Also

Recipe 20.4 applies caching
to class instances' attributes.