Mémoïsation

Lorsque nous implémentons un algorithme récursif, nous pouvons constater dans un grand nombre de cas qu'une même opération est souvent effectuée avec les mêmes valeurs en paramètre. A chaque fois ce calcul a un coût en temps processeur et en mémoire. Ce n'est pas conséquent lorsque nous traitons des données peu importantes, mais ce coût se révèle souvent être de type exponentiel, et nous nous retrouvons avec des programmes dont les performances ne sont plus acceptables (ou des programmes qui ne peuvent carrément plus s'exécuter) dès que la quantité de données à traiter devient plus importante.

Nous pouvons éviter de calculer inutilement une opération dont le calcul a déjà été effectué, en mémorisant le résultat lors du premier appel. A chaque appel, nous testons si le résultat est présent, mais ce test est généralement nettement mois coûteux que l'opération à calculer. Nous devrons donc modifier l'appel récursif pour invoquer une méthode "memo" comme le montre l'exemple ci-dessous.

function fibonacci(var n : integer) : integer;
{Pre: 	n>=0}
begin
	if n < 2 
	then
		fibonacci := n;
	else
		fibonacci := fibonacci(n-1) +  fibonacci(n-2);		
end;

Dans cette implémentation, nous pouvons remarquer deux appels récursifs¹, ce qui donne un ordre de grandeur de temps T(n) ≤ (2ⁿ)

program fibonacci-memo;
 
cons undef = -1; {valeur qui n'est jamais employee et qui signifie une valeur non definie}
cons maxIndice = 20;
 
var memoArray : packed array[0..maxIndice] of integer;
 
function fibonacci(var n : integer) : integer;
{Pre: 	0 <= n <= maxIndice}
begin
	if n < 2 
	then
		fibonacci := n;
	else
		fibonacci := fibonacciMemo(n-1) +  fibonacciMemo(n-2);		
end;
 
function fibonacciMemo(var n : integer) : integer;
{Pre: 	0 <= n <= maxIndice}
begin
	if memoArray[n] = undef
	then
		memoArray[n] := fibonacci(n);{il est necessaire de calculer la valeur}
	fibonacciMemo := memoArray[n];{la valeur est deja calculee}	
end;
 
{main program}
begin		
	var i : integer;
	var j : integer;
	j:=20;
	for i:=0 to maxIndice do
		memoArray[i]:=undef;
	writeln('Fibonacci(', j, ') = ', fibonacci(j));
end.

Dans cette deuxième implémentation, nous pouvons remarquer que le point de départ est toujours notre fonction fibonacci(n), mais que chaque appel au calcul(anciennement un appel récursif) est remplacé par un appel à la nouvelle fonction de mémoïsation. La complexité en temps de ce deuxième exemple est de (n) * (T_{recherche et/ou écriture; dans le tableau}), donc de (n) ou au maximum identique à l'exemple précédent.

La fonction de mémoïsation vérifie si le calcul a déjà été effectué(si c'est le cas une valeur est présente à l'indice n dans le tableau) et retourne cette valeur si c'est le cas, ou effectue le calcul et stocke la valeur dans le tableau avant de la renvoyer comme résultat.

Contents Haut

Récursivité ascendante

Comme pour la mémoïsation, la récursivité ascendante nous permet de construire une table des résultats intermédiaires, mais ici de manière à traiter le problème le plus simple en premier. Si nous calculons les résultats intermédiaires lors de la "remontée"² dans l'arbre, la probabilité que la valeur se trouve déjà dans le tableau des résultats est beaucoup plus importante.

La complexité de ce type d'algorithme est généralement de (n)

La structure de notre programme est modifiée, car nous utiliserons une boucle au lieu d'appels récursifs. Nous économisons donc la pile induite par notre alorithme récursif (gain mémoire), et nous nous assurons un remplissage optimal des résultats.