Skip to content

Solution du problème Caching

Vous trouverez ici la solution pour l'exercice suivant :

Caching

Exercice de base

Un décorateur qu'est-ce que c'est? C'est une fonction qui retourne une (autre) fonction. Le but étant de faire en sorte que la fonction retournée soit "augmentée" de certaines fonctionalités. Si on defini un decorateur deco ainsi: 

def deco(function):
    return function

Il n'aura aucun effet car il retourne la fonction source sans la modifier.

Si on veut decorer une fonction my_function, on peut faire ainsi: 

my_function = deco(my_function)
my_function se retrouve donc ecrasée par sa version "décorée".

Afin de rendre les choses plus facile pour le developpeur (et potentiellement plus lisible aussi), un decorateur peut etre appliqué au moment de la définition d'une fonction en utilisant le caractère @: 

@deco
def my_function():
  ...
Ce qui est equivalent à: 
def my_function():
  ...
my_function = deco(my_function)

Maintenant que l'on en sait un peut plus sur les décorateurs il va falloir écrire le notre.

Pour faire du caching, il va falloir stocker les valeurs de retour des fonctions que l'on va decorer. Comme notre décorateur sera le meme pour toutes les fonctions qui seront décorees, il va falloir stocker les valeurs de retour pour chaque fonction décorée. Le plus simple est donc d'utiliser un dictionaire dont les clés seront les fonctions que l'on veut décorer.

cache = dict()
def caching(function):
    def wrapper():
        if function not in cache:
            cache[function] = function()
        return cache[function]
    return wrapper

Ceci fonctionnera très bien, a partir du moment ou on decorrera des fonctions qui ne prennent pas de parametres. Vous admetterez que cela est rarement le cas... On pourrait faire un décorateur pour les fonctions sans parametres, puis un autre quand il y a un parametre, puis... Mais bon c'est pas possible, vous vous doutez bien qu'il y a un moyen de faire cela proprement.

En python, on peut utiliser une construction speciale pour les fonctions qui permet de récuperer tous les parametres passés par "position": 

def function(*args):
    ...
Si on utilise un parametre prefixe par *, alors il recevra tous les parametres passes par position. Ce sera un tuple contenant les differents parametres.

Note

On peut mettre un parametre prefixé par * en seconde, troisieme, ou plus, position, si des parametres sont necessaires et d'autres optionels

Mais en python on peut aussi passr des parametres avec leur nom keyword arguments ce qui est tres pratique pour ne donner qu'une seule valeure de parametre et laisser les autres à leur valeure par defaut. Pour cela, on utilise un parametre prefixé par **. Ceci est souvent utilise en conjonction des arguments positionels. 

def function(*args, **kwargs):
    pass

Tout cela a pour but de pouvoir decorer n'importe quelle fonction: 

cache = dict()
def caching(function):
    def wrapper(*args, **kwargs):
        if function not in cache:
            cache[function] = function(*args, **kwargs)
        return cache[function]
    return wrapper

Note

On peut utiliser un tuple et un dictionnaire pour faire comem si on donnait les parametres positioneles et par keyword en prefixant le tuple par * et le dictionaire par **. C'est facile a reconnaitre, car la notation est la meme dans les 2 cas.

Revenons-en à notre exercice: ça ne marche pas, et pour cause, quelques soient les parametres nous retournons toujours la premiere valeure calculée. Il va donc falloir stocker les valeures de retour en fonction des parametres. 

cache = dict()
def caching(function):
    cache[function] = dict()
    def wrapper(*args, **kwargs):
        key = args
        if key not in cache[function]:
            cache[function][key] = function(*args, **kwargs)
        return cache[function][key]
    return wrapper

Ainsi nous genrons le caching pour les parametres donnes par position. Pas pour les kwargs, "mais pourquoi?" me direz-vous. C'est tres simple, pour être stocké dans un dictionnaire, une clé dout pouvoir être hashée or, un dictionnaire python ne peut pas. Pour s'en convaincre, il suffira de taper le code suivant qui lèvera une exception de type TypeError: 

>>> hash(dict())

Il va donc falloir ruser un peu: 

cache = dict()
def caching(function):
    cache[function] = dict()
    def wrapper(*args, **kwargs):
        key = hash((args, repr(kwargs)))
        if key not in cache[function]:
            cache[function][key] = function(*args, **kwargs)
        return cache[function][key]
    return wrapper

Et voila qui resoud le problème de base.

Info

Dans les tests unitaires, il y a un calcul de fonction de fibonacci de 280; de quoi utiliser votre CPU pour longtemps. Grace au décorateur de caching, ce calcul s'efecue en moins d'une seconde sur mon netbook ;)

Bonus 1

Premier bonus: ajout d'informations utiles sur le caching que nous avons mis en place. Cela se fait sans réél problème à partir du moment ou on sait qu'une fonction est un objet qui peut avoir des attributs: 

cache = dict()
def caching(function):
    cache[function] = dict()
    def wrapper(*args, **kwargs):
        key = hash((args, repr(kwargs)))
        if key not in cache[function]:
            cache[function][key] = function(*args, **kwargs)
            wrapper.computed_count += 1
        else:
            wrapper.served_count += 1
        return cache[function][key]
    wrapper.computed_count = 0
    wrapper.served_count = 0
    return wrapper

Le seul probleme concerne missed_count. En effet, dans notre code, à quoi cela peut-il correspondre. Vous vous souvenez le probleme de hashage pour les dictionnaires, et bien il n'y a pas que les dictionnaires qui ne sont pas hashables. Si du code client utilise une valeure non hashable comme parametre, et bienn notre code plantera.

Il va donc falloir protéger notre decorateur de ce genre de desagrements, et c'est a cela que correspondra missed_count: le nombre de fois ou notre caching n'aura pas su mettre une valeure en cache. Ce qui nous donne:

cache = dict()
def caching(function):
    cache[function] = dict()
    def wrapper(*args, **kwargs):
        try:
            key = hash((args, repr(kwargs)))
        except TypeError:
            wrapper.computed_count += 1
            wrapper.missed_count += 1
            return function(*args, **kwargs)
        if key not in cache[function]:
            cache[function][key] = function(*args, **kwargs)
            wrapper.computed_count += 1
        else:
            wrapper.served_count += 1
        return cache[function][key]
    wrapper.computed_count = 0
    wrapper.served_count = 0
    wrapper.missed_count = 0
    return wrapper

Note

il ne faut pas oublier d'incrementer le computed_count quand on rate le hash, car on calcule bien la veleure de retour de la fonction.

Voila pour le premier bonus.

Bonus 2

Conserver les doctext et autres attributs de la fonction décorée. Effectivement si on demande la documentation associée a notre fonction décorée, on pourra voir qu'elle est vide; et pour cause, c'est la documentation de wrapper et pas la documentation de function que l'on obtient.

Pour copier la documentation rien de plus simple: 

...
def caching(function):
    ...
    def wrapper(*args, **kwargs):
        ...
    ...
    wrapper.__doc__ = function.__doc__
    return wrapper

En effet la dunder variable __doc__ contient le texte de la documentation de la fonction. Donc en la copiant pour notre fonction wrapper, on copie donc la documentation.

Note

On peut aussi augmenter la documentation dynamiquement, afin, par exemple, de dire que la fonction est accellérée en utilisant un cache. Cela peut être utile lorsqu'on décore une fonction dans du code client; mais si on decore la fonction au niveau de sa definition, il semble bien plus logique que la documentation indique elle même qu'elle utilise un cache.

On pourrait penser que cela est suffisant, mais en lien avec cette page de la doc officielle on peut voir qu'il n'y a pas que __doc__ comme dunder attribut à copier. Il y en a (pour l'instant) 5, mais qui sait, peut-être que dans 2 ans il y en aura le double à copier, et il est complique de maintenir ce genre de chose pour chaque decorateur que nous écrirons.

C'est pour cela que Python est livré avec le module functools, et plus particulièrement le décorateur wraps, qui nous permet (simplement) de copier les informations d'une fonction lorsqu'on écrit un décorateur. Comme c'est livré avec Python, on peut legitimement penser que son code sera toujours a jour des derniers changements du langage en lui même...

Voici donc ma version: 

import functools
cache = dict()
def caching(function):
    cache[function] = dict()
    @functools.wraps(function)
    def wrapper(*args, **kwargs):
        try:
            key = hash((args, repr(kwargs)))
        except TypeError:
            wrapper.computed_count += 1
            wrapper.missed_count += 1
            return function(*args, **kwargs)
        if key not in cache[function]:
            cache[function][key] = function(*args, **kwargs)
            wrapper.computed_count += 1
        else:
            wrapper.served_count += 1
        return cache[function][key]
    wrapper.computed_count = 0
    wrapper.served_count = 0
    wrapper.missed_count = 0
    return wrapper

Bonus 3

Enfin, pour le dernier bonus, il fallait faire en sorte de ne stocker qu'une quantité limité de données dans le cache, afin de ne pas faire exploser la quantité de mémoire utilisée (parfois cela pourait être préjudiciable aux calculs, si on doit swapper par exemple).

Tout d'abord, nous allons devoir ajouter des parametres à notre décorateur. Et pour cela il nous faut revenir à la première possibilité d'utilisation des décorateurs: une fonction qui retourne une autre fonction. 

def deco(function):
    def wrapper():
        ...
    return wrapper

decorated_function = deco(my_function)
Si nous voulons ajouter des parametres à ce décorateur, il n'y a pas moyen en changeant simplement la signature du décorateur. En effet, un décorateur ne prend toujours qu'un parametre: une fonction à décorer. Mais donc, serait-ce impossible? Surement pas sinon je l'aurais pas demandé ;)

La façon simple, même si cela peut paraitre compliqué au début: il va nous falloire écrire une fonction qui retourne un décorateur, donc une fonction qui retourne une fonction qui retourne une fonction... Si on ajoute un peu de context à cela: une fonction qui prend des parametres qui retourne une fonction qui prend une fonction pour la decorée qui retourne une fonction qui est décorée.

Donc avec le code de l'exemple simple précédent: 

def deco(my_parameter):
    def internal_decorator(function):
        # do something with my_parameter
        def wrapper():
            # do something with my_parameter
            ...
        return wrapper
    return internal_decorator
On a donc une fonction deco qui prend un parametre my_parameter et qui retourne un decorateur internal_decorator. Qui est lui même une fonction internal_decorator qui prend comme parametre une fonction function et qui retourne une fonction wrapper.

Tel quel ce n'est pas si compliqué, et pour vous en convaincre, regardons ce qui se passe en fait quand on décore une fonction sans utiliser @: 

decorated = deco(123)(my_function())
Cela va donc donner: 
decorated = internal_decorator(my_function)
Ce qui au final donne: 
decorated = wrapper
Bien sur le context de chaque fonction fait que ce n'est pas tout à fait pareil, mais dans l'idée cela peut aider de le voir comme cela.

Bien, voila qui nous laisse encore un point épineux: dans le cas du dessus j'ai donné un parametre obligatoire, mais dans notre exercice, le parametre est optionel, ce n'est pas pour rien... Au niveau de l'ecriture, cela ne change pas grand chose par rapport a l'exemple précédent, et au python classique: 

def deco(my_parameter=123):
    def internal_decorator(function):
        # do something with my_parameter
        def wrapper():
            # do something with my_parameter
            ...
        return wrapper
    return internal_decorator

Sauf que lorsque nous allons mettre notre decorateur avec un parametre, cela sera: 

@deco(12)
def my_function():
Et si nous ne mettons pas de parametre (car nous voulons qu'il soit optionel, en gros que l'utilisateur puisse ne pas le mettre): 
@deco
def my_function():
Python va donc faire ce qu'il doit (vis a vis de sa documentation) il va appeler deco sur my_function. Donc dans ce cas la, my_parameter vaudra my_function et pas un entier...

Il nous faut donc gérer cela: 

def deco(my_parameter=123):
    def internal_decorator(function):
        # do something with my_parameter
        def wrapper():
            # do something with my_parameter
            ...
        return wrapper
    if callable(my_parameter):
        # we are using decorator without any my_parameter
        function = my_parameter
        my_parameter = 123  # default value, because it will be used in internal_decorator
        return internal_decorator(function)
    else:
        # we are using decorator with a parameter
        return internal_decorator

Oui je sais c'est un peu ardu, mais en fait on ne fait que verifier que my_parameter n'est pas une fonction pour l'utiliser normalement, et sinon, on remet les choses en ordre pour retourner notre fonction décorée comme il faut.

Pour notre exercice, il va donc falloir faire en sorte de ne stocker que les N dernières valeures et pas plus. Comme les dictionaires en python3 sont ordonés, il nous suffi de verifier, lorsqu'on ajoute une nouvelle valeure, la taille et de supprimer la première entrée. Ce qui se fera simplement: 

>>> del my_dict[my_dict.keys()[0]]

Voici donc ma solution pour l'exercice: 

import functools

caches = dict()
def caching(store_size=None):
    def inner_decorator(function):
        function_key = hash(function)
        caches[function_key] = dict()

        @functools.wraps(function)
        def wrapper(*args, **kwargs):
            try:
                key = hash((args, repr(kwargs)))
            except TypeError:
                wrapper.computed_count += 1
                wrapper.missed_count += 1
                return function(*args, **kwargs)

            if key in caches[function_key]:
                wrapper.served_count += 1
                return caches[function_key][key]

            result = function(*args, **kwargs)
            caches[function_key][key] = result
            if store_size and len(caches[function_key]) > store_size:
                del caches[function_key][
                    list(caches[function_key].keys())[0]
                ]
            wrapper.computed_count += 1
            return result
        wrapper.computed_count = 0
        wrapper.served_count = 0
        wrapper.missed_count = 0
        return wrapper

    if callable(store_size):
        function = store_size
        store_size = None
        return inner_decorator(function)
    else:
        return inner_decorator

Voila, il y a de quoi s'amuser avec les décorateurs, et ajouter simplement des fonctionalités à des fonctions (et même de les enlever simplement en commentant le décorateur).

Dernière petite note

Il n'aura pas échapé aux personnes les plus curieuses, qui auront été sur la doc officielle de functools, qu'il existe deja un décorateur de mémoïsation cache et un dédié a la memoïsation à taille maximale lru_cache (Last Recently Used).