Clojure - хвост рекурсивное решето Эратосфена
У меня есть эта реализация решета Эратосфена в 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))))))
Для большего n (как 20 000), это заканчивается переполнением стека. Почему устранение последнего вызова не работает здесь? Как зафиксировать его?
3 ответа
Проблема: filter выполняет отложенную оценку, поэтому каждый новый уровень фильтрации зависает в стеке вызовов.
Исправление: Изменить (фильтр ...) до (doall (фильтр ...)) .
См. объяснение здесь.
Если вы посмотрите на бэктрейс
(try
(sieve 200000)
(catch java.lang.StackOverflowError e
(.printStackTrace e)))
то он выглядит так:
...
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)
...
Это слишком много фильтров, которые вызывают переполнение, а не цикл.
К сожалению, я не вижу очевидного решения для этого.
Я повторяю комментарий Михала Марчика о проверке красивой инкрементальной SoE cgrande. Я провел несколько действительно примитивных тестов и разместил их на http://clojure.roboloco.net/?p=100 для тех, кто интересуется производительностью ленивого генератора простых чисел.