Python - 任何人都有一個memoizing裝飾器，可以處理不可參數的參數？

Question

我一直在使用下面的memoizing裝飾器（從偉大的書籍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 

與這個裝飾的問題是，基於字典的緩存意味着我所有的參數都必須是可哈希。

有沒有人有一個實現（或調整到這一個），允許不可干擾的參數（例如字典）？

我知道缺少散列值意味着「這是在緩存中嗎？」的問題。變得不平凡，但我只是想我會問。

===編輯，以給定的上下文===

我上一個返回爾格式功能工作的「使用層次結構」給定模塊的字典：依賴關係。這裏的設置：

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是我想memoize的，使這個設置更具擴展性的功能。如果不使用memoization實現，它會多次計算依賴關係的級別（例如，在上面的示例中，我認爲「a」的計算次數是8次）。

感謝，

邁克

Answer 1

這裏是亞歷克斯·馬爾泰利Python Cookbook，說明如何創建使用cPickle爲採取可變參數功能memoize的裝飾的例子（原始版本）：

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] 

這裏是一個link。

編輯：使用您所提供的代碼，這memoize的裝飾：

_level = MemoizeMutable(_level) 

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

print uses_hierarchy(equirements) 

我能重現此：

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

Answer 2

從技術上講，你可以通過轉動dict（或list或set）轉換成一個元組解決這個問題。例如：

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

cache[key] = func(..) 

但我不會在memo做到這一點，我寧願改變你想使用的備忘錄上的功能 - 例如，而不是接受dict他們應該只接受(key, value)雙，而不是採取清單或集，他們應該採取*args。

Answer 3

沒有大量測試，但似乎工作：

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 4

由於沒有人提到過它，所以P ython Wiki有一個Decorator庫，其中包含一些memoizing decorator patterns。

我個人的偏好是最後一個，它可以讓調用代碼簡單地將該方法視爲一種懶惰評估的屬性，而不是一種方法。但我更喜歡執行here。

class lazy_property(object): 
    '''Decorator: Enables the value of a property to be lazy-loaded. 
    From Mercurial's util.propertycache 

    Apply this decorator to a no-argument method of a class and you 
    will be able to access the result as a lazy-loaded class property. 
    The method becomes inaccessible, and the property isn't loaded 
    until the first time it's called. Repeated calls to the property 
    don't re-run the function. 

    This takes advantage of the override behavior of Descriptors - 
    __get__ is only called if an attribute with the same name does 
    not exist. By not setting __set__ this is a non-data descriptor, 
    and "If an instance's dictionary has an entry with the same name 
    as a non-data descriptor, the dictionary entry takes precedence." 
    - http://users.rcn.com/python/download/Descriptor.htm 

    To trigger a re-computation, 'del' the property - the value, not 
    this class, will be deleted, and the value will be restored upon 
    the next attempt to access the property. 
    ''' 
    def __init__(self,func): 
     self.func = func 
     self.name = func.__name__ 
    def __get__(self, obj, type=None): 
     result = self.func(obj) 
     setattr(obj, self.name, result) 
     return result 

在連接的同一個文件上面也有一個lazy_dict裝飾，它可以讓你把一個函數與惰性計算值的字典。