Prolog et Fibonacci


précédentsommairesuivant

V. Conclusion.

On peut écrire un programme de test :

Prolog
Sélectionnez
% 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) :

Console Prolog
Sélectionnez
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)

Yes

En é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) :

Console Prolog
Sélectionnez
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)

Yes

On 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.


précédentsommairesuivant

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