Python - 有人能提供一个可以处理不可哈希参数的备忘录装饰器吗？

Question

我一直在使用一个记忆化装饰器（来自一本很棒的书《Python算法：掌握Python语言中的基本算法……我真的很喜欢这本书》）。

def memo(func):
    cache = {}
    @ wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

这个装饰器的问题在于，它使用字典来缓存数据，这就意味着我所有的参数都必须是可以被哈希的。

有没有人能提供一个实现（或者对这个装饰器的修改），可以支持那些不能被哈希的参数（比如字典）呢？

我知道没有哈希值就意味着“这个在缓存里吗？”的问题变得不那么简单，但我还是想问问。

===编辑以提供背景===

我正在开发一个函数，它根据一个模块和依赖关系的字典，返回一种类似Parnas风格的“使用层次结构”。这是我的设置：

def uses_hierarchy(requirements):
    """
    uses_hierarchy(requirements)

    Arguments:
    requirements - a dictionary of the form {mod: list of dependencies, }

    Return value:
    A dictionary of the form {level: list of mods, ...}

    Assumptions:
    - No cyclical requirements (e.g. if a requires b, b cannot require a).
    - Any dependency not listed as a mod assumed to be level 0.

    """

    levels = dict([(mod, _level(mod, requirements))
                   for mod in requirements.iterkeys()])
    reversed = dict([(value, []) for value in levels.itervalues()])
    for k, v in levels.iteritems():
        reversed[v].append(k)
    return reversed


def _level(mod, requirements):
    if not requirements.has_key(mod):
        return 0
    dependencies = requirements[mod]
    if not dependencies:
        return 0
    else:
        return max([_level(dependency, requirements)
                    for dependency in dependencies]) + 1

所以：

>>> requirements = {'a': [],
...                 'b': [],
...                 'c': ['a'],
...                 'd': ['a','b'],
...                 'e': ['c','d'],
...                 'f': ['e']
...                 }

>>> uses_hierarchy(requirements)
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']}

_level是我想要记忆化的函数，这样可以让这个设置更具可扩展性。没有记忆化的实现方式下，它会多次计算依赖关系的层级（比如在上面的例子中，‘a’大概被计算了8次）。

谢谢，

迈克

Answer 1

这个代码没有经过很多测试，但看起来是可以用的：

from functools import wraps

def memo(func):
    cache = []
    argslist = []
    @ wraps(func)
    def wrap(*args):
        try:
            result = cache[argslist.index(args)]
            print 'cache hit'
            return result
        except ValueError:
            argslist.append(args)
            cache.append(func(*args))
            print 'cache miss'
            return cache[-1]
    return wrap

d1 = { 'a':3, 'b':42 }
d2 = { 'c':7, 'd':19 }
d3 = { 'e':34, 'f':67 }

@memo
def func(d):
    return sum(d.values())

print func(d1)
# cache miss
# 45
print func(d2)
# cache miss
# 26
print func(d3)
# cache miss
# 101
print func(d2)
# cache hit
# 26

Answer 2

从技术上讲，你可以通过把 dict（字典）、list（列表）或 set（集合）转换成一个元组来解决这个问题。比如说：

 key = tuple(the_dict.iteritems())
 key = tuple(the_list)
 key = tuple(sorted(the_set))

 cache[key] = func( .. )

不过我不建议在 memo 中这样做，我更倾向于直接修改你想要使用记忆化的函数。例如，函数可以只接受 (key, value) 这样的键值对，而不是接受字典；如果要处理列表或集合，函数可以直接接受 *args 这样的参数。

Answer 3

这里有一个例子，来自于Alex Martelli的《Python Cookbook》，展示了如何使用cPickle创建一个记忆化装饰器，适用于接受可变参数的函数（原始版本）：

import cPickle

class MemoizeMutable:
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args, **kwds):
        import cPickle
        str = cPickle.dumps(args, 1)+cPickle.dumps(kwds, 1)
        if not self.memo.has_key(str): 
            print "miss"  # DEBUG INFO
            self.memo[str] = self.fn(*args, **kwds)
        else:
            print "hit"  # DEBUG INFO

        return self.memo[str]

这里有一个链接。

编辑：使用你提供的代码和这个记忆化装饰器：

_level = MemoizeMutable(_level)

requirements = {'a': [],
               'b': [],
               'c': ['a'],
               'd': ['a','b'],
               'e': ['c','d'],
               'f': ['e']
                 }

print uses_hierarchy(requirements)

我成功地复现了这个结果：

miss
miss
hit
miss
miss
hit
miss
hit
hit
hit
miss
hit
{0: ['a', 'b'], 1: ['c', 'd'], 2: ['e'], 3: ['f']}