Welcome, guest | Sign In | My Account | Store | Cart

Cache decorator in python 2.4 (Python recipe) by George Sakkis
ActiveState Code (http://code.activestate.com/recipes/325205/)

The latest version of Python introduced a new language feature, function and method decorators (PEP 318, http://www.python.org/peps/pep-0318.html). This recipe show a common callable transformation that can benefit from the new syntax, often referred to as Memoization pattern.

Python, 58 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import types

def cachedmethod(function):
    return types.MethodType(Memoize(function), None)


class Memoize:
    def __init__(self,function):
        self._cache = {}
        self._callable = function
            
    def __call__(self, *args, **kwds):
        cache = self._cache
        key = self._getKey(*args,**kwds)
        try: return cache[key]
        except KeyError:
            cachedValue = cache[key] = self._callable(*args,**kwds)
            return cachedValue
    
    def _getKey(self,*args,**kwds):
        return kwds and (args, ImmutableDict(kwds)) or args    


class ImmutableDict(dict):
    '''A hashable dict.'''

    def __init__(self,*args,**kwds):
        dict.__init__(self,*args,**kwds)
    def __setitem__(self,key,value):
        raise NotImplementedError, "dict is immutable"
    def __delitem__(self,key):
        raise NotImplementedError, "dict is immutable"
    def clear(self):
        raise NotImplementedError, "dict is immutable"
    def setdefault(self,k,default=None):
        raise NotImplementedError, "dict is immutable"
    def popitem(self):
        raise NotImplementedError, "dict is immutable"
    def update(self,other):
        raise NotImplementedError, "dict is immutable"
    def __hash__(self):
        return hash(tuple(self.iteritems()))


if __name__ == '__main__':
    from math import sqrt,log,sin,cos
        
    class Example:
        def __init__(self,x,y):
            # self._x and self._y should not be changed after initialization
            self._x = x
            self._y = y
        
        @cachedmethod
        def computeSomething(self, alpha, beta):
            w = log(alpha) * sqrt(self._x * alpha + self._y * beta)
            z = log(beta) * sqrt(self._x * beta + self._y * alpha)
            return sin(z) / cos(w)

Memoization is a useful pattern for improving the amortized performance of a computationally expensive function or method. The new syntax allows making explicit that a callable is memoized.

A restriction of the recipe above is that the arguments of the function (and also the method receiver object for methods) have to be hashable.

The decorator can be generalized by allowing different caching policies (e.g. a FIFO cache or a cache implementing an LRU policy) apart from the implied "cache-forever" policy of a dict.

Tags: oop

12 comments

Alex Naanou 19 years, 5 months ago  # | flag

to make this more generic I'd update the __call__ method to:

def __call__(self, *args, **kw):
    cache = self._cache
    try:
        return cache[(args, kw)]
    except KeyError:
        cachedValue = cache[(args, kw)] = self._callable(*args, **kw)
        return cachedValue
Sridhar R 19 years, 5 months ago  # | flag

Memory boom! Memoization is nice technique. But making it implicit will lead to programmers forgetfullness in controlling memory usage the cache takes.

"Explicit is better than Implicit"

George Sakkis (author) 19 years, 5 months ago  # | flag

Handling *keywords. Unfortunately it's not that straightforward; a dict is not hashable, so you can't use it as a key in the cache. One way to make this work is to define an ImmutableDict subclass that is (__hash__)able. Then wrap *kwds into such an ImmutableDict before caching them. However I wanted to keep this recipe simple, hence the less general solution.

Anyway, I updated the recipe for handling keyword arguments too.

George Sakkis (author) 19 years, 5 months ago  # | flag

That's what is neat about decorators; they make it explicit at the point of method definition. It is also straightforward to replace the dict used for cache with any other appropriate class to address issues such as memory consumption, efficiency or anything else that is important for the application:

def cachedmethod(cache = dict()):
    return lambda function: types.MethodType(Memoize(function,cache), None)

class Memoize:
    def __init__(self, function, cache = dict()):
        self._callable = function
        self._cache = cache

     # rest methods
     # (...)

# uses a dict
@cachedmethod()
def example1(x,y,z):
    pass

# uses an LRU policy with a cache of size 1000
@cachedmethod(cache = LRU(size=1000))
def example2(x,y,z):
    pass
Connelly Barnes 19 years, 5 months ago  # | flag

Simple is better than complex.

import pickle, copy
def memoize(f, cache={}):
  d = copy.copy(cache)
  def g(*args, **kwargs):
    key = pickle.dumps((args, kwargs))
    if not key in d:
      d[key] = f(*args, **kwargs)
    return d[key]
  return g

Works with builtin dicts, lists, allows arbitrary cache objects. Yes, this will use up your memory and crash your system if the cache gets too big.

Chris Spencer 17 years, 12 months ago  # | flag

Broken. This doesn't work with Python 2.4.

Traceback (most recent call last):
  File "memo-test.py", line 48, in ?
    class Example:
  File "memo-test.py", line 54, in Example
    @cachedmethod
  File "memo-test.py", line 4, in cachedmethod
    return types.MethodType(Memoize(function), None)
TypeError: unbound methods must have non-NULL im_class
Chris Spencer 17 years, 12 months ago  # | flag

A working example. This will corretly decorate a method:

def memoize(function):
    return Memoize(function)

class Memoize(object):
    def __init__(self, fn):
        self.cache={}
        self.fn=fn

    def __get__(self, instance, cls=None):
        self.instance = instance
        return self

    def __call__(self,*args):
        if self.cache.has_key(args):
            return self.cache[args]
        else:
            object = self.cache[args] = self.fn(self.instance, *args)
            return object
Yair Chuchem 17 years, 9 months ago  # | flag

set. You can use set instead of ImmutableDict

Radek Szklarczyk 16 years, 10 months ago  # | flag

Beautiful is better than ugly. The function below is a nice compromise between simplicity and power. Unlike the version above you can use this decorator to safely decorate more than one function (thanks to the fact that functions are hashable).

def memoize(f, cache={}):
    def g(*args, **kwargs):
        key = ( f, tuple(args), frozenset(kwargs.items()) )
        if key not in cache:
            cache[key] = f(*args, **kwargs)
        return cache[key]
    return g

Note that args list is converted to a tuple (which is hashable, unlike the list) and the dictionary *kwargs is converted to a frozenset (which is, as opposed to a set, hashable). If you don't have frozenset (pre-2.4), you can use tuple(kwargs.items())

Maxim Krikun 15 years, 3 months ago  # | flag

Doesn't work with recursive functions:

f = lambda n: (n<=2) and 1 or (f(n-1)+f(n-2))

now computing, say, f(30) takes some considerable time, because of a dumb recursion;

now let

g = Memoize(f)

computing g(30) takes the same amount of time, because internal evaluations of f(n-1), f(n-2) do not take advantage of memorization.

Radek Szklarczyk 14 years, 8 months ago  # | flag

@maxim.krikun: Memoize indeed does not work as work function, but it does work as a decorator

@memoize
def f(n):
    return (n<=2) and 1 or (f(n-1)+f(n-2))

f(40) # blindingly fast
Created by George Sakkis on Tue, 26 Oct 2004 (PSF)
◄ Python recipes (4591) ►
◄ George Sakkis's recipes (26) ►

Required Modules

Other Information and Tasks