Caching the results of a function with two parameters in Python

Question

I have a method with two parameters that does some complex computation. It is called very often with the same parameters, so I am using a dictionary for caching. Currently this looks something like this:

def foo(self, a, b):
    params = frozenset([a, b])
    if not params in self._cache:
        self._cache[params] = self._calculate(a, b)
    return self._cache[params]

The reason for building the frozenset is that the parameters can be in any order, but the result will be the same. I am wondering if there is a simpler (and most importantly more efficient) solution for this.

Answer 1

You can either combine the two values into one hash value like str(a)+'\0'+str(b) and then put it into a cache, or you can make a two-dimensional array so that cache[a][b] returns the value you want.

You may also want to turn this functionality into a @decorator kind of function, then you can reuse the decorator on several functions and maintain one code location for the caching.

Answer 2

I'd just store it in the cache twice, once for each ordering.

def foo(self, a, b):
    try:
        return self._cache[(a, b)]
    except KeyError:
        value = self._calculate(a, b)
        self._cache[(a, b)] = self._cache[(b, a)] = value
        return value

Answer 3

You could use beaker.cache for that (http://beaker.groovie.org/index.html)

# define a cache manager
cache = CacheManager(dict_of_config_options)

# in your class, apply a cache decorator
@cache.cache('mycache')
def foo(self, a,b):
    return self._calculate

I think it works like you want by default. Not sure if this uses self as part of the key. It assumes that a, b are pickleable.

Answer 4

There's nothing particularly inefficient or complicated about how you implemented your caching; that's essentially what needs to happen. It isn't very general, however.

You can implement some sort of more generalized caching strategy, using decorators if you like, for convenience. One possible approach might be:

class Memoizer(object):
    def __init__(self):
        self._cache = dict()

    def memoize_unordered(self, f):
        def wrapper(s, *args, **kwargs):
            key = (s, f, frozenset(args), frozenset(kwargs.iteritems()))
            if key not in self._cache:
                print 'calculating', args, kwargs
                self._cache[key] = f(s, *args, **kwargs)
            return self._cache[key]
        return wrapper

    def memoize_ordered(self, f):
        def wrapper(s, *args, **kwargs):
            key = (s, f, tuple(args), frozenset(kwargs.iteritems()))
            if key not in self._cache:
                print 'calculating', args, kwargs
                self._cache[key] = f(s, *args, **kwargs)
            return self._cache[key]
        return wrapper

memoizer = Memoizer()

class Foo(object):

    @memoizer.memoize_unordered
    def foo(self, a, b):
        return self._calculate(a, b)

    def _calculate(self, a, b):
        return frozenset([a,b])

foo = Foo()


results = [foo.foo(*a) for a in [(1, 5), (1, 5), (5, 1), (9, 12), (12, 9)]]
for result in results:
    print 'RESULT', result

printing:

calculating (1, 5) {}
calculating (9, 12) {}
RESULT frozenset([1, 5])
RESULT frozenset([1, 5])
RESULT frozenset([1, 5])
RESULT frozenset([9, 12])
RESULT frozenset([9, 12])

The downside of course, to implementing caching outside of your object, is that the cache data doesn't get deleted when your object goes away, unless you take some care to make this happen.

Answer 5

Your code has two problems:

(1) It uses the old dict.has_key() method which is slow and has vanished in Python 3.x. Instead use "key in dict" or "key not in dict".

So:

def foo(self, a, b):
    params = frozenset([a, b])
    if params in self._cache:
        self._cache[params] = self._calculate(a, b)
    return self._cache[params]

(2) "key in dict" is more readable, and exposes the much worse problem: your code doesn't work! If the args are in the dict, it recalculates. If they're not in the dict, it will blow up with a KeyError. Consider copy/paste instead of typing from memory.

So:

def foo(self, a, b):
    params = frozenset([a, b])
    if params not in self._cache:
        self._cache[params] = self._calculate(a, b)
    return self._cache[params]

(3) Some more efficiency suggestions:

def foo(self, a, b):
    if a < b:
        params = (a, b)
    else:
        params = (b, a)
    try:
        return self._cache[params]
    except KeyError:
        v = self._cache[params] = self._calculate(a, b)
        return v