Clojure: Предотвращение переполнения стека в Решете Erathosthene?
Вот моя реализация Решета Erathosthene в Clojure (на основе урока SICP по потокам):
(defn nats-from [n]
(iterate inc n))
(defn divide? [p q]
(zero? (rem q p)))
(defn sieve [stream]
(lazy-seq (cons (first stream)
(sieve (remove #(divide? (first stream) %)
(rest stream))))))
(def primes (sieve (nats-from 2)))
Теперь, это - весь OK, когда я беру сначала 100 начал:
(take 100 primes)
Но, если я пытаюсь взять сначала 1 000 начал, повреждений программы из-за переполнения стека. Я задаюсь вопросом, ли возможно изменить так или иначе функциональное решето, чтобы стать рекурсивным хвостом и, тем не менее, сохранить "streamnes" алгоритма?
Какая-либо справка???
1 ответ
Во-первых, это не сито Эратосфена... см. мой комментарий для подробностей.
Во-вторых, извините за закрытое голосование, так как ваш вопрос не является фактическим дубликатом того, на который я указал... Виноват.
Объяснение происходящего
Разница, конечно, в том, что вы пытаетесь построить инкрементальное сито, где диапазон, в котором работает вызов remove, бесконечен, и поэтому невозможно просто обернуть doall вокруг него. Решением является реализация одного из "настоящих" инкрементальных SoE из статьи, на которую я, похоже, часто ссылаюсь в последнее время - The Genuine Sieve of Eratosthenes Мелиссы Э. О'Нил.
Особенно прекрасная реализация подобного сита в Clojure была написана Кристофом Грандом и доступна здесь для восхищения всех, кому это может быть интересно. Настоятельно рекомендую к прочтению.
Что касается источника проблемы, то вопросы, которые я изначально посчитал дубликатом вашего, содержат пояснения, которые должны быть вам полезны: смотрите здесь и здесь. Еще раз извините за поспешное голосование за закрытие.
Почему хвостовая рекурсия не поможет
Поскольку в вопросе конкретно упоминается создание хвостовой рекурсии для функции просеивания как возможное решение, я решил рассмотреть это здесь: функции, преобразующие ленивые последовательности, в общем случае не должны быть хвостовыми рекурсивными.
Это довольно важный момент, о котором следует помнить, и который ставит в тупик многих неопытных программистов на Clojure (или Haskell). Причина в том, что хвостовая рекурсивная функция по необходимости возвращает свое значение только тогда, когда она "готова" - в самом конце вычислений. (Итеративный процесс в конце любой конкретной итерации может либо вернуть значение, либо перейти к следующей итерации). В отличие от этого, функция, которая генерирует ленивую последовательность, должна немедленно вернуть объект ленивой последовательности, который содержит биты кода, которые можно попросить произвести голову или хвост последовательности, когда это необходимо.
Таким образом, ответ на проблему суммирования ленивых преобразований заключается не в том, чтобы сделать хвост рекурсивным, а в том, чтобы объединить преобразования. В этом конкретном случае наилучшая производительность может быть получена при использовании пользовательской схемы объединения операций фильтрации, основанной на приоритетных очередях или картах (подробности см. в вышеупомянутой статье).