在Python中缓存具有两个参数的函数结果

Question

我有一个方法，它需要两个参数来进行一些复杂的计算。这个方法被频繁调用，而且每次用的参数都差不多，所以我用一个字典来缓存结果。现在的代码大概是这样的：

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]

我之所以要使用frozenset，是因为这两个参数的顺序可以不同，但计算结果是一样的。我在想，是否有更简单（而且更高效）的解决方案。

Answer 1

我会把它存储在缓存里两次，每种顺序各存一次。

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 2

你实现的缓存方式并没有什么特别低效或复杂的地方，这基本上就是需要做的事情。不过，这种方式并不是很通用。

你可以使用装饰器来实现一种更通用的缓存策略，这样会更方便。一个可能的方法是：

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

打印：

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])

当然，把缓存放在对象外部的缺点是，当你的对象消失时，缓存的数据不会被删除，除非你特别去处理这个问题。

Answer 3

你的代码有两个问题：

(1) 它使用了旧的 dict.has_key() 方法，这个方法比较慢，并且在 Python 3.x 中已经被删除了。你应该用 "key in dict" 或 "key not in dict" 来替代。

所以：

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" 更容易理解，而且暴露了一个更严重的问题：你的代码根本无法正常工作！如果参数在字典里，它会重新计算。如果参数不在字典里，就会出现 KeyError 错误。建议你考虑复制粘贴，而不是凭记忆输入。

所以：

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) 还有一些提高效率的建议：

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