Sam & Max » function http://sametmax.com Du code, du cul Sat, 07 Nov 2015 10:56:13 +0000 en-US hourly 1 http://wordpress.org/?v=4.1 Mémoization d’une fonction Python 11 http://sametmax.com/memoization-dune-fonction-python/ http://sametmax.com/memoization-dune-fonction-python/#comments Fri, 20 Jul 2012 20:37:27 +0000 http://sametmax.com/?p=1223 mémoization est une forme de mise en cache, elle consiste à cacher le résultat d'une fonction afin que les appels successifs avec des paramètres identiques utilisent le cache plutôt que de calculer à nouveau les données.]]> La mémoization est une forme de mise en cache, elle consiste à cacher le résultat d’une fonction afin que les appels successifs avec des paramètres identiques utilisent le cache plutôt que de calculer à nouveau les données.

En gros:

>>> fonction_super_lente(True, '127.0.0.1') # calcule
>>> fonction_super_lente(True, '127.0.0.1') # ne calcule pas, retourne le cache
>>> fonction_super_lente(True, '192.168.0.1') # calcule car les paramètres sont différents

En Python on peut le faire de plusieurs manières, malgré ce que prétend la philosophie du langage.

La version avec dico externe

resultats = {}
def fonction_super_lente(le_faire, sur_quoi):
 
    if not (le_faire, sur_quoi) in resultats:
        resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici
 
    return resultats[(le_faire, sur_quoi)]

Cela marche parceque resultats est gardé dans une closure et donc accessible dans la fonction. Comme il est défini avant, et que les dictionnaires sont mutables, on a toujours la même référence au même dico à chaque appel. On a juste a vérifier qu’un résultat pour ces param existent (les tuples peuvent être des clés de dictionnaires), et si non, on remplit le cache.

Avantages:

  • c’est facile à comprendre;
  • on peut manipuler le cache depuis l’extérieur.

Inconvénient:

  • le namespace du module est pollué;
  • on risque d’importer le cache par erreur.

La version avec paramètre additionel

def fonction_super_lente(le_faire, sur_quoi, _resultats={}):
 
    if not (le_faire, sur_quoi) in resultats:
        _resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici
 
    return _resultats[(le_faire, sur_quoi)]

Même chose que précédement, mais la différence est que le cache est stocké dans un paramètre. Cela marche car les paramètres sont initialisés à la déclaration en Python, et une seule fois.

Notez le underscore devant le nom de paramètre qui est une convention pour désigner un paramètre qui ne fait pas partie de l’API publique.

Avantages:

  • c’est encore pas trop dur à comprendre;
  • le namespace est clean.

Inconvénient:

  • la signature de la fonction possède un argument artificiel.

La version avec attribut

def fonction_super_lente(le_faire, sur_quoi):
 
    resultats = getattr(function_super_lente, '_resultats', {})
    if not (le_faire, sur_quoi) in resultats:
        resultats[(le_faire, sur_quoi)] = # balancer le calcul lent ici
        function_super_lente._resultats = resultats
 
    return resultats[(le_faire, sur_quoi)]

Cela marche car les fonctions en Python sont des objets. On peut leur rajouter des attributs à la volées comme pour n’importe quel objet :-)

Notez l’usage du troisième paramètre de getattr() qui nous permet d’avoir une valeur par défaut même si l’attribut n’existe pas encore.

Avantages:

  • pas de polution du namespace ni de la signature.

Inconvénient:

  • votre collègue va surement vous demander: WTF ?

La version avec décorateur

Il existe pas mal de versions de décorateurs de mémoization disponibles sur le Net. Ca s’utilise généralement comme ça :

from malib import memoized
 
@memoized
def fonction_super_lente(le_faire, sur_quoi):
 
    return # le truc normalement

Avantages:

  • y a pas plus propre;
  • y a pas plus facile.

Inconvénient:

  • une dépendance de plus;
  • chaque implémentation possède une caractéristique (souvent une limite): il faut donc comprendre des codes parfois complexes pour les utiliser en toute tranquilité d’esprit.

Petit rappel

Cette technique, de par sa nature, implique de tout stocker en mémoire vive. Donc attention à votre RAM, et vérifiez bien que ça vaut le coup d’échanger la charge CPU contre celle de vos barettes. Ensuite, le bénéfice est d’autant plus grand que le code tourne longtemps. Si c’est un script lancé de nombreuses fois, avec quelques appels à la fonction, le gain est faible: entre chaque initialisation de la VM Python, le cache disparait. Dans ce cas il vaut mieux se tourner vers une solution telle que Redis.

Le cas typique d’usage pertinent est celui d’un daemon faisant des appels à une API WEB: en cachant les résultats, vous économisez une requête HTTP.

]]>
http://sametmax.com/memoization-dune-fonction-python/feed/ 11