Clojure - хвостовое рекурсивное сито Эратосфена - PullRequest
Новая
       19

Clojure - хвостовое рекурсивное сито Эратосфена

9 голосов
/ 05 июня 2010

У меня есть эта реализация сита Эратосфена в 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 (например, 20000) это заканчивается переполнением стека. Почему здесь не работает устранение хвостовых вызовов? Как это исправить?

Ответы [ 3 ]

12 голосов
/ 05 июня 2010

Проблема: filter выполняет ленивую оценку, поэтому каждый новый уровень фильтрации зависает в стеке вызовов.

Исправлено: Изменить (filter ...) на (doall (filter ...)).

См. Объяснение здесь .

2 голосов
/ 05 июня 2010

Если вы посмотрите на след 

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

Переполнение вызывает слишком много фильтров, а не цикл.

К сожалению, я не вижу очевидного решения для этого.

0 голосов
/ 09 июня 2010

Я второй комментарий Михала Марчика о проверке прекрасного возрастающего SoE cgrande. Я сделал несколько действительно примитивных тестов и поставил их на http://clojure.roboloco.net/?p=100, для тех, кому интересно работать с ленивыми простыми генераторами.

...