Рекурсивная функция, вызывающая переполнение стека

Question

Я пытаюсь написать простую функцию сита для вычисления простых чисел в clojure. Я видел этот вопрос о написании эффективной функции сита, но я пока не дошел до этого. Сейчас я просто пытаюсь написать очень простое (и медленное) сито. Вот что я придумала:

(defn sieve [potentials primes]
  (if-let [p (first potentials)]
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p))
    primes))

Для небольших диапазонов работает нормально, но вызывает переполнение стека для больших диапазонов:

user=> (sieve (range 2 30) [])
[2 3 5 7 11 13 17 19 23 29]
user=> (sieve (range 2 15000) [])
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Я думал, что при использовании recur это будет циклическая конструкция без использования стека? Чего мне не хватает?

Answer 1

Тебя поражает лень filter. Измените (filter ...) на (doall (filter ...)) в форме recur, и проблема должна исчезнуть.

Более подробное объяснение:

Вызов filter возвращает ленивый seq, который материализует фактические элементы фильтрованного seq по мере необходимости. Как написано, ваш код стекается filter на filter на filter ..., добавляя еще один уровень filter на каждой итерации; в какой-то момент это взрывается. Решение состоит в том, чтобы форсировать весь результат на каждой итерации, чтобы следующая выполняла свою фильтрацию на полностью реализованном seq и возвращала полностью реализованный seq вместо добавления дополнительного уровня обработки lazy seq; это то, что doall делает.

Answer 2

Алгоритмически проблема в том, что вы продолжаете фильтрацию, когда в ней больше нет цели. Остановка как можно раньше приводит к квадратичному уменьшению глубины рекурсии (sqrt(n) против n):

(defn sieve [potentials primes]    
  (if-let [p (first potentials)]
      (if (> (* p p) (last potentials))
        (concat primes potentials)
        (recur (filter (fn [n] (not= (mod n p) 0)) potentials)
               (conj primes p)))
    primes))

Работает нормально для 16 000 (выполняя всего 30 итераций вместо 1862), и для 160 000 тоже для идеона . Даже работает на 5% быстрее без doall.