如何加速这个记忆化装饰器？

Question

如何加速这个记忆化装饰器？

3

我需要一个备忘录装饰器，它可以：

备忘实例方法的参数和关键字参数
具有可通过一次调用清除（全局）缓存的缓存（与此使用每个函数缓存的缓存不同：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 = {}

我觉得它的问题在于缓存部分似乎有很多开销（例如对于递归函数）。以以下函数为例，我可以使用非记忆化版本 10 次调用 fib(30)，所需时间比记忆化版本少。

def fib(n):

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

有没有人能够建议一种更好的编写装饰器的方法？（或指向一个更好（即更快）的装饰器来完成我想要的功能）。

我不感兴趣保留方法签名，也不希望帮助内省工具“了解”被装饰函数的任何信息。

谢谢。

P.S. 使用的是Python 2.7

- Gerrat

2个回答

2

这里是一个明显更快的版本。不幸的是，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()

- Omnifarious

1

重置需要成为一个@classmethod，然后是reset(cls)和cls.__cache.itervalues()。 - Nickpick

@Nickpick - 很明显，在我匆忙写下它的那么多年前，我没有完全测试它。 - Omnifarious

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Glenn Maynard · Accepted Answer

你实际上没有缓存任何数据，因为每次设置新的缓存值时，都会覆盖先前的值：

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的版本，请参见编辑历史记录。