Mémoization

En informatique, la mémoization est une technique d'optimisation de code consistant à réduire le temps d'exécution d'une fonction en mémorisant ses résultats d'une fois sur l'autre. Bien que liée à la notion de cache, la mémoization désigne une technique bien distincte de celles mises en œuvre dans les algorithmes de gestion de la mémoire cache.

Présentation

Le terme « mémoization » a été introduit par Donald Michie en 1968^[1] et est dérivé du mot latin « memorandum » signifiant « qui doit être rappelé ».
Il y a donc derrière le terme mémoization l'idée de résultats de calculs dont il faut se souvenir. Bien que mémoization évoque « mémorisation », le terme mémoization a une signification particulière en informatique.

Une fonction mémoizée stocke les résultats de ses appels précédents dans une table et, lorsqu'elle est appelée à nouveau avec les mêmes paramètres, renvoie la valeur stockée au lieu de la recalculer. Une fonction peut être mémoizée seulement si elle est référentiellement transparente, c'est-à-dire si sa valeur de retour ne dépend que de la valeur de ses arguments. À la différence d'une fonction tabulée, où la table est statique, une fonction mémoizée repose sur une table dynamique remplie à la volée.

La mémoization est une façon de diminuer le temps de calcul d'une fonction, au prix d'une occupation mémoire plus importante. La mémoization modifie donc la complexité d'une fonction, en temps comme en espace.

À titre d'illustration, considérons la fonction suivante calculant les termes de la suite de Fibonacci :

fib(n) {
   si n vaut 1 ou 2 alors renvoyer 1;
   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 n. La version mémoizée de fib stocke les valeurs déjà calculées dans une table associative table :

fib(n) {
   si table(n) est défini alors renvoyer table(n);
   table(n) = si n vaut 1 ou 2 alors 1 sinon fib(n-1) + fib(n-2);
   renvoyer table(n);
}

La complexité de fib devient 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émoization.)

La mémoïsation peut aussi être parfois considérée comme un cas particulier de la programmation dynamique dans sa façon d'exprimer la solution d'un problème en fonction de la résolution de sous-problèmes, indépendamment de la façon dont la résolution du sous-problème est obtenue. Par exemple, les techniques de mémoïsation utilisées en analyse syntaxique, dont les premiers exemples sont l'algorithme CYK de Cocke-Youger-Kasami et l'algorithme de Earley, peuvent être décrites comme une application de la mémoïsation à de simple algorithmes d'exploration de l'espace des analyses possibles. Si on associe un coût aux règles des grammaires utilisées, et que l'on cherche l'analyse de moindre coût, les mêmes algorithmes, mémorisant également le coût (maximum ou minimum) associé à une sous-analyse, sont en fait des calculs de recherche d'une analyse optimale par programmation dynamique.

Mémoization automatique

Dans l'exemple ci-dessus, la mémoization a été réalisée de manière explicite et interne à la fonction. Dans les langages de programmation fonctionnels, où les fonctions sont des valeurs de première classe, il est possible de réaliser cette opération de manière automatique et externe à la fonction. Il est en effet possible d'écrire une fonction d'ordre supérieur prenant en argument une fonction f et renvoyant une version mémoizée de cette fonction. Dans le langage Objective Caml, une telle fonction memo peut s'écrire ainsi :

 let memo f =
   let h = Hashtbl.create 97 in
   fun x ->
     try Hashtbl.find h x
     with Not_found ->
       let y = f x in
       Hashtbl.add h x y;
       y

La fonction memo a le type ('a -> 'b) -> 'a -> 'b, c'est-à-dire qu'elle prend en argument une fonction quelconque de type 'a -> 'b et renvoie une fonction du même type. La mémoization est ici réalisée grâce à une table de hachage polymorphe. Si on dispose d'une fonction particulière ma_fonction on obtient sa version mémoizée par

 let ma_fonction_efficace = memo ma_fonction

Il est important de réaliser l'application partielle de la fonction memo, afin qu'une seule table de hachage soit créée, et partagée ensuite entre tous les appels à ma_fonction_efficace.

Dans le cas de la fonction fib, cependant, on ne peut pas se contenter d'appliquer la fonction memo ci-dessus à la version naïve de la fonction fib, car les appels récursifs se feraient alors sur la version naïve et non sur la version mémoizée. Pour obtenir l'équivalent de la fonction memo pour une fonction récursive, il faut fournir un combinateur de point fixe, tel que :

 let memo_rec yf =
   let h = Hashtbl.create 97 in
   let rec f x = 
     try Hashtbl.find h x
     with Not_found ->
       let y = yf f x in
       Hashtbl.add h x y;
       y
   in
   f

Il est alors possible d'obtenir une version efficace de la fonction fib avec la définition suivante :

 let fib = memo_rec (fun fib n -> if n < 2 then n else fib (n-1) + fib (n-2))

Références

Voir aussi

• Transparence référentielle
• Programmation dynamique

• Portail de l’informatique