lazy-seq и переполнение стека для бесконечных последовательностей

Я пытаюсь показать важность ленивых последовательностей или ленивую оценку программистам, не относящимся к FP. Я написал это реализация простого поколения, чтобы показать концепцию:lazy-seq и переполнение стека для бесконечных последовательностей

(defn primes-gen [sieve] 
    (if-not (empty? sieve) 
    (let [prime (first sieve)] 
     (cons prime 
      (lazy-seq (primes-gen 
         (filter (fn [x] 
           (not= 0 (mod x prime))) 
           (rest sieve)))))))) 

;;;;; --------- TO SHOW ABOUT THE LAZY-THINGS 
;; (take 400 (primes-gen (iterate inc 2))) 
;; (take 400 (primes-gen (range 2 1000000000000N)))

Однако, я получаю стеку переполнения исключения, если я давать какое-либо большее значение take.

Стек:

user> (pst) 
StackOverflowError 

    clojure.core/range/fn--4269 (core.clj:2664) 
    clojure.lang.LazySeq.sval (LazySeq.java:42) 
    clojure.lang.LazySeq.seq (LazySeq.java:60) 
    clojure.lang.RT.seq (RT.java:484) 
    clojure.core/seq (core.clj:133) 
    clojure.core/filter/fn--4226 (core.clj:2523) 
    clojure.lang.LazySeq.sval (LazySeq.java:42) 
    clojure.lang.LazySeq.seq (LazySeq.java:60) 
    clojure.lang.RT.seq (RT.java:484) 
    clojure.core/seq (core.clj:133)

кажется, что filter санки становятся накопили. Но если делать (doall (filter ..., то я не смог обработать бесконечные последовательности, то есть (take 1000 (primes-gen (iterate inc 2))) больше не работал.

Каков правильный путь?

источник

2015-03-16 Ashish Negi

Малый пункт: предпочитают '(если (далее сито) ...)' в '(если-нет (пустое сито) ...?)'. – Thumbnail

@amalloy отмеченный вопрос вовсе не дублируется этой: он имеет дело с конечными последовательностями, в то время как этот конкретно задает вопрос о * бесконечных *. Готов к открытию снова, надеюсь, вы тоже. –

@WillNess Согласен. Это одна и та же основная проблема, но ответы на вопрос, который я закрыл, как дубликат, не работают, когда вам нужно работать для бесконечного вывода. Ссылка для будущих зрителей: [Рекурсивная функция, вызывающая переполнение стека] (http://stackoverflow.com/q/2946764/625403) не является дубликатом, как я думал. – amalloy

Ваш анализ на месте: вы слишком много вложенных фильтров. Вы должны изменить prime-gen, чтобы взять два аргумента: набор известных простых чисел и кандидатов. См. Мой блог для некоторых других идей на implementing the Erathostenes' sieve.

Обновление: Итак, вы складываете фильтры по фильтрам, и в какой-то момент стек слишком велик, когда вы хотите получить нового кандидата.

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

(defn primes-gen 
([candidates] (primes-gen candidates [])) 
([candidates known-primes] 
    (lazy-seq ; I prefer having the lazy-seq up here 
    (when-first [prime candidates] ; little known macro 
     (let [known-primes (conj known-primes prime)] 
     (cons prime 
      (primes-gen 
      (drop-while (fn [n] (some #(zero? (mod n %)) known-primes)) candidates) 
      known-primes)))))))

источник

2015-03-16 09:32:07 cgrand

Мне жаль, что я не мог понять ваш алгоритм. На самом деле я больше заинтересован в том, как решить эту проблему, и не так много на алгоритме простого числа. Можете ли вы объяснить, в сущности, как вы решили эту проблему в вашем коде? –

В этом конкретном случае алгоритм изменения (до истинного сита) является стратегией «de-thunk». См. Мое обновление для менее решительного отклонения от исходного кода. – cgrand

Ох! так что посмотрим на это .. Я нахожу, что если я не буду использовать ленивые функции внутри 'lazy-seq', тогда у меня не будет проблем с громкой. это то, что происходит, когда мы используем '(doall' unlazy the lazy .., но вы показали, что мы действительно можем извлечь максимум из того, что работаем над бесконечным seq и no-thunks с лучшим пониманием проблемы и языка .. спасибо .. –

Одним из возможных решений будет перемещение функции генератора внутри ленивого сегмента. Например (из here):

(def primes 
    (concat 
    [2 3 5 7] 
    (lazy-seq 
    (let [primes-from 
      (fn primes-from [n [f & r]] 
      (if (some #(zero? (rem n %)) 
         (take-while #(<= (* % %) n) primes)) 
       (recur (+ n f) r) 
       (lazy-seq (cons n (primes-from (+ n f) r))))) 
      wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 
         6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 
         2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])] 
     (primes-from 11 wheel)))))

источник

2015-03-16 09:33:23 Jarlax

lazy-seq и переполнение стека для бесконечных последовательностей

ответ

Смежные вопросы