clojure - 惰性序列中的 OutOfMemoryError

Question

这个问题在这里已经有了答案:




8年前关闭。

Possible Duplicate:
Recursive function causing a stack overflow

完成示例惰性序列 here .

(defn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                             (rest s))))))

如果我尝试生成超过几千个左右的素数，则会出现 OutOfMemoryError。根据我的研究(但我对 clojure 很陌生)，我怀疑这可能是“捕获头”类的问题，但无法弄清楚为什么会这样或如何补救。如何更改此函数，以免在生成大量素数时内存不足？

Answer 1

您可以在不创建惰性序列的情况下使用版本。它工作得更快更便宜:

 (defn sieve* [res s]
      (if (empty? s)
        res
        (recur (conj res (first s))
               (filter #(not= 0 (mod % (first s)))
                       (rest s)))))

(defn sieve [n]
  (sieve* [] (range 2 n)))

(sieve 10000)
=> [2 3 5 7 11 13 17 ... 9941 9949 9967 9973]

这是更有效的版本:

(defn sieve* [res n maxn]
  (if (> n maxn)
    res
    (if (some #(= 0 (mod n %))
              (take (round (sqrt (count res))) res))
      (recur res (inc n) maxn)
      (recur (conj res n) (inc n) maxn))))

(defn sieve [n]
  (sieve* [] 2 n))

(last (sieve 1000000))
=> 999983

更新。 相当快/便宜的懒惰版本

(defn primes-seq* [primes]
  (let [last-prime (last primes)]
    (cons last-prime
          (lazy-seq
           (primes-seq*
            (conj primes
                  (first (let [compare-primes
                               (take (round (sqrt (count primes)))
                                     primes)]
                           (drop-while (fn [n]
                                         (some #(= 0 (mod n %))
                                               compare-primes))
                                       (iterate inc (inc last-prime)))))))))))


(def primes-seq (primes-seq* [2]))

(last (take 50000 primes-seq))
=> 611953