¿Qué se puede hacer para acelerar este decorador de memoizaciones?

Lo que quiero es un decorador de memorias que:

  • puede memorizar métodos de instancia con argumentos y argumentos de palabras clave
  • tiene una memoria caché que se puede borrar (globalmente) con una llamada (frente a esta que usa una memoria caché por función: decorador de memoización de métodos de instancias que se puede restablecer en Python )
  • es razonablemente eficiente

He ajustado un ejemplo que vi y se me ocurrió lo siguiente:

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 = {} 

Mi problema con esto es que la parte de almacenamiento en caché parece implicar una gran cantidad de gastos generales (por ejemplo, para funciones recursivas). Usando la siguiente función como ejemplo, puedo llamar a fib (30) diez veces con la versión no memorizada en menos tiempo que la versión memorizada.

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

¿Alguien puede sugerir una mejor manera de escribir este decorador? (o apúntame a un decorador mejor (es decir, más rápido) que hace lo que quiero). No estoy interesado en conservar las firmas de los métodos ni en ayudar a las herramientas de introspección a “saber” nada sobre la función decorada.

Gracias.

PS utilizando python 2.7

En realidad, no está guardando en caché ningún dato, porque cada vez que establece un nuevo valor en caché sobrescribe el anterior:

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

p.ej.

 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) sin almacenamiento en caché: 2.86742401123
  • fib (30) con almacenamiento en caché: 0.000198125839233

Algunas otras notas:

  • No use __prefix ; No hay ninguna razón para hacerlo aquí y solo uglifica el código.
  • En lugar de utilizar un dict único, monolítico, de atributo de clase, Memoized cada instancia de Memoized su propio Memoized , y mantenga un registro de objetos Memoized . Esto mejora la encapsulación y elimina la rareza de dependiendo de los nombres de módulo y función.

.

 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() 

Editado: agregue pruebas y use weakref.WeakSet. Tenga en cuenta que WeakSet solo está disponible en 2.7 (que utiliza el OP); para una versión que funciona en 2.6, vea el historial de edición.

Aquí hay una versión que es significativamente más rápida. Lamentablemente, el reset ya no puede borrar completamente la memoria caché ya que todas las instancias almacenan su propia copia local de la referencia al diccionario por función. Aunque puedes hacer que funcione:

 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()