的OutOfMemoryError在懶-SEQ

可能重複：
Recursive function causing a stack overflow 的OutOfMemoryError在懶-SEQ

通過示例懶惰-SEQ here工作。

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

如果我試圖產生超過幾千素數左右，我得到一個OutOfMemoryError。基於我的研究（但我對clojure非常陌生），我懷疑這可能是一個「頭等大事」的問題，但無法弄清楚爲什麼會這樣或者如何修復。如何修改這個函數以便在產生大量素數時不會耗盡內存？

來源

2013-01-12 richguy

這裏http://stackoverflow.com/questions/2980587/clojure-tail-recursive-sieve-of-eratosthenes同時要求，在這裏得到解答http://stackoverflow.com/問題/ 2946764 /遞歸函數引起-一個堆棧溢出。 –

感謝您指出這一點，這回答了我的問題，我認爲我已經充分搜索，顯然不是。 – richguy

雖然通過它後，它似乎並沒有解決我的問題。 – richguy

可以使用的版本，而無需創建懶序列。它的工作原理更快，更便宜：

(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-12 17:29:09 mobyte

我寧願懶惰的解決方案，謝謝。 – richguy

@richguy沒問題。我已經添加了懶惰版本。 – mobyte

給定的算法通過「記住」所有以前的素數來工作，所以如果持續足夠長的時間，就會吹掉堆棧。

下可能不太有效，但不會佔用內存（摘自我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-12 17:21:51 JohnJ

這個工程，但你說的很慢。 – richguy

的OutOfMemoryError在懶-SEQ

回答

相關問題