2

Possible Duplicate:
Recursive function causing a stack overflow

Working through the example lazy-seq here.

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

If I try to generate more than a couple of thousand primes or so, I get an OutOfMemoryError. Based on my research (but I am very new to clojure) I suspect this may be a problem of the class "hold onto head" but cannot figure out why that would be or how it might be remedied. How can this function be altered so as not to run out of memory when generating larger numbers of primes?

4

2 回答 2

2

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

 (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
于 2013-01-12T17:29:09.543 回答
1

给定的算法通过“记住”所有先前的素数来工作，所以如果你继续走足够长的时间，你将会破坏堆栈。

以下可能效率较低但不会耗尽内存（从我的4clojure解决方案改编为#116）：

(defn prime-seq []
  (letfn [(is-prime [x]
            (not (some #(= (rem x %) 0) (range 2 x))))]
    (filter is-prime (range))))

(take 20 (prime-seq))
;=> (0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61)
(nth (prime-seq) 10000)
;=> 104723
于 2013-01-12T17:21:51.870 回答