Problème — Cache de résultats générique
Exercice de TD · niveau 3 (difficile) · NSI (terminale), chapitre 2 — Dictionnaires et tables de hachage
Énoncé
Problème — Cache de résultats générique.
On souhaite accélérer une fonction coûteuse calcul(n) en mémorisant ses résultats. Écrire une fonction d'ordre supérieur memoise qui prend une fonction et renvoie une version mémoïsée de celle-ci, à l'aide d'un dictionnaire interne.
Corrigé
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 25Grâce au cache, chaque valeur n'est calculée qu'une seule fois ; les appels suivants pour la même clé sont en moyen.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.