Mémoïsation

La mémoïsation est une technique très générale permettant l'utilisation d'une table pour stocker les valeurs calculées par une fonction afin d'éviter de les recalculer lors d'un prochain appel. La signature de la fonction est généralement préservée, permettant ainsi d'utiliser la technique pour améliorer la performance d'un programme existant en modifiant la fonction concernée pour qu'elle stocke et réutilise ses valeurs.

Il y a deux façons d'utiliser la mémoïsation. Pour des performances optimales, il est impératif de modifier la fonction manuellement afin de tenir compte de la structure et du domaine des valeurs calculées. Mais il est souvent possible d'obtenir une amélioration considérable avec une technique complètement générale, ne nécessitant aucune réflexion concernant les valeurs possibles. Un exemple de cette technique sera analysé dans cette section. La dernière de ces deux techniques est également un excellent illustration de la puissance du langage Common Lisp, en particulier de ses macros.

L'idée de la technique générale est de modifier la fonction afin de stocker automatiquement une correspondance entre les arguments fournis et la valeur calculée pour ces arguments. Nous allons utiliser la liste des propriétés du symbole nom de la fonction pour stocker cette correspondance. La table sera organisée sous forme de liste d'associations afin de simplifier le code. Une solution permettant une meilleure performance serait d'utiliser une table de hachage permettant un test equal des clés. La définition de la fonction d'origine est remplacée par une définition permettant un nombre arbitraire d'arguments. La liste des arguments fournis est utilisée pour chercher la table. Si la valeur y figure, elle sera simplement renvoyée. Sinon, la fonction d'origine est appelée pour calculer la valeur puis la correspondance entre les arguments et cette valeur est stockée dans la table. Le tout est encapsulé dans une macro similaire à defun. Voici la macro :

memoiser.lisp

Cette macro permet d'obtenir l'avantage de la mémoïsation par simple remplacement de defun par defun-memo pour la définition une fonction. Nous allons illustrer cette technique avec la version récursive du calcul d'un nombre de fibonnacci. La complexité de cette version est exponentielle alors qu'il est possible de calculer cette fonction en temps linéaire ; la seule raison d'être de la version exponentielle est qu'elle est calquée sur la définition des nombres fibonnacci.

Voici d'abord la définition normale de la fonction :

fib.lisp

On peut confirmer que cette version est lente :

* (time (fib 36))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 13.78 seconds of real time
 13.77 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 0 bytes consed.
24157817
*

Voici maintenant la définition utilisant la macro defun-memo :

fib-memo.lisp

Cette version est tellement rapide que time est incapable de mesurer le temps nécessaire pour le même calcul :

* (time (fib 36))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 0.0 seconds of real time
 0.0 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 0 bytes consed.
24157817
*

La version récursive devient rapidement trop lente pour être utilisable, même interactivement, à partir de $n = 40$. Par contre, la version mémoïsée reste pratique beaucoup plus longtemps. Voici un exemple avec $n = 1000$ :

* (time (fib 1000))
Compiling LAMBDA NIL:
Compiling Top-Level Form:

Evaluation took:
 0.16 seconds of real time
 0.16 seconds of user run time
 0.0 seconds of system run time
 0 page faults and
 90136 bytes consed.
703303677...encore 200 chiffres
*