如何加速这个备忘录装饰器？

Question

我想要一个记忆化装饰器，它需要满足以下几点：

• 能够对实例方法进行记忆化处理，支持传入参数和关键字参数
• 有一个可以通过一次调用全局清除的缓存（而不是像这个使用每个函数单独缓存的方式：python 可重置的实例方法记忆化装饰器）
• 效率要合理

我对一个例子进行了修改，得到了以下代码：

import functools

class Memoized(object):
  """Decorator that caches a function's return value each time it is called.
  If called later with the same arguments, the cached value is returned, and
  not re-evaluated.
  """

  __cache = {}

  def __init__(self, func):
    self.func = func
    self.key = (func.__module__, func.__name__)

  def __call__(self, *args):
    try:
      return Memoized.__cache[self.key][args]
    except KeyError:
      value = self.func(*args)
      Memoized.__cache[self.key] = {args : value}
      return value
    except TypeError:
      # uncachable -- for instance, passing a list as an argument.
      # Better to not cache than to blow up entirely.
      return self.func(*args)

  def __get__(self, obj, objtype):
    """Support instance methods."""
    return functools.partial(self.__call__, obj)

  @staticmethod
  def reset():
    Memoized.__cache = {}

我遇到的问题是，缓存部分似乎涉及了很多开销（比如在递归函数中）。以以下函数为例，我可以在不使用记忆化的情况下调用 fib(30) 十次，所用时间比使用记忆化的版本还要少。

def fib(n):

   if n in (0, 1):
      return n
   return fib(n-1) + fib(n-2)

有没有人能建议我一个更好的方法来写这个装饰器？（或者指引我找到一个更好（也就是更快）的装饰器，能实现我想要的功能）。

我对保留方法签名或帮助工具“了解”被装饰函数的内容不感兴趣。

谢谢。

附：使用的是 Python 2.7

相关问题：

• Python中的高效备忘录法
• Python Memcached：缓存对象
• python 如何对方法进行记忆化
• 如何对**kwargs进行记忆化？
• Python 可重置的实例方法缓存装饰器
• Python - 缓存属性以避免未来计算
• Python 记忆化/延迟查找属性装饰器
• Python 装饰器、类方法与评估 -- django memoize

Answer 1

这里有一个版本，速度快了很多。不过不幸的是，reset 现在不能完全清空缓存，因为所有的实例都在保存自己本地的函数字典的引用。虽然你可以让它勉强工作：

import functools

class Memoized(object):
  """Decorator that caches a function's return value each time it is called.
  If called later with the same arguments, the cached value is returned, and
  not re-evaluated.
  """

  __cache = {}

  def __init__(self, func):
    self.func = func
    key = (func.__module__, func.__name__)
    if key not in self.__cache:
      self.__cache[key] = {}
    self.mycache = self.__cache[key]

  def __call__(self, *args):
    try:
      return self.mycache[args]
    except KeyError:
      value = self.func(*args)
      self.mycache[args] = value
      return value
    except TypeError:
      # uncachable -- for instance, passing a list as an argument.
      # Better to not cache than to blow up entirely.
      return self.func(*args)

  def __get__(self, obj, objtype):
    """Support instance methods."""
    return functools.partial(self.__call__, obj)

  @classmethod
  def reset(cls):
    for v in cls.__cache.itervalues():
      v.clear()

Answer 2

你其实并没有缓存任何数据，因为每次你设置一个新的缓存值时，都会覆盖掉之前的值：

Memoized.__cache[self.key] = {args : value}

比如：

import functools

class Memoized(object):
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    cache = {}

    def __init__(self, func):
        self.func = func
        self.key = (func.__module__, func.__name__)
        self.cache[self.key] = {}

    def __call__(self, *args):
      try:
          return Memoized.cache[self.key][args]
      except KeyError:
          value = self.func(*args)
          Memoized.cache[self.key][args] = value
          return value
      except TypeError:
          # uncachable -- for instance, passing a list as an argument.
          # Better to not cache than to blow up entirely.
          return self.func(*args)

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

    @staticmethod
    def reset():
        Memoized.cache = {}

• 不使用缓存的 fib(30) 计算结果是：2.86742401123
• 使用缓存的 fib(30) 计算结果是：0.000198125839233

还有一些其他的注意事项：

• 不要使用 __prefix；在这里没有必要，这样只会让代码变得更难看。
• 与其使用一个大的、单一的类属性字典，不如给每个 Memoized 的实例分配一个自己的字典，并保持一个 Memoized 对象的注册表。这样可以提高封装性，也避免了依赖模块和函数名称的奇怪情况。

.

import functools
import weakref

class Memoized(object):
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.

    >>> counter = 0
    >>> @Memoized
    ... def count():
    ...     global counter
    ...     counter += 1
    ...     return counter

    >>> counter = 0
    >>> Memoized.reset()
    >>> count()
    1
    >>> count()
    1
    >>> Memoized.reset()
    >>> count()
    2

    >>> class test(object):
    ...     @Memoized
    ...     def func(self):
    ...         global counter
    ...         counter += 1
    ...         return counter
    >>> testobject = test()
    >>> counter = 0
    >>> testobject.func()
    1
    >>> testobject.func()
    1
    >>> Memoized.reset()
    >>> testobject.func()
    2
    """

    caches = weakref.WeakSet()

    def __init__(self, func):
        self.func = func
        self.cache = {}
        Memoized.caches.add(self)

    def __call__(self, *args):
      try:
          return self.cache[args]
      except KeyError:
          value = self.func(*args)
          self.cache[args] = value
          return value
      except TypeError:
          # uncachable -- for instance, passing a list as an argument.
          # Better to not cache than to blow up entirely.
          return self.func(*args)

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

    @staticmethod
    def reset():
        for memo in Memoized.caches:
            memo.cache = {}

if __name__ == '__main__':
    import doctest
    doctest.testmod()

编辑：添加测试，并使用 weakref.WeakSet。请注意，WeakSet 仅在 2.7 版本中可用（而提问者使用的就是这个版本）；如果你需要在 2.6 版本中使用，请查看编辑历史。