Prolog et Fibonacci


précédentsommairesuivant

II. Utilisation de la mémoïsation.

II-A. Qu'est-ce que la mémoïsation ?

Observons le développement du calcul de Fibonacci(5), les calculs les plus à gauches sont effectués en premier.

Graphe de calcul de Fibonacci(5)
Sélectionnez

                                                                fib(5)
                                                                  |
                                 _________________________________+______________________________
                                 fib(4)                                                    fib(3)
                                   |                                                         |
                 __________________+__________________                              _________+___________
                 fib(3)                         fib(2)                              fib(2)     fib(1) = 1 
                   |                              |                                   |
          _________+___________      _____________+_____________          ____________+____________            
          fib(2)     fib(1) = 1      fib(1) = 1       fib(0) = 0          fib(1) = 1     fib(0) = 0
            |
____________+____________
fib(1) = 1     fib(0) = 0

On constate que de nombreux calculs sont répétés inutilement, et si on peut les mémoriser, un important gain de temps est effectué.
Cette technique s'appelle la mémoïsation, dès qu'un résultat est connu, il est mémorisé pour pouvoir être récupéré plus tard.
Observons ce que celà donne, mémo indique que le résultat est mémorisé.

Graphe de calcul de Fibonacci(5)
Sélectionnez

                                                                fib(5)
                                                                  |
                                 _________________________________+_________________________________
                                 fib(4) mémo                                               fib(3)= 2
                                   |                                                         
                 __________________+___________________               
                 fib(3) mémo                  fib(2)= 1              
                   |                                                          
          _________+_______________     
          fib(2) mémo    fib(1) = 1        
            |
____________+____________
fib(1) = 1     fib(0) = 0

Dans le calcul, on devra s'assurer d'abord que le résultat n'est pas déjà connu, et s'il ne l'est pas, le calculer et le mémoriser. On obtient cet algo :

Algorithme
Sélectionnez
fonction fibonacci_memo(N : entier) : entier
variable retour : entier
variable existe : booleen
début
  existe <- existence de Fibonacci(N) dans la base de données
  si existe = vrai alors
    retour <- Fibonacci(N)
  sinon
    retour <- fibonacci_memo(N-1) + fibonacci_memo(N-2)
    // Maintenant Fibonacci(N) est connu, il faut l'enregistrer dans la base de données
    memoriser le couple (N, Fibonacci(N))
  fin si
  retourner retour
fin

II-B. Une première méthode de mémoïsation.

Prolog possède un mécanisme très simple de mémorisation, les prédicats dynamiques qui permettent d'ajouter "à runtime" des faits dans la base de données Prolog. On peut le faire par l'intermédiaire de 3 prédicats : assert/1, asserta/1 et assertz/1 (mais qui est équivalent à assert/1). Un petit exemple permet de mieux comprendre :

Prolog
Sélectionnez
% déclaration des prédicats dynamiques (nom/arité)
:- dynamic pred1/2, pred2/2.

test :-
    % insertion normale dans la base de données
	assert(pred1(0,0)),
	assert(pred1(2,4)),
	assert(pred1(3,5)),
	
	% insertion en tête de base de données
	asserta(pred2(0,0)),
	asserta(pred2(2,4)),
	asserta(pred2(3,5)).

On obtient, entre autres, le contenu de la base de données Prolog par le prédicat listing/0. Après avoir enlevé certains renseignements ici inutiles, on obtient comme résultat :

Console Prolog
Sélectionnez
5 ?- listing.

:- dynamic pred1/2.

pred1(0, 0).
pred1(2, 4).
pred1(3, 5).

:- dynamic pred2/2.

pred2(3, 5).
pred2(2, 4).
pred2(0, 0).

Yes

On constate bien que les couples pred2 sont mémorisés dans l'ordre inverse de l'insertion dans la base de données. Cependant, il n'y a aucune différence au point de vue temps d'accès entre les deux prédicats

Les tuples fibo(N, FN) seront ajoutés à la base de données par l'intermédiaire de assert/1. On obtient donc le code Prolog suivant :

Prolog
Sélectionnez
% fibo/2 permet de mémoriser les résultats intermédiaires
% déclaration du prédicat dynamique (nom/arité)
:- dynamic (fibo/2).

% Lancement du calcul
fib_memo(N, F) :-
    % les deux premiers resultats sont memorises
	assert(fibo(0,0)),
	assert(fibo(1,1)),
	fib_memo_calcul(N, F).

% On vérifie que le calcul n'a pas déjà été effectué
fib_memo_calcul(N, F) :-
	fibo(N, F), !.

% En cas d'échec, on le calcule
fib_memo_calcul(N, F) :-
	N1 is N - 1,
	% Calcul de Fibonacci(N1)
	fib_memo_calcul(N1, F1),
	N2 is N - 2,
	% Le calcul de Fibonacci(N2) a déjà été fait, on peut le récupérer
	fibo(N2,F2),
	F is F1 + F2,
	% et on le mémorise dans la base de données
	assert(fibo(N, F)).

Les résultats sont honorables, même s'ils n'atteignent pas la performance du calcul itératif.

Console Prolog
Sélectionnez
3 ?- test(100000).
% 699,998 inferences, 28.03 CPU in 29.38 seconds (95% CPU, 24972 Lips)

II-C. Une seconde méthode de mémoïsation.

La méthode précédente possède à mon avis le défaut "de ne pas laisser l'environnement aussi propre que lorsque je l'avais trouvé".
On peut mémoriser les résultats intermédiaires en utilisant une bibliothèque toute faite, les listes d'assocations. Ces listes d'associations utilisent les techniques d'arbres AVL pour des insertions et des recherches en O(Log (N)). Les détails sur cette bibliothèque peuvent être trouvés iciLes listes d'associations en SWI-Prolog..
Le code obtenu ressemble comme un frère au précédent.

Prolog
Sélectionnez
% fibonacci avec des listes d'associations
fib_assoc(N, X) :-
    % creation de la liste d'association vide
	empty_assoc(As0),
	% on insere les deux premieres valeurs
	put_assoc(0, As0, 0, As1),
	put_assoc(1, As1, 1, As2),
	% et on lance le calcul
	fib_assoc_calcul(N, X, As2, _).

fib_assoc_calcul(N, X, As1, As1 ):-
	get_assoc(N, As1, X), !.

fib_assoc_calcul(N, X, As0, As3) :-
	N1 is N-1,
	N2 is N-2,
	% Calcul de Fibonacci(N1)
	fib_assoc(N1, FN1, As0, As1),
	% Le calcul de Fibonacci(N2) a déjà été fait, on peut le récupérer
	get_assoc(N2, As1, FN2),
	X is FN1 + FN2,
	% et on le mémorise
	put_assoc(N, As1, X, As3).

Les résultats sont nettement moins bons :

Console Prolog
Sélectionnez
6 ?- time(fib_assoc(50000, N)).
% 5,991,280 inferences, 5.47 CPU in 5.61 seconds (97% CPU, 1095548 Lips)

Le calcul de Fibonacci(100 000) explose la pile d'exécution !


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+