Réponse.

Historique de la question :

La mémorisation est une technique d'optimisation largement utilisée dans la programmation fonctionnelle, les calculs récursifs et la programmation dynamique, lorsque les mêmes fonctions sont appelées plusieurs fois avec les mêmes arguments. En Python, elle est devenue courante avec l'apparition du décorateur functools.lru_cache et des motifs de mise en cache des résultats des calculs.

Problème :

Sans mise en cache, les fonctions récursives comme le calcul des nombres de Fibonacci fonctionnent très lentement : pour chaque argument, les calculs sont répétés plusieurs fois, ce qui entraîne une croissance exponentielle du nombre d'appels.

Solution :

La mémorisation stocke les valeurs déjà calculées (par exemple, dans un dictionnaire) afin de les réutiliser si nécessaire :

Exemple d'implémentation manuelle :

memo = {}
def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        result = n
    else:
        result = fib(n-1) + fib(n-2)
    memo[n] = result
    return result

À partir de Python 3.2, vous pouvez simplement utiliser le décorateur :

from functools import lru_cache

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

Caractéristiques clés :

Permet d'accélérer les fonctions récursives ou coûteuses en calcul sans modifier leur logique
L'implémentation peut être manuelle (dans un dictionnaire) ou automatique (via lru_cache)
Il faut faire attention avec les arguments mutables, car lru_cache ne fonctionne qu'avec des arguments hachables (immutables)

Questions pièges.

Peut-on mémoriser une fonction avec des arguments mutables (par exemple, des listes) ?

Non, lru_cache requiert que tous les arguments soient hachables (immutables), sinon une TypeError se produira.

from functools import lru_cache

@lru_cache
# def f(a): return a[0]  # TypeError: unhashable type: 'list'

Les valeurs mémorisées sont-elles supprimées automatiquement ?

Oui, si un maxsize est défini — les valeurs qui dépassent cette limite sont supprimées (Least Recently Used). Un cache infini (maxsize=None) peut entraîner un débordement de mémoire.

Que se passe-t-il si une fonction mémorisée s'appelle elle-même avec de nouveaux arguments ?

La mémorisation fonctionnera quand même — pour chaque ensemble unique d'arguments, le résultat est calculé une seule fois et mis en cache.

Erreurs typiques et anti-modèles

Utiliser la mémorisation sans limite de cache et saturer la mémoire
Essayer de mémoriser des fonctions avec des arguments mutables
Oublier de nettoyer le cache lorsqu'il n'est plus nécessaire

Exemple de la vie réelle

Cas négatif

Écrire son propre cache sans limite de taille :

cache = {}
def foo(x):
    if x not in cache:
        cache[x] = long_heavy_computation(x)
    return cache[x]

avec le temps, le programme utilise des gigaoctets de mémoire.

Avantages :

Fonctionne rapidement pour des appels répétés

Inconvénients :

Croissance illimitée de la mémoire
Risque de Out of Memory

Cas positif

Utilisation de lru_cache avec maxsize :

from functools import lru_cache

@lru_cache(maxsize=1000)
def foo(x):
    return long_heavy_computation(x)