bonjour

Imaginons que vous ayez une fonction f qui soit longue à exécuter et appelée de nombreuse fois dans un programme. Il se peut que vous ayez à calculer f(n) pour un n tel que f(n) a déjà été calculé. Plutôt que de refaire le calcul qui est long, mieux vaut récupérer le résultat précédemment calculé, à condition bien sur de l'avoir mémorisé.

ça peut se faire avec un décorateur.

Voici le code du décorateur trouvé ici: http://www.python-course.eu/linear_combinations.php

def memoize(f):
    results = {}
    def helper(n):
        if n not in results:
            results[n] = f(n)
        return results[n]
    return helper

le décorateur s'utilise comme ceci:

@memoize
def f(n):
   ....
   return ...

La compréhension précise du fonctionnement du décorateur n'est pas si simple.

Tout d'abord, la fonction memoize() n'est appelée qu'une seule fois, juste après la définition de f():

f= memoize(f)

memoize remplace la fonction f par la fonction helper, tout en gardant l'identificateur f puisque c'est sous ce nom que la fonction est appelée dans le programme.

memoize crée un dictionnaire results qui contient les données n : f(n)  pour tous les n qui sont passés par f.

Ce dictionnaire qui est local à la fonction memoize reste en mémoire bien que la fonction memoize soit terminée car la fonction helper l'utilise. C'est un point que personnellement j'avais du mal à comprendre. Mais bon c'est comme ça.

Ensuite si on cherche à calculer f(n) et que n est une clé du dictionnaire, alors on sort directement la valeur correspondante f(n)

-
Edité par ast2 28 janvier 2015 à 17:33:22

C'est le principe du cache mémoire, tout simplement on vérifie si les données ne sont pas déjà présente en mémoire, deux cas de figures se présentent,

• Soit elle est présente, et dans ce cas, on affiche directement le résultat
• Soit elle n'est pas présente, et dans ce cas on enregistre le résultat, puis on l'affiche

C'est une technique très connue et qui a fait ses preuves.

Si tu veux avoir de plus amples informations et diverses utilisations, cherche du côté de technics caching python ou memoization python sur ton moteur de recherche préféré.

Puis surtout, c'est déjà dans la librairie standard: https://docs.python.org/3/library/functools.html#functools.lru_cache

Ah oui, pour les fonctions recursives, c'est génial !

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

et je constate aussi que le même décorateur memoize peut être utilisé pour décorer plusieurs fonctions distinctes d'un programme car les caches sont bien distincts.

def memoize(f):
    
    cache_dict = {}

    def f2(*arg):
        
        if arg not in cache_dict:
            cache_dict[arg] = f(*arg)
            
        return cache_dict[arg]

    return f2

@memoize    
def factorial(n):

    fact = 1
    
    for i in range(2, n+1):
        fact = fact * i

    return fact

@memoize  
def factorial_x2(n):

    fact = 2
    
    for i in range(2, n+1):
        fact = fact * i

    return fact

la fonction mémoize est appelée 2 fois, après les déclarations des fonctions factorial et factorial_x2, et chacun de ces 2 appels crée un dictionnaire cache_dict distinct.

>>> factorial(5)
120
>>> factorial(8)
40320
>>> factorial_x2(7)
10080
>>> factorial(7)
5040

Pour le calcul de factorial(7) on est pas allé cherché le contenu du cache correspondant à factorial_x2(7).

-
Edité par ast2 29 janvier 2015 à 15:34:47

Oui.

ast2 a écrit:

Ah oui, pour les fonctions recursives, c'est génial !

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

>>> [fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]

>>> fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)

D'un autre cotée, programmer fibonacci en

récursif est vraiment très mauvais.... Même si le cache limite les dégâts  

-
Edité par edouard22 31 janvier 2015 à 15:08:00