Clojure - StackOverflowError при переборе ленивой коллекции - PullRequest
Новая
       24

Clojure - StackOverflowError при переборе ленивой коллекции

3 голосов
/ 14 апреля 2019

В настоящее время я внедряю решение для одной из задач Project Euler, а именно - Sieve of Eratosthenes (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), в Clojure. Вот мой код: 

(defn cross-first-element [coll]
  (filter #(not (zero? (rem % (first coll)))) coll))

(println
  (last
  (map first
    (take-while
      (fn [[primes sieve]] (not (empty? sieve)))
      (iterate
        (fn [[primes sieve]] [(conj primes (first sieve)) (cross-first-element sieve)])
        [[] (range 2 2000001)])))))

Основная идея состоит в том, чтобы иметь две коллекции - простые числа, уже извлеченные из сита, и оставшееся само сито. Мы начинаем с пустого primes, и пока сито не станет пустым, мы выбираем его первый элемент и добавляем его к primes, а затем вычеркиваем кратные его числа из сита. Когда он исчерпан, мы знаем, что у нас есть все простые числа из двух миллионов в простых числах.

К сожалению, как бы хорошо оно ни работало для маленькой верхней границы сита (скажем, 1000), оно вызывает java.lang.StackOverflowError с длинной трассировкой стека с повторяющейся последовательностью: 

...
clojure.lang.RT.seq (RT.java:531)
clojure.core$seq__5387.invokeStatic (core.clj:137)
clojure.core$filter$fn__5878.invoke (core.clj:2809)
clojure.lang.LazySeq.sval (LazySeq.java:42)
clojure.lang.LazySeq.seq (LazySeq.java:51)
...

Где концептуальная ошибка в моем решении? Как это исправить?

Ответы [ 2 ]

1 голос
/ 15 апреля 2019

причина этого заключается в следующем: поскольку функция filter в вашем cross-first-element является ленивой, она фактически не фильтрует вашу коллекцию на каждом шаге iterate, а скорее «штабелирует» вызовы функции фильтрации. Это приводит к тому, что когда вам действительно понадобится результирующий элемент, будет выполнена вся нагрузка тестовых функций, примерно так: 

(#(not (zero? (rem % (first coll1))))
  (#(not (zero? (rem % (first coll2))))
    (#(not (zero? (rem % (first coll3))))
       ;; and 2000000 more calls

приводит к переполнению стека.

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

Но, тем не менее, ваше решение действительно медленное. Я бы предпочел использовать для этого циклические и нативные массивы.

0 голосов
/ 15 апреля 2019

Вы (повторно) обнаружили, что наличие вложенных ленивых последовательностей иногда может быть проблематичным. Вот один пример того, что может пойти не так (это не интуитивно понятно).

Если вы не возражаете против использования библиотеки, проблема намного проще с одной ленивой оболочкой вокругимперативная петля.Вот что lazy-gen и yield дают вам (а-ля "генераторы" в Python): 

(ns tst.demo.core
  (:use demo.core tupelo.test)
  (:require [tupelo.core :as t]))

(defn unprime? [primes-so-far candidate]
  (t/has-some? #(zero? (rem candidate %)) primes-so-far))

(defn primes-generator []
  (let [primes-so-far (atom [2])]
    (t/lazy-gen
      (t/yield 2)
      (doseq [candidate (drop 3 (range))] ; 3..inf
        (when-not (unprime? @primes-so-far candidate)
          (t/yield candidate)
          (swap! primes-so-far conj candidate))))))

(def primes (primes-generator))

(dotest
  (is= (take 33 primes)
    [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 ])

  ; first prime over 10,000
  (is= 10007 (first (drop-while #(< % 10000) primes)))

  ; the 10,000'th prime (https://primes.utm.edu/lists/small/10000.txt)
  (is= 104729 (nth primes 9999)) ; about 12 sec to compute
)

Мы могли бы также использовать loop/recur для управления циклом, но легче читать сatom для хранения состояния.

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

(defn primes-upto [limit]
  (let [primes-so-far (atom [2])]
    (doseq [candidate (t/thru 3 limit)]
      (when-not (unprime? @primes-so-far candidate)
        (swap! primes-so-far conj candidate)))
    @primes-so-far))

(dotest
  (is= (primes-upto 100)
    [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]) )
...