Le même calcul refait des millions de fois
La mémoïsation accélère une fonction récursive en gardant en mémoire les réponses déjà calculées. Elle évite de refaire le même calcul, et transforme parfois des millions d’appels en quelques dizaines.
Pour calculer fibonacci(30), la version simple fait 2 692 537 appels. Avec une mémoire, elle n’en fait que 59.
À la fin de cette leçon
Remarque
Je peux accélérer une récursion lente en retenant ses réponses.
Mots-clés
| Mot | Ce que ça veut dire | Exemple |
|---|---|---|
| Mémoïsation | garder une réponse calculée pour la réutiliser | |
| Mémo | le dictionnaire qui garde les réponses | {3: 2, 4: 3} |
| Calcul répété | un même appel refait plusieurs fois | |
| Algorithme glouton | un algorithme qui prend à chaque étape le meilleur choix du moment | |
| Programmation dynamique | résoudre un problème avec les réponses de problèmes plus petits |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
La récursion simple refait les mêmes calculs
Dans fibonacci(5), le calcul de fibonacci(3) est refait deux fois, et celui de fibonacci(2) trois fois. Chaque répétition refait tout son sous-arbre.
Plus n grandit, plus ces calculs répétés se multiplient. C’est ce qui rend la version simple si lente.
La mémoïsation range chaque réponse une fois
La mémoïsation ajoute un mémo, un dictionnaire qui garde chaque réponse trouvée. Au début de la fonction, on regarde dans le mémo.
Si la réponse y est, on la rend aussitôt. Sinon, on la calcule, on la range dans le mémo, puis on la rend. Chaque valeur de n n’est donc calculée qu’une seule fois.
Fibonacci avec un mémo
# Fibonacci qui retient ses réponses dans un dictionnaire.
appels = 0
memo = {}
def fibonacci(n):
global appels
appels = appels + 1
if n in memo:
return memo[n] # déjà calculé : on ne refait rien
if n < 2:
return n
memo[n] = fibonacci(n - 1) + fibonacci(n - 2)
return memo[n]
print(fibonacci(30), "en", appels, "appels")
# Sans mémoire, il en fallait 2 692 537. Essayez 50.
Appels de fibonacci(30), sans mémo
python3 -c "exec('compteur = 0\ndef fib(n):\n global compteur\n compteur = compteur + 1\n if n < 2:\n return n\n return fib(n - 1) + fib(n - 2)\nprint(fib(30), compteur)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Appels de fibonacci(30), avec mémo
python3 -c "exec('compteur = 0\nmemo = {}\ndef fib(n):\n global compteur\n compteur = compteur + 1\n if n in memo:\n return memo[n]\n if n < 2:\n return n\n memo[n] = fib(n - 1) + fib(n - 2)\n return memo[n]\nprint(fib(30), compteur)')"Affichée ici, non exécutée. Créez un compte gratuit pour appuyer sur Exécuter et la saisir dans le terminal de votre propre labo.
Rendre la monnaie avec le moins de pièces
Un distributeur doit rendre un montant avec le moins de pièces possible. Un algorithme glouton prend toujours la plus grande pièce qui entre. Avec les pièces d’euro, cela marche.
Avec des jetons de 1, 3 et 4 points pour rendre 6, le glouton prend 4 + 1 + 1, soit trois jetons. La meilleure réponse est 3 + 3, soit deux jetons.
Exemple travaillé : jetons de 1, 3 et 4
| Montant | Calcul | Moins de jetons |
|---|---|---|
| 0 | cas de base | 0 |
| 1 | 1 + réponse(0) | 1 |
| 2 | 1 + réponse(1) | 2 |
| 3 | 1 + le moins de réponse(2) et réponse(0) | 1 |
| 4 | 1 + le moins de réponse(3), réponse(1) et réponse(0) | 1 |
| 5 | 1 + le moins de réponse(4), réponse(2) et réponse(1) | 2 |
| 6 | 1 + le moins de réponse(5), réponse(3) et réponse(2) | 2 |
Les cellules que les étudiants remplissent restent vides dans cet aperçu.
Le moins de jetons, avec un mémo
# Le moins de jetons pour rendre un montant.
def jetons_minimum(montant, jetons, memo):
if montant == 0:
return 0
if montant in memo:
return memo[montant]
meilleur = -1
for jeton in jetons:
if jeton <= montant:
reste = jetons_minimum(montant - jeton, jetons, memo)
if reste != -1 and (meilleur == -1 or reste + 1 < meilleur):
meilleur = reste + 1
memo[montant] = meilleur
return meilleur
print(jetons_minimum(6, [1, 3, 4], {}))
# Essayez 8 avec les jetons [4, 6], puis 9.
Erreur fréquente
Attention
Beaucoup pensent que prendre la plus grande pièce donne toujours le moins de pièces. C’est vrai pour les euros, mais faux pour des jetons de 1, 3 et 4 : le glouton rend 6 avec trois jetons. Pour être sûr de la meilleure réponse, essayez chaque pièce et gardez le mémo.