Ce qui est fou, c'est qu'apparement l'interpreteur LISP a déjà compris lors du premier appel que c'est un appel "tail recursive" au vu de tes temps d'execution. Si c'est le cas et sans directives, je suis vraiment épaté.
En fait, tu commences par calculer fib(999), puis pour calculer fib(999) tu calcules fib(998), etc, etc -> tu ne descends qu'un fois pour calculer chaque valeur de fib jusqu'à 1 et ensuite tout ce que tu calcules est déjà stocké dans la table de hachage => gain de temps là où normalement tu devrais calculer chaque valeur à chaque fois en remontant.
Sinon, niveau optimisation, je n'ai rien rajouté (juste compilé chaque fonction).
Par contre, sans la mémoization, fib(44) met environ 80 secondes sur ma machine avec la version recursive de base (je n'ai pas encore eu le temps de tester la version avec une boucle) et j'ai arrété fib(1000) ;-)
Pour la notation infix, j'en ai déjà parlé ici, mais tu as des macros qui te permettent de faire tes calculs dans cette notation, et c'est le compilateur qui se charge de les transformer en notation prefix avec de les évaluer. http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/l(...)
A chaque cas sa solution, et je crois que c'est un peu l'esprit qui se dégage sur cette news.
[^] # Re: Comment casser le mythe de rapidité de Fibonacci :-)
Posté par hocwp (site web personnel) . En réponse à la dépêche Erlang/OTP R11B supporte les architectures multiprocesseur. Évalué à 2.
En fait, tu commences par calculer fib(999), puis pour calculer fib(999) tu calcules fib(998), etc, etc -> tu ne descends qu'un fois pour calculer chaque valeur de fib jusqu'à 1 et ensuite tout ce que tu calcules est déjà stocké dans la table de hachage => gain de temps là où normalement tu devrais calculer chaque valeur à chaque fois en remontant.
Sinon, niveau optimisation, je n'ai rien rajouté (juste compilé chaque fonction).
Par contre, sans la mémoization, fib(44) met environ 80 secondes sur ma machine avec la version recursive de base (je n'ai pas encore eu le temps de tester la version avec une boucle) et j'ai arrété fib(1000) ;-)
Pour la notation infix, j'en ai déjà parlé ici, mais tu as des macros qui te permettent de faire tes calculs dans cette notation, et c'est le compilateur qui se charge de les transformer en notation prefix avec de les évaluer.
http://www.cs.cmu.edu/afs/cs/project/ai-repository/ai/lang/l(...)
Oui, je crois que ça resume bien la situation.