Outils pour utilisateurs

Outils du site


decorateurs_cache

Faire un cache par décorateur pour accélérer le calcul des fonctions longues

Problématique

Imaginons une fonction de calcul s'exécutant en plusieurs secondes (ou plus).

Si, peu après, on redemande le même calcul, c'est dommage de perdre du temps en recalculant une valeur qu'on a déjà calculée.

Et si on avait gardé le couple [arguments, résultat], il suffirait de reconnaitre les arguments pour donner le résultat tout de suite! Voilà l'idée du cache!

En plus, en utilisant les techniques des décorateurs pour fabriquer le cache, on pourra l'appliquer à n'importe quelle fonction d'un programme sans la modifier, ni même avoir accès à son code.

Bien sûr, pour que le cache d'une fonction ait un sens, il faut:

  • que la fonction ait des résultats non aléatoires qui ne dépendent que de ses arguments: un même jeu d'arguments doit toujours donner le même résultat.
  • que les arguments aient une chance raisonnable de se retrouver par la suite. Sinon, le cache se contentera de stocker les données sans jamais les restituer.

Code proposé

Comme on aura besoin de conserver les résultats précédents [arguments, resultat] de la fonction décorée, le décorateur sera sous forme de classe.

Comme, en plus, on pourrait demander à ce que le cache soit limité en taille, on va prendre un décorateur 'avec arguments'.

Voilà le code proposé (largement auto-documenté):

# Python v2.7
 
import functools
 
#############################################################################
class decocache(object):
    """Décorateur qui remplit une fonction de cache"""
 
    adr = {} # dictionnaire de classe pour porter les adresses d'instances
 
    # =======================================================================
    def __init__(self, maxicache=0):
        """Initialisation"""
 
        self.maxicache = maxicache # nb maxi d'éléments du cache si >0
        self.cache = [] # initialisation du cache
 
    # =======================================================================
    def __call__(self, fonc): 
 
        # -------------------------------------------------------------------
        @functools.wraps(fonc) # pour que fonc garde son nom et son docstring
        def appelfonc(*args, **kwargs):
            """ méthode appelée à chaque appel de la fonction décorée """
 
            # calcul du dictionnaire des arguments passés à la fonction décorée
            dicvars = self.calculargs(args, kwargs, varsfn, dico_varsfn_def)
 
            # recherche dans le cache
            for var, val in self.cache:
                if var == dicvars:
                    # on a trouvé les mêmes arguments dans le cache!
                    return val # retour du précédent résultat de la fonction 
 
            # ici, on n'a pas trouvé dans le cache: on exécute la fonction
            result = fonc(*args, **kwargs)
 
            # mise en cache si la taille du cache n'est pas dépassée
            if self.maxicache==0 or len(self.cache)<self.maxicache:
                self.cache.append([dicvars, result])
 
            # et on retourne le résultat
            return result        
 
        # -------------------------------------------------------------------
        # initialisation de la var. de classe 'adr' avec l'adresse de l'instance
        self.__class__.adr[fonc.func_name] = self # adresse de l'inst. de classe
 
        # cacul des variables passées à la fonction dans sa définition
        varsfn, dico_varsfn_def = self.calculvars(fonc)
 
        # retourne la fonction à appeler à chaque appel de la fonction décorée
        return appelfonc
 
    # =======================================================================
    def calculvars(self, fonc):
        """Calcul des variables passées à la fonction décorée"""
        # liste complète des variables passées à la fonction décorée
        varsfn = list(fonc.func_code.co_varnames[:fonc.func_code.co_argcount])
        # liste des arguments déclarées par défaut
        argsfn_def = fonc.func_defaults
        if argsfn_def == None:
            argsfn_def = ()
        # liste des variables par défaut
        varsfn_def = varsfn[len(varsfn)-len(argsfn_def):]
        # dictionnaire des variables par défaut avec leurs valeurs par défaut
        dico_varsfn_def = dict(zip(varsfn_def, argsfn_def))
        # retour de la liste des var. et du dictionnaire des var. par défaut        
        return varsfn, dico_varsfn_def
 
    # =======================================================================
    def calculargs(self, args, kwargs, varsfn, dico_varsfn_def):    
        """Calcul du dictionnaire des arguments passés à la fonction décorée"""
        # initialisation du dico avec les arguments passés par position
        dicvars = dict(zip(varsfn[:len(args)], args))
        # on complète avec les arguments par défaut effectivement passés 
        dicvars.update(kwargs)
        # on complète avec les éventuels arguments par défaut NON passés
        for c in dico_varsfn_def.keys():
            if c not in dicvars.keys():
                dicvars[c] = dico_varsfn_def[c]
        # retour du dictionnaire complet des variables:arguments de fonc        
        return dicvars
 
    # =======================================================================
    def reinit(self):
        """méthode pour vider le cache"""
        self.cache = []

Utilisation type:

@decocache()
def test1(a, b, c=5):
    #...
    # calcul long
    #...
    return resultat
 
@decocache(1000)
def test2(a, b, c, d=5):
    #...
    # calcul long
    #...
    return resultat

Dans le 1er cas de la fonction décorée 'test1', le cache n'a pas de limite de taille (mais les parenthèses sont cependant nécessaires!).

Dans le 2e cas, le cache est limité à 1000 couples: [arguments, résultat]

Vous voyez aussi que le décorateur-cache s'adapte automatiquement à n'importe quelle configuration des arguments passés par position ou par défaut.

Avantage du cache en décorateur: on peut ainsi mettre en cache plusieurs fonctions différentes d'un même programme avec la seule ligne ajoutée “@decocache()” avant chaque fonction. Avec ou sans limite de taille du cache.

On peut vider le cache à tout moment avec:

  • pour la fonction décorée test1: decocache.adr['test1'].reinit()
  • pour la fonction décorée test2: decocache.adr['test2'].reinit()

Et, rien n'empêche d'ajouter des méthodes et attributs supplémentaires pour enregistrer sur disque le contenu du cache pour le recharger à la session suivante !

Exemple d'utilisation

On va montrer par un exemple simplifié l'intérêt du cache.

Le code suivant s'ajoute au code précédent qui décrit la classe decocache

import functools
from random import randint
import time
 
#############################################################################
#
# recopier ici la classe decocache ci-dessus
#
#############################################################################
def tempsexec(fonc):
    """décorateur qui affiche le temps d'exécution de la fonction décorée"""
    @functools.wraps(fonc)
    def _tempsexec(*args, **kwargs):
        t = time.clock()
        result = fonc(*args, **kwargs)
        t = time.clock()-t
        print "temps d'exécution: %.7f" % (t)
        return result
    return _tempsexec
 
#############################################################################
 
@tempsexec
@decocache()
def calcul(a):
    time.sleep(1)
    return 2*a
 
#############################################################################
 
for i in xrange(0,100):
    a = randint(1,20)
    x = calcul(a)
    print i, a, x

On utilise pour ce test un décorateur supplémentaire, tempsexec, qui calcule et affiche le temps d'exécution de la fonction décorée.

Le principe du test est simple:

  • on a une fonction calcul() qui est artificiellement longue grâce au sleep(1) (1 seconde) et qui est décorée par le decocache et par tempsexec.
  • on va calculer cette fonction 100 fois en ayant comme argument une valeur au hasard comprise entre 1 et 20

Pour un calcul donné, si l'argument 'a' n'est pas trouvé dans le cache, le calcul prend 1 seconde. Si par contre l'argument a est trouvé dans le cache, le résultat est renvoyé sans passer par la fonction, ce qui prend… moins de 1/1000 de seconde!

Au fur et à mesure des 100 calculs, il est de plus en plus probable de trouver l'argument dans le cache, et le temps diminue rapidement.

Les derniers calculs sont quasi instantanés.


Amusez-vous bien!

decorateurs_cache.txt · Dernière modification: 2011/04/04 20:56 par tyrtamos

Outils de la page