python - 可以做些什么来加速这个 memoization 装饰器？

Question

我想要的是一个内存装饰器:

• 可以内存带有参数和关键字参数的实例方法
• 有一个可以通过一次调用(与使用每个函数缓存的调用:python resettable instance method memoization decorator 相比)(全局)清除的缓存
• 相当高效

我对我看到的一个例子进行了调整，并得出以下结论:

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)

谁能建议一个更好的方法来编写这个装饰器？ (或者给我指出一个更好(即更快)的装饰器来做我想要的)。我对保留方法签名或帮助内省(introspection)工具“了解”有关修饰函数的任何信息不感兴趣。

谢谢。

附言使用 python 2.7

Answer 1

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

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(OP 正在使用)中可用；对于适用于 2.6 的版本，请参阅编辑历史记录。