I. Les algorithmes classiques▲
I-A. Un petit rappel historique▲
Ce rappel est extrait d'un article de WilkipediaFibanacci sur Wilkipedia
La suite de Fibonacci est l'une des suites mathématiques les plus connues. Elle doit son nom au mathématicien italien Leonardo Pisano, plus connu sous le pseudonyme de Fibonacci (1175 - 1250). Dans un problème récréatif posé dans un de ses ouvrages, le Liber Abaci, Fibonacci décrit la croissance d'une population de lapins :
« Possédant initialement un couple de lapins, combien de couples obtient-on en douze mois si chaque couple engendre tous les mois un nouveau couple à compter du second mois de son existence ? »
Ce problème est à l'origine de la suite dont le -ième terme correspond au nombre de paires de lapins au -ième mois. Dans cette population (idéale), on suppose que :
- le premier mois, il y a juste une paire de lapereaux ;
- les lapereaux ne sont pubères qu'à partir du deuxième mois ;
- chaque mois, toute paire susceptible de procréer engendre effectivement une nouvelle paire de lapereaux ;
- les lapins ne meurent jamais (donc la suite de Fibonacci est strictement croissante).
I-B. La définition mathématique de la suite▲
fibonacci(n) = n si n < 2
fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)I-C. Les algorithmes de base▲
Dans cette section, nous abordons les deux algorithmes de base, le premier récursif particulièrement inefficace, et le second itératif, très performant.
I-C-1. L'algorithme naïf▲
Le premier algorithme de calcul dérive directement de la définition mathématique :
fonction Fibonacci_naive(n : entier) : entier
variable retour : entier
début
si n < 2 alors
retour <- n
sinon
retour <- Fibonacci_naive(n-1) + Fibonacci_naive(n-2)
fin si
retourner retour
finI-C-2. L'algorithme itératif▲
Bien évidemment, une version itérative nettement plus efficace a été élaborée. Elle se base sur la construction du nombre à partir de 0 et 1, un nombre de la suite étant la somme des deux nombres le précédant.
fonction Fibonacci_iter(n : entier) : entier
variable compteur, val1, val2, val3, retour : entier
debut
si n < 2 alors
retour <- n
sinon
val1 <- 0
val2 <- 1
pour compteur de 2 à n par pas de 1 faire
val3 <- val1 + val2
val1 <- val2
val2 <- val3
fin pour
retour <- val2
fin si
retourner retour
finI-D. Implémentation Prolog des algorithmes de base▲
I-D-1. L'algorithme naïf▲
Les fonctions n'existant pas en Prolog, on utilisera un prédicat naive_fib/2 le premier étant l'indice du second dans la suite des nombres de Fibonacci.
naive_fib(X, X) :- X < 2, !.
naive_fib(X, Y) :-
Idx1 is X - 1,
Idx2 is X - 2,
naive_fib(Idx1, A),
naive_fib(Idx2, B),
Y is A + B.Cette version n'est pas très performante, on obtient ce résultat pour le calcul de Fibonacci(40) :
14 ?- time(naive_fib(40,N)).
% 1,159,060,982 inferences, 340.16 CPU in 362.57 seconds (94% CPU, 3407437 Lips)
N = 102334155 ;soit plus de 1 100 000 000 inférences et plus de 5 minutes 40 secondes pour calculer Fibonacci(40) !
I-D-2. L'algorithme itératif▲
La boucle pour de l'algorithme est remplacée par un appel récursif terminal.
Le prédicat possède quatre arguments. L'indice de boucle est décrémenté à partir de N pour pouvoir arrêter la boucle à 1 et éviter ainsi un cinquième argument, le maximum de l'indice de boucle.
fib_iter(N, F) :-
% si N est plus petit que 2, pas de calcul
N < 2 -> F = N ;
% Sinon il est lancé
fib_iter_cal(0, 1, N, F).
% arg1 : l'avant-dernier calcul
% arg2 : le dernier calcul
% arg3 : Indice de boucle de calcul en cours (arrêt à 1)
% arg4 : résultat final
fib_iter_cal(_F, F, 1, F) :- !.
fib_iter_cal(TT1, TT2, N, F) :-
TT3 is TT1 + TT2,
N1 is N - 1,
fib_iter_cal(TT2, TT3, N1, F).Ce code est nettement plus performant :
time(fib_iter(100000, N)).
% 299,999 inferences, 0.67 CPU in 1.15 seconds (58% CPU, 446510 Lips)Je vous épargne le résultat, il s'écrit avec 20 900 chiffres !
I-E. Conclusion▲
Bien évidemment, l'algorithme itératif est nettement plus performant que l'algorithme naïf. Aucune autre méthode ne peut faire mieux en Prolog. Cependant, la puissance d'expression du langage permet d'utiliser d'autres concepts pour le calcul. Ces concepts sont exposés dans les chapitres suivants.
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 à gauche sont effectués en premier.
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) = 0On 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 cela donne, mémo indique que le résultat est mémorisé.
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) = 0Dans 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 :
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
mémoriser le couple (N, Fibonacci(N))
fin si
retourner retour
finII-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 trois prédicats : assert/1, asserta/1 et assertz/1 (mais qui est équivalent à assert/1). Un petit exemple permet de mieux comprendre :
% 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 :
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).
YesOn 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 :
% 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.
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.
% 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 :
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 !
III. Utilisation des « Open Lists »▲
III-A. Que sont les Open Lists ?▲
Dans une liste « normale », le dernier élément est la liste vide : exemple [1,2,3|[]].
Les Open Lists sont des listes particulières où le dernier élément n'est pas défini : exemple [1,2,3|_].
Considérons ce petit programme :
test :-
L = [1,2,3|_],
( member(1, L) -> format('1 présent dans ~w~n', [L]);format('1 absent dans ~w~n', [L])),
( member(3, L) -> format('3 présent dans ~w~n', [L]);format('3 absent dans ~w~n', [L])),
( member(5, L) -> format('5 présent dans ~w~n', [L]);format('5 absent dans ~w~n', [L])).La sortie obtenue est :
10 ?- test.
1 présent dans [1, 2, 3|_G272]
3 présent dans [1, 2, 3|_G272]
5 présent dans [1, 2, 3, 5|_G281]On constate que lorsque l'élément est présent, la liste n'est pas modifiée, lorsqu'il est absent, il est ajouté en fin de liste. Remarquons au passage que contrairement à ce qui se passe habituellement en Prolog, bien que la liste soit modifiée, elle est toujours unifiée avec la même variable.
III-B. Simulation d'un stream par une Open List▲
Il est possible d'attacher une procédure à une Open List, on peut ainsi simuler un stream.
Le code suivant est inspiré de cette pageLes stream en Prolog. when(@Condition, :Goal) est un prédicat qui permet de geler l'exécution de :Goal tant que la condition @Condition n'est pas à true. En Prolog, le « @ » en début de nom de variable signifie que l'argument n'est pas encore instancié, le « : » signifie que l'argument est un métaargument.
Ce code permet de calculer la suite des puissances de 2, on remarquera que la création du stream est faite avant la création de l'Open List.
% arg1 : la procédure à appliquer au stream (ici un prédicat à deux arguments)
% arg2 : l'élément d'initialisation du calcul
% arg3 : le stream
make_stream(Pred, Head, OpenList) :-
when(nonvar(OpenList),
(
% on construit l' Open List
OpenList = [Head|Rest],
% on applique le prédicat de calcul
call(Pred, Head, Next),
% on construit récursivement l' Open List
make_stream(Pred, Next, Rest)
)).
% le prédicat de calcul des puissances
double(X, Y) :-
Y is X * 2.
% le stream permettra de calculer la liste des puissances de 2
tests :-
% création du stream
make_stream(double, 1, OpenList),
OpenList = [_, _, _, _|X],
format('Les quatre premières puissances de 2 sont ~w~n', [OpenList]),
X = [_, _, _, _|_Y],
format('Les huit premières puissances de 2 sont ~w~n', [OpenList]).On obtient :
12 ?- test.
Les quatre premières puissances de 2 sont [1, 2, 4, 8|_G312]
Les huit premières puissances de 2 sont [1, 2, 4, 8, 16, 32, 64, 128|_G466]De plus amples explications sur le prédicat when/2 peuvent être trouvées iciLe prédicat when/2.
De plus amples explications sur le prédicat nonvar/1 peuvent être trouvées iciLe prédicat nonvar/1.
III-C. Le calcul des nombres de Fibonacci avec les Open Lists et les streams▲
Par les streams, on obtient une liste des nombres de Fibonacci.
La construction de l'Open List se fait de manière itérative.
Le calcul des nombres est un calcul itératif semblable au calcul itératif du I-C-2.
% Construction de l' Open List
make_OpenList(0, OpenList, OpenList):- !.
make_OpenList(N, L1,L2) :-
N1 is N-1,
make_OpenList(N1, [_|L1], L2).
% creation du stream de calcul
% ici le prédicat de calcul a besoin de 2 arguments en entree !
make_stream_fib(Pred, First, Second, OpenList) :-
when(nonvar(OpenList),
(
OpenList = [Second |Rest],
call(Pred, First, Second, Next),
make_stream_fib(Pred, Second, Next, Rest)
)).
fib_OpenList(N) :-
make_stream_fib(fib_OpenList, 0, 1, OpenList),
make_OpenList(N, _, OpenList).
% calcul effectif du nombre de Fibonacci.
fib_OpenList(X,Y,Z) :-
Z is X + Y.Les performances sont correctes :
11 ?- time(fib_OpenList(30000)).
% 360,029 inferences, 0.73 CPU in 0.89 seconds (83% CPU, 490252 Lips)Remarquons que la génération de l'Open List par make_OpenList prend 60 000 inférences.
IV. Utilisation des DCG▲
Les DCG « Definite Clause Grammar » permettent d'écrire de façon aisée en Prolog des règles de grammaire.
IV-A. Exemple de DCG▲
Regardons ces DCG pour une grammaire très simple d'expressions numériques :
expression --> terme, suite_terme.
suite_terme --> [].
suite_terme --> [+], expression.
terme --> facteur, suite_facteur.
suite_facteur --> [].
suite_facteur --> [*], terme.
facteur --> [I], {integer(I)}.
facteur --> ['('], expression, [')'].La première règle signifie qu'une expression est un terme suivi d'un élément appelé suite_terme.
Le deuxième et la troisième règle définissent suite_terme. suite_terme peut n'être rien (deuxième règle) ou l'enchaînement du signe + et d'une expression.
La règle facteur --> [I], {integer(I)}. indique qu'un facteur peut être un nombre et qu'un nombre est reconnu comme vérifiant le prédicat integer/1. Le code entre accolades est interprété comme du Prolog pur.
Après compilation du code comme un code Prolog, on peut tester les règles :
13 ?- expression([1,+,3,*,'(',2,+,4,')'],[]).
Yes
14 ?- expression([1,-,3,*,'(',2,+,4,')'],[]).
NoLa deuxième expression n'est pas reconnue puisque '-' n'est pas défini par notre grammaire.
On peut obtenir la conversion en Prolog des règles DCG par le prédicat listing/0.
expression(A, C) :-
terme(A, B),
suite_terme(B, C).
terme(A, C) :-
facteur(A, B),
suite_facteur(B, C).
suite_terme(A, A).
suite_terme([+|À], B) :-
expression(A, B).
facteur([A|C], B) :-
integer(A),
B=C.
facteur(['('|A], C) :-
expression(A, B),
B=[')'|C].
suite_facteur(A, A).
suite_facteur([*|À], B) :-
terme(A, B).On constate que Prolog ajoute automatiquement deux arguments aux prédicats et qu'on retrouve la structure d'Open Lists (prédicas suite_terme, facteur …).
Des renseignements complémentaires sur les DCG peuvent être trouvés ici. Des renseignements sur les DCG en SWI-Prolog peuvent être trouvés ici.
IV-B. La version naïve en DCG▲
La version de l'algorithme naïf peut s'écrire sous cette forme:
fib_dcg_naif(0,0) --> [].
fib_dcg_naif(1,1) --> [].
fib_dcg_naif(X, FX) -->
{X > 1,
X1 is X-1,
X2 is X - 2},
fib_dcg_naif(X1, FX1),
fib_dcg_naif(X2, FX2),
{FX is FX1 + FX2}.Les performances sont à la hauteur de la méthode du calcul des nombres de Fibonacci !
24 ?- time(fib_dcg_naif(25, X,_,_)).
% 971,137 inferences, 10.00 CPU in 10.05 seconds (100% CPU, 97114 Lips)
X = 75025 ;
NoLe simple calcul fib_dcg_naif(30, X). fait exploser la pile d'exécution.
IV-C. Une méthode itérative de calcul des nombres de Fibonacci avec les DCG.▲
Les méthodes suivantes sont inspirées de cet article
La première méthode est basée sur le calcul itératif, les résultats, sous la forme de tuples fib(Nombre, Valeur), sont mémorisés dans une liste. La liste est initialisée avec les deux premières valeurs, Fibonacci(0) et Fibonacci(1).
% Le lancement du calcul
fib_dcg_ver1(X) :-
fib_dcg_ver1_calc(X, [fib(1,1), fib(0,0)], _, _).
% ici la valeur recherchée est trouvée
fib_dcg_ver1_calc(X, [X|_]) --> [].
% Sinon on calcule la valeur suivante
% En s'assurant qu'on n'a pas dépassé la valeur recherchée
fib_dcg_ver1_calc(X, [A, B]) -->
{gt(X, A)},
fib_suivant_ver1(A, B, Next_Fib),
fib_dcg_ver1_calc(X, [Next_Fib, A]).
% calcul de la valeur suivante
fib_suivant_ver1(fib(Idx1, Num1), fib(_Idx2, Num2), fib(Idx3, Num3)) -->
[],
{Idx3 is Idx1 + 1,
Num3 is Num1 + Num2}.
gt(fib(A, _FA), fib(X, _FX)) :-
À >= X.Les résultats sont intéressants :
8 ?- time(fib_dcg_ver1(100000, _)).
% 799,994 inferences, 0.80 CPU in 1.16 seconds (69% CPU, 1003914 Lips)IV-C-1. Amélioration de la méthode▲
On peut améliorer la rapidité du code en introduisant un cut bien placé : lorsque la valeur a été trouvée, il est inutile de continuer.
% Le lancement du calcul
fib_dcg_ver2(X) :-
fib_dcg_ver2_calc(X, [fib(1,1), fib(0,0)], _,_).
% version avec un cut
fib_dcg_ver2_calc(X, [X|_]) --> [], {!}.
fib_dcg_ver2(X, [A, B]) -->
fib_suivant_ver2(X, A, B, Fib1),
fib_dcg_ver2_calc(X, [Fib1, A]).
fib_suivant_ver2(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
[],
{ Idx3 is Idx1 + 1,
Num3 is Num1 + Num2 }.Le gain est important en nombre d'inférences :
10 ?- time(fib_dcg_ver2(100000, _)).
% 499,999 inferences, 0.61 CPU in 1.08 seconds (57% CPU, 820511 Lips)IV-D. Le calcul des nombres de Fibonacci avec mémorisation des résultats▲
Les méthodes précédentes n'utilisent pas toute la puissance des DCG. On peut mémoriser les résultats intermédiaires dans une liste. Attention, il n'est pas question de mémoïsation, les résultats ne sont pas réutilisés, la mémoïsation sera évoquée dans le chapitre suivant.
Au cours du calcul, les résultats seront insérés en fin de la liste des nombres en utilisant la technique des différences de listes : cette méthode permet de concaténer n'importe quelles listes en une seule inférence, alors que append/3 est en O(N) où N est la longueur de la première chaîne.
IV-D-1. Le mécanisme des différences de listes.▲
Une liste écrite sous la forme d'une différence des listes s'écrit de manière générale X-Y. En utilisant les possibilités des Open Lists, on peut les écrire sous la forme [X|Y]-Y. Ainsi, pour concaténer des listes écrites en différences, on utilise le mécanisme suivant :
append_dl(X1-X2, X2-X3, X1-X3).Observons ce qui se passe lors de la concaténation avec cet exemple :
append_dl([1,2,3|T]-T, [4,5,6|U]-U, Z-U).On constate que
X1 est unifié avec [1,2,3|T].
X2 est unifié avec T et [4,5,6|U], donc T est unifié avec [4,5,6|U] et par voie de conséquence X1 est unifié avec [1,2,3,4,5,6|U].
La concaténation s'est faite en une seule inférence !
La transformation d'une différence de listes en liste normale est très simple et se fait en temps constant, il suffit de concaténer la différence de listes avec la liste vide représentée par []-[] :
dl_to_lf(DL, LF):-
append_dl(DL, []-[], LF-[]).IV-D-2. Le calcul des nombres de Fibonacci avec mémorisation▲
Comme dans la méthode itérative, les deux derniers nombres calculés servent au calcul du suivant. Le premier des deux nombres est mémorisé au moment du calcul avant d'être « oublié » par la boucle de calcul. Remarquons que insere_successeur passe de 2 arguments dans les DCG à 4 dans les règles Prolog. Le troisième argument peut être considéré comme un argument d'entrée de la clause (il contient la liste des résultats déjà connus) et le quatrième comme un argument de sortie (il contient un résultat de plus).
% la bonne valeur est trouvée
fib_dcg_memo(X, [X|_]) --> [].
% les deux derniers nombres calculés servent au calcul du suivant
fib_dcg_memo(X, [A, B]) -->
fib_dcg_memo_suivant(X, A, B, Fib1),
fib_dcg_memo_suivant(X, B, Fib1, Fib2),
fib_dcg_memo(X, [Fib1, Fib2]).
% Calcul du nombre de Fibonacci, somme des deux précédents
% le premier est mémorisé
fib_dcg_memo_suivant(X, fib(Idx1, Num1), fib(Idx2, Num2), fib(Idx3, Num3)) -->
insere_successeur(X, fib(Idx1, Num1)),
{ Idx3 is Idx2 + 1,
Num3 is Num1 + Num2 }.
% insertion en fin de liste d'un nombre de Fibonacci
% On s'assure qu'on n'a pas dépassé le nombre cherché
insere_successeur(A, B, Old, New) :-
gt(A, B),
append_dl(Old, [B|T2] - T2, New).
gt(fib(A, _FA), fib(B, _FB)) :-
À >= B.
append_dl(X1-X2, X2-X3, X1-X3).Le lancement du calcul peut se faire par :
fib_dcg_demo(X, FX, Lst_Fibo) :-
% fib_dcg_memo(arg1, arg2, arg3, arg4).
% arg1 : le tuple fib(X, FX) recherché
% arg2 : la liste contenant les deux premiers résultats connus nécessaires pour le calcul
% arg3 : la liste des tuples résultats mémorisés. À l'initialisation elle est vide
% donc initialisée à T-T, car c'est une différence de listes
% arg4 : la liste des tuples résultats connus après le calcul
fib_dcg_memo(fib(X, FX), [fib(0,0), fib(1,1)], T-T, Dl_Lst_Fibo),
% conversion de la liste des tuples en liste "normale"
dl_to_lf(Dl_Lst_Fibo, Lst_Fibo).Exemple de calcul :
?- fibo(8, FX, LstFibo).
FX = 21,
LstFibo = [fib(0, 0), fib(1, 1), fib(2, 1), fib(3, 2), fib(4, 3), fib(5, 5), fib(6, 8), fib(7, 13)] ;
NoÀ cause de la création de la liste des nombres de Fibonacci, la méthode ne permet pas d'aller plus loin que Fibonacci(50000). Les résultats sont honorables :
?- time(fib_dcg_memo(fib(50000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 425,001 inferences, 0.64 CPU in 0.73 seconds (88% CPU, 663416 Lips)
75 ?- time(fib_dcg_memo(fib(30000, FX), [fib(0,0), fib(1,1)], T-T, _)).
% 255,001 inferences, 0.28 CPU in 0.31 seconds (91% CPU, 906670 Lips)Les calculs sont plus rapides que pour la méthode avec les streams :
?- time(fib_OpenList(30000)).
% 360,029 inferences, 0.73 CPU in 0.89 seconds (83% CPU, 490252 Lips)IV-E. Le calcul des nombres de Fibonacci avec mémoïsation▲
Dans cette partie, on utilise la méthode récursive, mais les résultats sont mémorisés pour ne pas avoir à les recalculer. La recherche du résultat dans la liste se faisant à l'aide du prédicat member/2, on ne peut pas utiliser la technique des différences de listes. Voir iciLes Open Lists.
Les couples seront donc insérés en tête de la liste des résultats déjà connus.
Les règles de grammaire sont très simples : l'obtention d'un nombre de Fibonacci s'obtient soit par la recherche dans une liste, soit par le calcul des deux nombres précédents.
% premiere possibilité , on trouve le résultat dans la liste
fib_dcg_memoisation(A) -->
fib_dcg_memoisation_recherche(A), {!}.
% seconde possibilité, on calcule le nombre
fib_dcg_memoisation(A) -->
fib_dcg_memoisation_calcul(A).
% La recherche est le simple test member/2
fib_dcg_memoisation_recherche(A, Lst, Lst) :-
member(A, Lst).
% Le calcul est le calcul classique récursif.
fib_dcg_memoisation_calcul(fib(X, FX)) -->
{
X1 is X-1,
X2 is X-2
},
fib_dcg_memoisation(fib(X1, FX1)),
fib_dcg_memoisation(fib(X2, FX2)),
{
FX is FX1 + FX2
},
% le résultat est mémorisé
ajoute_fib_ver1(fib(X,FX)).
% mémorisation du nombre dans la liste
ajoute_fib_ver1(A, Old, [A | Old]).
fib_dcg_memoisation_lance(X, L) :-
fib_dcg_memoisation(X, [fib(1,1), fib(0,0)], L).Exemple de résultat :
32 ?- fib_dcg_memoisation_lance(fib(7,X), L).
X = 13,
L = [fib(7, 13), fib(6, 8), fib(5, 5), fib(4, 3), fib(3, 2), fib(2, 1), fib(1, 1), fib(0, 0)] ;
NoLes performances ne sont pas extraordinaires, près de 850 000 inférences pour le calcul de Fibonacci(50 000) :
33 ?- time(fib_dcg_memoisation_lance(fib(50000,_), _)).
% 849,988 inferences, 0.80 CPU in 0.96 seconds (83% CPU, 1066652 Lips)
YesV. Conclusion▲
On peut écrire un programme de test :
% programme de test
% N est le rang du nombre de Fibonnaci à calculer
test(N) :-
retractall(fibo(_,_)),
writeln('fib_iter'), time(fib_iter(N, _)), nl,
writeln('fib_memo'), time(fib_memo(N, _)), nl,
writeln('fib_assoc'), time(fib_assoc(N, _)), nl,
writeln('fib_OpenList'), time(fib_OpenList(N)), nl,
writeln('fib_dcg_ver1'), time(fib_dcg_ver1(fib(N, _))), nl,
writeln('fib_dcg_ver2'), time(fib_dcg_ver2(fib(N, _))), nl,
writeln('fib_dcg_memo'), time(fib_dcg_memo(fib(N, _), [fib(0,0), fib(1,1)], T-T, _)), nl,
writeln('fib_dcg_memoisation'), time(fib_dcg_memoisation(fib(N, _), [fib(1,1), fib(0,0)],_)).On obtient les résultats suivants pour le calcul de Fibonacci(30 000) :
1 ?- test(30000).
fib_iter
% 89,999 inferences, 0.13 CPU in 0.13 seconds (96% CPU, 719992 Lips)
fib_memo
% 209,998 inferences, 0.94 CPU in 1.07 seconds (88% CPU, 223998 Lips)
fib_assoc
% 3,433,516 inferences, 2.11 CPU in 2.19 seconds (96% CPU, 1627741 Lips)
fib_OpenList
% 361,667 inferences, 0.69 CPU in 0.89 seconds (77% CPU, 526061 Lips)
fib_dcg_ver1
% 239,994 inferences, 0.30 CPU in 0.31 seconds (94% CPU, 808401 Lips)
fib_dcg_ver2
% 149,998 inferences, 0.20 CPU in 0.21 seconds (95% CPU, 738452 Lips)
fib_dcg_memo
% 255,001 inferences, 0.23 CPU in 0.26 seconds (89% CPU, 1088004 Lips)
fib_dcg_memoisation
% 510,025 inferences, 0.33 CPU in 0.38 seconds (86% CPU, 1554362 Lips)
YesEn éliminant quatre méthodes qui ne dépassent pas le calcul de Fibonacci(50 000), on obtient ce résultat pour le calcul de Fibonacci(100 000) :
8 ?- test(100000).
fib_iter
% 299,999 inferences, 0.69 CPU in 1.05 seconds (66% CPU, 436362 Lips)
fib_memo
% 699,998 inferences, 28.52 CPU in 29.69 seconds (96% CPU, 24548 Lips)
fib_dcg_ver1
% 799,994 inferences, 0.70 CPU in 1.17 seconds (60% CPU, 1137769 Lips)
fib_dcg_ver2
% 499,999 inferences, 0.63 CPU in 1.08 seconds (58% CPU, 799998 Lips)
YesOn constate que la version la plus performante en nombre d'inférences est sans contestation possible la version itérative et que la version avec mémoïsation est très lente par rapport à la version écrite à l'aide des DCG sans le cut.
VI. Téléchargements▲
Le fichier « fibonacci.pl » donnant le code de tous les calculs décrits dans cet article est téléchargeable ici.
Il est aussi possible de télécharger une version PDF ici.
.
VII. Remerciements▲
Je tiens à remercier jbarreau-mainson pour sa relecture attentive, Gorgonite Alp et pcaboche pour leurs conseils avisés. :)