Problème — Cache de résultats générique

On enferme un dictionnaire dans une fermeture (closure). À chaque appel, on regarde si l'argument est déjà une clé du cache ; sinon on calcule, on stocke, puis on renvoie.

def memoise(fonction):
    cache = {}
    def version_memo(n):
        if n not in cache:
            cache[n] = fonction(n)
        return cache[n]
    return version_memo

def calcul(n):
    print("calcul de", n)   # montre les appels reels
    return n * n

rapide = memoise(calcul)
print(rapide(4))   # affiche "calcul de 4" puis 16
print(rapide(4))   # 16 directement, sans recalcul
print(rapide(5))   # affiche "calcul de 5" puis 25

Grâce au cache, chaque valeur n'est calculée qu'une seule fois ; les appels suivants pour la même clé sont en $O(1)$ moyen.