J'ai cette implémentation du tamis des eratosthènes dans le clojure: pour plus grand n (comme 20000) il se termine par un débordement de pile. Pourquoi la queue n'appelle pas l'élimination des appels ici? Comment réparer cela?
3 Réponses :
Si vous regardez l'arrière-arrière , il ressemble à ceci: C'est trop de filtres qui causent le trop-plein, pas La boucle. Malheureusement, je ne vois pas une solution évidente pour cela.
L'indice était dans le Lazyseq. Les clojures La mise en œuvre de la paresse a quelques gotchas, cela étant l'un d'entre eux.
Vous avez correctement identifié le principal problème algorithmique (par opposition à juste technique). Une solution évidente consiste à arrêter le filtrage dès qu'il n'y a plus besoin de filtrer. Et c'est-à-dire quand (> (* derniers a essayé de dernière fois) n) . Pour 20000, cela signifie une profondeur de récursivité d'environ 2000, pour une peine d'environ 30 ans.
(en effet pour 16 000 , il s'agit de filtres imbriqués 30 VS 1862).
Problème: Correction: Changer Voir l'explication ici . Filtre L'évaluation paresseuse est donc de sorte que chaque nouveau niveau de filtrage se bloque sur la pile d'appels.
(filtrer ...) à (DOTALL (filtre ...)) . .
I Deuxième commentaire de Michal Marczyk sur la vérification de la belle SOE incrémentielle de Cgrande. J'ai fait des points de repère vraiment primitifs et mettais-les à http://clojure.roboloco.net/?p = 100 , pour ceux qui curieux de la performance des générateurs de premiers paresseux.
À titre de note latérale, mais ce n'est pas le tamis des eratosthènes. SOE n'effectue aucune opération de reste, juste addition et «traversée». Voir CS.HMC.EDU/~NEILL/PAPERS/SIEve-JFP .pdf pour une discussion prolongée (c'est une bonne lecture!); Pour une belle mise en œuvre de SOE "incrémentielle" dans le clojure de Christophe Grand, voir clj-me.cgrand.net/2009/07/30/... (c'est aussi la version la plus rapide que j'ai vue jusqu'à présent).
@ Michał Marczyk merci. Je dirais que "traverser" équivaut à "filtrer" et "addition" dans cet algorithme équivaut à "multiplication" et par conséquent "reste".
Pas vraiment. Le résultat est bien sûr la même chose, mais la complexité algorithmique est extrêmement différente.
L'article est très bon avec les calculs mais fait malheureusement un mauvais travail avec des mots expliquant les mathématiques. La différence se situe entre l'élimination itérative des composites testés par des morceaux croissants contigus des nombres premiers (premier 1, premier 2, premiers 3 premiers, des 4 premiers premiers, ...) , vs production indépendante de composites à partir de Ses principaux facteurs seulement (
p -> {p * p, p * p + p, p * p + 2 * p, ...} ).