Comment créer un décorateur de mémorisation borné en Python?

Question

De toute évidence, une recherche rapide donne un million d'implémentations et de saveurs du décorateur de mémorisation en Python. Cependant, je suis intéressé par une saveur que je n'ai pas pu trouver. Je voudrais qu'il soit tel que le cache des valeurs stockées puisse être d'une capacité fixe. Lorsque de nouveaux éléments sont ajoutés, si la capacité est atteinte, la valeur la plus ancienne est supprimée et remplacée par la valeur la plus récente.

Ce qui me préoccupe, c'est que si j'utilise la mémorisation pour stocker un grand nombre d'éléments, alors le programme se bloque à cause d'un manque de mémoire. (Je ne sais pas dans quelle mesure cette préoccupation peut être bien placée dans la pratique.) Si le cache avait une taille fixe, une erreur de mémoire ne serait pas un problème. Et de nombreux problèmes sur lesquels je travaille changent au fur et à mesure que le programme s'exécute, de sorte que les valeurs initiales mises en cache semblent très différentes des valeurs mises en cache plus tard (et seraient beaucoup moins susceptibles de se reproduire plus tard). C'est pourquoi j'aimerais que les éléments les plus anciens soient remplacés par les éléments les plus récents.

J'ai trouvé la classe OrderedDict et un exemple montrant comment la sous-classer pour spécifier une taille maximale. Je voudrais l'utiliser comme cache, plutôt que comme un dict normal. Le problème est que j'ai besoin que le décorateur memoize prenne un paramètre appelé maxlen qui par défaut est None. S'il s'agit d'un None, alors le cache est illimité et fonctionne normalement. Toute autre valeur est utilisée comme taille du cache.

Je veux que cela fonctionne comme suit:

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

et

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

Voici le code que j'ai jusqu'à présent, mais je ne vois pas comment passer le paramètre dans le décorateur tout en le faisant fonctionner à la fois "nu" et avec un paramètre.

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)

Modifier : en utilisant la suggestion de Ben, j'ai créé le décorateur suivant, qui, je crois, fonctionne comme je l'avais imaginé. Il est important pour moi de pouvoir utiliser ces fonctions décorées avec multiprocessing, et cela a été un problème dans le passé. Mais un test rapide de ce code a semblé fonctionner correctement, même lorsque les tâches sont confiées à un pool de threads.

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

Ici, memoize est utilisé comme une fonction qui est appelée sur un seul argument de fonction, et renvoie une fonction. memoize est un décorateur.

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

Ici, memoize est utilisé comme une fonction qui est appelée sur un seul argument entier et renvoie une fonction, et cette fonction retournée est elle-même utilisée comme décorateur, c'est-à-dire qu'elle est appelée sur un seul argument de fonction et renvoie une fonction. memoize est une fabrique de décorateurs .

Donc, pour unifier ces deux éléments, vous allez devoir écrire du mauvais code. La façon dont je le ferais probablement est de faire ressembler à memoize:

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

De cette façon, si vous voulez passer des paramètres, vous les passez toujours comme arguments de mot-clé, laissant le func (qui devrait être un paramètre de position) non défini, et si vous voulez juste que tout soit par défaut, cela fonctionnera comme par magie en tant que décorateur directement. Cela signifie que @memoize(200) vous donnera une erreur; vous pouvez éviter cela en effectuant à la place une vérification de type pour voir si func est appelable, ce qui devrait bien fonctionner en pratique mais n'est pas vraiment très "pythonique".

Une alternative serait d'avoir deux décorateurs différents, disons memoize et bounded_memoize. Le memoize illimité peut avoir une implémentation triviale en appelant simplement bounded_memoize avec maxlen défini sur None, donc cela ne vous coûte rien en implémentation ou en maintenance.

En règle générale, j'essaie d'éviter de modifier une fonction pour implémenter deux ensembles de fonctionnalités uniquement liés de manière tangentielle, en particulier lorsqu'ils ont des signatures si différentes. Mais dans ce cas, l ' utilisation du décorateur est naturelle (exiger @memoize() serait assez sujet aux erreurs, même si c'est plus cohérent d'un point de vue théorique), et vous allez probablement l'implémenter une fois et l'utiliser plusieurs fois, donc la lisibilité au point d'utilisation est probablement la préoccupation la plus importante.

Answer 2

Vous voulez écrire un décorateur qui prend un argument (la longueur maximale du BoundedOrderedDict) et renvoie un décorateur qui mémorisera votre fonction avec un BoundedOrderedDict de la taille appropriée:

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

Vous pouvez l'utiliser comme ceci:

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

Modifier: Oups, j'ai manqué une partie de la question.Si vous voulez que l'argument maxlen du décorateur soit facultatif, vous pouvez faire quelque chose comme ceci:

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

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

La syntaxe actuelle permet également aux déclarations de décorateur d'appeler une fonction qui renvoie un décorateur:

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

Ceci équivaut à:

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

De plus, je ne sais pas si j'utiliserais OrderedDict pour cela, j'utiliserais un Ring Buffer, ils sont très faciles à implémenter.