¿Cómo creo un decorador de memorización limitado en Python?

Question

Obviamente, una búsqueda rápida produce un millón de implementaciones y sabores del decorador de memorización en Python. Sin embargo, estoy interesado en un sabor que no he podido encontrar. Me gustaría tenerlo de tal manera que el caché de los valores almacenados pueda tener una capacidad fija. Cuando se agregan nuevos elementos, si se alcanza la capacidad, entonces se elimina el valor más antiguo y se reemplaza con el valor más nuevo.

Mi preocupación es que, si uso memoización para almacenar muchos elementos, entonces el programa se bloqueará debido a la falta de memoria. (No sé cuán bien ubicado puede estar esta preocupación en la práctica). Si el caché fuera de tamaño fijo, entonces un error de memoria no sería un problema. Y muchos problemas en los que trabajo en el cambio a medida que se ejecuta el programa para que los valores almacenados en caché iniciales se vean muy diferentes de los valores cachorros posteriores (y sería mucho menos probable que se repita más adelante). Es por eso que me gustaría que las cosas más antiguas fueran reemplazadas por las cosas más nuevas.

Encontré el OrderedDict clase y un ejemplo que muestra cómo subclasificarlo para especificar un tamaño máximo. Me gustaría usar eso como mi caché, en lugar de una normalidad dict. El problema es que necesito que el decorador de memo de memo se llame un parámetro llamado maxlen ese predeterminado es None. Si esto es None, entonces el caché no tiene límites y funciona como normal. Cualquier otro valor se usa como tamaño para el caché.

Quiero que funcione como lo siguiente:

@memoize
def some_function(spam, eggs):
    # This would use the boundless cache.
    pass

y

@memoize(200)  # or @memoize(maxlen=200)
def some_function(spam, eggs):
    # This would use the bounded cache of size 200.
    pass

A continuación se muestra el código que tengo hasta ahora, pero no veo cómo pasar el parámetro al decorador mientras lo hace funcionar tanto "desnudo" como con un parámetro.

import collections
import functools

class BoundedOrderedDict(collections.OrderedDict):
    def __init__(self, *args, **kwds):
        self.maxlen = kwds.pop("maxlen", None)
        collections.OrderedDict.__init__(self, *args, **kwds)
        self._checklen()

    def __setitem__(self, key, value):
        collections.OrderedDict.__setitem__(self, key, value)
        self._checklen()

    def _checklen(self):
        if self.maxlen is not None:
            while len(self) > self.maxlen:
                self.popitem(last=False)

def memoize(function):
    cache = BoundedOrderedDict()  # I want this to take maxlen as an argument
    @functools.wraps(function)
    def memo_target(*args):
        lookup_value = args
        if lookup_value not in cache:
            cache[lookup_value] = function(*args)
        return cache[lookup_value]
    return memo_target

@memoize
def fib(n):
    if n < 2: return 1
    return fib(n-1) + fib(n-2)

if __name__ == '__main__':
    x = fib(50)
    print(x)

Editar: Usando la sugerencia de Ben, creé el siguiente decorador, que creo que funciona de la manera que imaginaba. Es importante para mí poder usar estas funciones decoradas con multiprocessing, y eso ha sido un problema en el pasado. Pero una prueba rápida de este código parecía funcionar correctamente, incluso cuando cultivaba los trabajos a un grupo de hilos.

def memoize(func=None, maxlen=None):
    if func:
        cache = BoundedOrderedDict(maxlen=maxlen)
        @functools.wraps(func)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = func(*args)
            return cache[lookup_value]
        return memo_target
    else:
        def memoize_factory(func):
            return memoize(func, maxlen=maxlen)
        return memoize_factory

Answer 1

@memoize
def some_function(spam, eggs):
    # This would use the boundless cache.
    pass

Aquí memoize se usa como una función que se llama en un argumento de una sola función y devuelve una función. memoize es decorador.

@memoize(200)  # or @memoize(maxlen=200)
def some_function(spam, eggs):
    # This would use the bounded cache of size 200.
    pass

Aquí memoize se usa como una función que se llama en un solo argumento entero y devuelve una función, y que la función devuelta se usa en sí misma como decorador, es decir, se llama en un argumento de una sola función y devuelve una función. memoize es un fábrica decoradora.

Entonces, para unificar a estos dos, tendrá que escribir un código feo. La forma en que probablemente lo haría es tener memoize se parece a esto:

def memoize(func=None, maxlen=None):
    if func:
        # act as decorator
    else:
        # act as decorator factory

De esta manera si quieres pasar los parámetros siempre pasarlos como argumentos de palabras clave, dejando func (que debería ser un parámetro posicional) no lo establece, y si solo desea que todo sea predeterminado, funcionará mágicamente como decorador directamente. Esto significa @memoize(200) te dará un error; podría evitarlo haciendo algún tipo de verificación para ver si func es llamable, lo que debería funcionar bien en la práctica, pero no es realmente muy "pitónico".

Una alternativa sería tener dos decoradores diferentes, digamos memoize y bounded_memoize. El ilimitado memoize puede tener una implementación trivial simplemente llamando bounded_memoize con maxlen ajustado a None, por lo que no le cuesta nada en implementación o mantenimiento.

Normalmente, como regla general, trato de evitar destrozar una función para implementar dos conjuntos de funcionalidad relacionados con tangencialmente, especialmente Cuando tienen firmas tan diferentes. Pero en este caso hace que el usar del decorador es natural (que requiere @memoize() Sería muy propenso a un error, aunque sea más consistente desde una perspectiva teórica), y presumiblemente implementará esto una vez y lo use muchas veces, por lo que la lectura en el punto de uso es probablemente la preocupación más importante.

Answer 2

Quieres escribir un decorador que tome una discusión (la longitud máxima del BoundedOrderedDict) y devuelve un decorador que memorice tu función con un BoundedOrderedDict del tamaño apropiado:

def boundedMemoize(maxCacheLen):
    def memoize(function):
        cache = BoundedOrderedDict(maxlen = maxCacheLen)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = function(*args)
            return cache[lookup_value]
        return memo_target
    return memoize

Puedes usarlo así:

@boundedMemoize(100)
def fib(n):
    if n < 2: return 1
    return fib(n - 1) + fib(n - 2)

Editar: Vaya, perdió parte de la pregunta. Si desea que el argumento de Maxlen al decorador sea opcional, podría hacer algo como esto:

def boundedMemoize(arg):
    if callable(arg):
        cache = BoundedOrderedDict()
        @functools.wraps(arg)
        def memo_target(*args):
            lookup_value = args
            if lookup_value not in cache:
                cache[lookup_value] = arg(*args)
            return cache[lookup_value]
        return memo_target

    if isinstance(arg, int):
        def memoize(function):
            cache = BoundedOrderedDict(maxlen = arg)
            @functools.wraps(function)
            def memo_target(*args):
                lookup_value = args
                if lookup_value not in cache:
                    cache[lookup_value] = function(*args)
                return cache[lookup_value]
            return memo_target
        return memoize

Answer 3

De http://www.python.org/dev/peps/pep-0318/

La sintaxis actual también permite que las declaraciones del decorador llamen a una función que devuelve un decorador:

@decomaker(argA, argB, ...)
def func(arg1, arg2, ...):
    pass

Esto es equivalente a:

func = decomaker(argA, argB, ...)(func)

Además, no estoy seguro de si usaría Ordereddict para esto, usaría un búfer de anillo, son muy fáciles de implementar.