/ / Clojure - sito rekurencyjne Eratostenesa - algorytm, clojure, funkcjonalne programowanie, liczby pierwsze, sito eratosteny

Clojure - ogonkowe sito rekurencyjne Eratostenesa - algorytm, clojure, funkcjonalne programowanie, liczby pierwsze, sito eratosteny

Mam tę implementację sita Eratostenesa w Clojure:

(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))))))

Dla większych n (jak 20000) kończy się przepełnieniem stosu. Dlaczego tutaj nie działa eliminacja połączeń końcowych? Jak to naprawić?

Odpowiedzi:

12 dla odpowiedzi № 1

Problem: filter robi leniwą ocenę, więc każdy nowy poziom filtrowania rozłącza się na stosie wywołań.

Napraw: Zmień (filter ...) do (doall (filter ...)).

Zobacz wyjaśnienie tutaj.


2 dla odpowiedzi nr 2

Jeśli spojrzysz na ślad śledzenia

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

To wygląda tak:

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

To zbyt wiele filtrów, które powodują przepełnienie, a nie pętlę.

Niestety, nie widzę dla tego oczywistego rozwiązania.


0 dla odpowiedzi № 3

Zastanawiam się nad komentarzem Michała Marczyka na temat sprawdzania pięknego SoE w cgrande. Zrobiłem naprawdę prymitywne testy porównawcze i umieściłem je na http://clojure.roboloco.net/?p=100, dla osób ciekawi wydajności leniwego generatora.