Clojure: Как избежать переполнения стека в Sieve of Erathosthene? - PullRequest
Новая
       25

Clojure: Как избежать переполнения стека в Sieve of Erathosthene?

11 голосов
/ 07 июня 2010

Вот моя реализация Sieve of 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)))

Теперь все нормально, когда я беру первые 100 простых чисел: 

(take 100 primes)

Но, если я попытаюсь взять первые 1000 простых чисел , программа остановится из-за переполнения стека. Мне интересно, можно ли как-то изменить функцию sieve, чтобы она стала хвостовой рекурсивной и, тем не менее, сохранить "потоки" алгоритма?

Любая помощь ???

1 Ответ

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

Во-первых, это не сито Эратосфена ... подробности смотрите в моем комментарии.

Во-вторых, извинения за закрытое голосование, поскольку ваш вопрос не является точной копией того, на который я указал ... Мой плохой.

Объяснение того, что происходит

Разница, конечно, заключается в том, что вы пытаетесь построить инкрементальное сито, где диапазон, в котором работает вызов remove, бесконечен, и поэтому невозможно просто обернуть doall вокруг него. Решение состоит в том, чтобы внедрить одно из «настоящих» инкрементальных СО из статьи, на которую я, похоже, довольно часто ссылаюсь в наши дни - «1011 * Подлинное сито Эратосфена» Мелиссы Э. О'Нил .

Особенно красивая реализация сита Clojure такого рода была написана Кристофом Грандом и доступна здесь для восхищения всех, кто может быть заинтересован. Настоятельно рекомендуется к прочтению.

Что касается источника проблемы, то вопросы, которые я первоначально считал вашими, были дубликатами с пояснениями, которые должны быть вам полезны: см. здесь и здесь . Еще раз извините за необдуманное закрытие голосования.

Почему рекурсия хвоста не поможет

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

Это очень важный момент, о котором следует помнить, и который сбивает с толку многих неопытных программистов на Clojure (или Haskell). Причина в том, что хвостовая рекурсивная функция необходимости возвращает свое значение только тогда, когда она «готова» - в самом конце вычисления. (Итеративный процесс может в конце любой конкретной итерации либо вернуть значение, либо перейти к следующей итерации.) В отличие от этого, функция, которая генерирует ленивую последовательность, должна немедленно вернуть ленивый объект последовательности, который инкапсулирует биты кода, которые можно попросить произвести головку или хвост последовательности, когда это необходимо.

Таким образом, ответ на проблему суммирования ленивых преобразований состоит не в том, чтобы сделать что-либо хвостовым рекурсивным, а в объединении преобразований. В этом конкретном случае наилучшую производительность можно получить, используя пользовательскую схему для объединения операций фильтрации, основанную на приоритетных очередях или картах (подробности см. в вышеупомянутой статье ).

...