Come posso creare un decoratore di memoria limitato in Python?

Question

Ovviamente, una rapida ricerca produce un milione di implementazioni e sapori del decoratore di memoria di Python. Tuttavia, sono interessato a un sapore che non sono stato in grado di trovare. Vorrei averlo in modo tale che la cache dei valori memorizzati possa essere di capacità fissa. Quando vengono aggiunti nuovi elementi, se viene raggiunta la capacità, il valore più antico viene rimosso e viene sostituito con il valore più recente.

La mia preoccupazione è che, se utilizzo la memorizzazione per archiviare molti elementi, allora il programma si schianterà a causa della mancanza di memoria. (Non so quanto sia ben posizionata questa preoccupazione in pratica.) Se la cache fosse di dimensioni fisse, un errore di memoria non sarebbe un problema. E molti problemi che lavoro sulla modifica eseguono il programma in modo che i valori memorizzati con cache iniziali sembrerebbero molto diversi dai valori memorizzati nella cache successivi (e avrebbero molte meno probabilità di ripresentarsi in seguito). Ecco perché vorrei che le cose più antiche fossero sostituite dalle cose più recenti.

Ho trovato il OrderedDict classe e un esempio che mostra come sottoclassarlo per specificare una dimensione massima. Vorrei usarlo come cache, piuttosto che un normale dict. Il problema è che ho bisogno che il decoratore della memoria prenda un parametro chiamato maxlen che è predefinito a None. Se è None, quindi la cache è illimitata e funziona normalmente. Qualsiasi altro valore viene utilizzato come dimensione per la cache.

Voglio che funzioni come le seguenti:

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

e

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

Di seguito è riportato il codice che ho finora, ma non vedo come passare il parametro nel decoratore mentre lo fa funzionare sia "nudo" che con un parametro.

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)

Modificare: Usando il suggerimento di Ben, ho creato il seguente decoratore, che credo funzioni nel modo in cui ho immaginato. È importante per me essere in grado di utilizzare queste funzioni decorate multiprocessing, e questo è stato un problema in passato. Ma un rapido test di questo codice sembrava funzionare correttamente, anche quando coltiva i lavori a un pool di thread.

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

Qui memoize viene utilizzato come funzione che viene chiamata su un argomento di singola funzione e restituisce una funzione. memoize è un decoratore.

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

Qui memoize è usato come funzione che viene chiamata su un singolo argomento intero e restituisce una funzione e che la funzione restituita è essa stessa usata come decoratore, cioè è chiamata su un argomento di una singola funzione e restituisce una funzione. memoize è un fabbrica di decoratori.

Quindi, per unificare questi due, dovrai scrivere un codice brutto. Il modo in cui probabilmente lo farei è averlo memoize Assomiglia a questo:

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

In questo modo se vuoi passare i parametri sempre Passali come argomenti di parole chiave, lasciando func (che dovrebbe essere un parametro posizionale) non acceso, e se vuoi solo che tutto predefinito funzionerà magicamente come decoratore direttamente. Questo significa @memoize(200) ti darà un errore; Potresti evitarlo invece facendo un controllo di tipo per vedere se func è richiamabile, che dovrebbe funzionare bene in pratica ma non è molto "pitone".

Un'alternativa sarebbe quella di avere due decoratori diversi, diciamo memoize e bounded_memoize. Il illimitato memoize può avere un'implementazione banale solo chiamando bounded_memoize insieme a maxlen impostato None, quindi non ti costa nulla in implementazione o manutenzione.

Normalmente come regola generale cerco di evitare di sfruttare una funzione per implementare due set di funzionalità solo tangenzialmente correlati, specialmente Quando hanno firme così diverse. Ma in questo caso fa il uso del decoratore è naturale (che richiede @memoize() Sarebbe piuttosto soggetto a errori, anche se è più coerente da una prospettiva teorica), e presumibilmente lo implementerai una volta e lo utilizzerai molte volte, quindi la leggibilità al punto di utilizzo è probabilmente la preoccupazione più importante.

Answer 2

Vuoi scrivere un decoratore che prende una discussione (la lunghezza massima del BoundedOrderedDict) e restituisce un decoratore che memorizzerà la tua funzione con a BoundedOrderedDict della dimensione appropriata:

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

Puoi usarlo in questo modo:

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

Modificare: Whoops, ha perso parte della domanda. Se vuoi che l'argomento Maxlen al decoratore sia facoltativo, potresti fare qualcosa del genere:

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

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

La sintassi attuale consente inoltre alle dichiarazioni del decoratore di chiamare una funzione che restituisce un decoratore:

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

Questo è equivalente a:

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

Inoltre, non sono sicuro se userei OrderEdDict per questo, userei un buffer ad anello, sono molto facili da implementare.