Clojure - tamis récursive queue de Eratosthène

J'ai cette mise en œuvre du tamis d'Eratosthène en Clojure:Clojure - tamis récursive queue de Eratosthène

(defn sieve [n] 
    (loop [last-tried 2 sift (range 2 (inc n))] 
    (if 
     (or (nil? last-tried) (> last-tried n)) 
     sift 
     (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)] 
     (let [next-to-try (first (filter #(> % last-tried) filtered))] 
     (recur next-to-try filtered))))))

Pour plus n (comme 20000), il se termine par un débordement de pile. Pourquoi n'effectue-t-on pas un travail d'élimination de queue ici? Comment le réparer?

Source

2010-06-05 Konrad Garus

En note, mais ce n'est pas le tamis de Eratosthenes. SoE n'effectue pas d'opérations restantes, juste l'addition et le "barrage". Voir http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf pour une discussion prolongée (c'est une excellente lecture!); pour une belle mise en œuvre "incrémentale" de SoE dans Clojure par Christophe Grand, voir http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ (c'est aussi le plus rapide version que j'ai vu jusqu'ici). –

@ Michał Marczyk merci. Je dirais que "rayer" est équivalent à "filtrage", et "addition" dans cet algorithme est équivalent à "multiplication" et par conséquent "reste". –

Pas vraiment. Le résultat est, bien sûr, le même, mais la complexité algorithmique est très différente. –

Problème: filter effectue une évaluation paresseuse, de sorte que chaque nouveau niveau de filtrage se trouve sur la pile d'appels. Correction: (filter ...) à (doall (filter ...)). Voir l'explication here

Source

2010-06-05 14:05:56

Si vous regardez le backtrace

(try 
(sieve 200000) 
(catch java.lang.StackOverflowError e 
    (.printStackTrace e)))

il ressemble à ceci:

... 
at clojure.lang.LazySeq.sval(LazySeq.java:42) 
at clojure.lang.LazySeq.seq(LazySeq.java:56) 
at clojure.lang.RT.seq(RT.java:440) 
at clojure.core$seq__4176.invoke(core.clj:103) 
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751) 
at clojure.lang.LazySeq.sval(LazySeq.java:42) 
at clojure.lang.LazySeq.seq(LazySeq.java:56) 
...

Il y a trop de filtres qui est à l'origine du débordement, pas la boucle.

Malheureusement, je ne vois pas de solution évidente pour cela.

Source

2010-06-05 13:55:02 cobbal

L'indice était dans le LazySeq. La mise en œuvre de Clojures de Laziness a quelques getchas ceci étant l'un d'entre eux. –

vous avez correctement identifié le problème algorithmique principal (par opposition à technique). une solution évidente est d'arrêter le filtrage dès qu'il n'y a plus besoin de filtrer. et c'est-à-dire, quand '(> (* dernier-essayé dernier-essayé) n)'. Pour 20000, cela signifie que la profondeur de récursivité d'échange d'environ 2000, pour à peu près 30. –

(en effet [pour 16 000] (http://stackoverflow.com/a/41621006/849891) c'est 30 vs 1862 filtres imbriqués). –

J'ai secondé le commentaire de Michal Marczyk au sujet de la belle mise en valeur progressive de cgrande. J'ai fait quelques benchmarks vraiment primitifs et les ai mis en place au http://clojure.roboloco.net/?p=100, pour ceux qui sont curieux de connaître les performances des générateurs paresseux.

Source

2010-06-09 03:16:34 ivar

Clojure - tamis récursive queue de Eratosthène

Répondre

Questions connexes