Mémoïsation

En informatique, la mémoïsation (ou mémoïzation) est la mise en cache des valeurs de retour d'une fonction selon ses valeurs d'entrée. Le but de cette technique d'optimisation de code est de diminuer le temps d'exécution d'un programme informatique en mémorisant les valeurs retournées par une fonction. Bien que liée à la notion de cache, la mémoïsation désigne une technique bien distincte de celles mises en œuvre dans les algorithmes de gestion de la mémoire cache. Le terme anglais « memoization » a été introduit par Donald Michie en 1968. Il est dérivé du mot anglais « memo » qui signifie pense-bête, lui-même abréviation du mot d'origine latine « memorandum » (littéralement « qui doit être rappelé ») désignant un certain type de documents. Il y a donc derrière le terme mémoïsation l'idée de résultats de calculs dont il faut se souvenir. Bien que mémoïsation évoque le mot du vocabulaire général « mémorisation », le terme mémoïsation est un terme d'informatique. Considérons la fonction suivante calculant les termes de la suite de Fibonacci : fib(n) { si n vaut 1 ou 2 alors renvoyer 1 sinon renvoyer fib(n-1) + fib(n-2); } Telle quelle, cette fonction récursive est extrêmement inefficace (de complexité en temps O() où est le nombre d'or), car de nombreux appels récursifs sont faits sur de mêmes valeurs de . La version mémoïsée de fib stocke les valeurs déjà calculées dans une table associative table : memofib(n) { si table(n) n'est pas défini alors si n vaut 1 ou 2 alors table(n) = 1 sinon table(n) = memofib(n-1) + memofib(n-2); renvoyer table(n); } La fonction calcule la valeur table(n) si celle-ci n'a pas encore été définie, puis renvoie la valeur stockée dans table(n). La complexité de memofib est alors linéaire, en temps comme en espace. Note : il existe des moyens plus efficaces encore de calculer les termes de la suite de Fibonacci, mais il s'agit seulement ici d'illustrer la mémoïsation. Une fonction mémoïsée stocke les valeurs renvoyées par ses appels précédents dans une structure de données adaptée et, lorsqu'elle est appelée à nouveau avec les mêmes paramètres, renvoie la valeur stockée au lieu de la recalculer.