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^{[réf. nécessaire]}, 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.

Étymologie

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.

Exemple

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($\varphi ^{n}$) où $\varphi$ est le nombre d'or), car de nombreux appels récursifs sont faits sur de mêmes valeurs de $n$. 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.

Principe

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. Une fonction peut être mémoïsée seulement si elle est pure, c'est-à-dire si sa valeur de retour ne dépend que de la valeur de ses arguments, sans effet de bord. En ce cas, la transparence référentielle permet de remplacer l'appel de fonction directement par sa valeur. À la différence d'une fonction tabulée, où la table est statique, une fonction mémoïsée repose sur une table dynamique remplie à la volée.

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

Mémoïsation automatique

Dans les langages de programmation fonctionnels, où les fonctions sont des entités de première classe, il est possible de réaliser la mémoïsation de manière automatique et externe à la fonction (c'est-à-dire sans modifier la fonction initiale)^{[réf. nécessaire]} : on peut écrire une fonction d'ordre supérieur memo prenant en argument une fonction f et renvoyant une version mémoïsée de f. Un candidat pour une telle fonction memo peut s'écrire ainsi :

 fonction memo(f)
       h = une table de hachage
       renvoyer une fonction définie par fonction(x) 
                                               si h[x] n'est pas défini
                                                     h[x] := f(x)
                                               retourner h[x]

La fonction memo renvoie la version mémoïsée de f si f n'effectue pas d'appels récursifs. Malheureusement, si la fonction f contient des appels récursifs, la fonction memo ci-dessus ne renvoie pas la version mémoïsée de f car les appels récursifs se feraient toujours avec f et non pas avec memo(f). Pour obtenir l'équivalent de la fonction memo pour une fonction récursive, il faut fournir un combinateur de point fixe^{[réf. nécessaire]}, tel que :

 fonction memorec(f)
       h = une table de hachage
       alias = fonction  g définie par fonction(x) 
                                       si h[x] n'est pas défini
                                               h[x] := f(g(x))
                                      retourner h[x]
       renvoyer g                  

Exemple en OCaml

Dans le langage OCaml, 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émoïsation 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émoïsé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émoïsé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)) ;;

Mémoïsation dans les langages orientés objet

En programmation orientée objet, la mémoïsation est souvent obtenue en associant des variables statiques aux classes elles-mêmes (et non pas aux objets), voire en créant des classes statiques.

Épistémologie

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.

Voir aussi

• Transparence référentielle
• Programmation dynamique

Liens externes

• Jean-Christophe Filliâtre et Sylvain Conchon, Apprendre à programmer avec OCaml : Algorithmes et structures de données, Paris, Eyrolles, 2014 (ISBN 2-21213-678-1, présentation en ligne, lire en ligne), Programmation dynamique et mémoïsation.