2

重複
の可能性：スタックオーバーフローを引き起こす再帰関数

ここで例のlazy-seqを実行します。

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

数千を超える素数を生成しようとすると、OutOfMemoryErrorが発生します。私の調査に基づくと（しかし、私はclojureに非常に慣れていません）、これは「頭を抱える」クラスの問題かもしれないと思いますが、なぜそうなるのか、どのように改善されるのか理解できません。多数の素数を生成するときにメモリが不足しないように、この関数をどのように変更できますか？

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 に答える