39

clojure で素数を計算するための単純なふるい関数を作成しようとしています。効率的なふるい関数の作成に関するこの質問を見たことがありますが、まだその時点ではありません。今、私は非常に単純な (そして遅い) ふるいを書こうとしています。これが私が思いついたものです：

(defn sieve [potentials primes]
  (if-let [p (first potentials)]
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p))
    primes))

範囲が小さい場合は問題なく動作しますが、範囲が大きい場合はスタック オーバーフローが発生します。

user=> (sieve (range 2 30) [])
[2 3 5 7 11 13 17 19 23 29]
user=> (sieve (range 2 15000) [])
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

これを使用recurすると、スタックを消費しないループ構造になると思いましたか? 私は何が欠けていますか？

4

2 に答える 2

57

あなたはfilterの怠惰にやられています。フォームに変更(filter ...)すると、問題は解消さ(doall (filter ...))れます。recur

より詳細な説明：

への呼び出しfilterは、必要に応じてフィルタリングされた seq の実際の要素を具体化する遅延 seq を返します。書かれているように、コードは ... に積み上げられ、各反復で ingのレベルが 1 つ追加filterさfilterれます。ある時点でこれは爆発します。解決策は、各反復で結果全体を強制することです。これにより、次の反復では、遅延 seq 処理のレイヤーを追加する代わりに、完全に実現された seq でフィルタリングを行い、完全に実現された seq を返します。それがそうです。filterfilterdoall

于 2010-06-01T01:34:59.293 に答える
-1

アルゴリズム上の問題は、目的がなくなったときにフィルタリングを続行することです。できるだけ早く停止すると、再帰の深さ ( sqrt(n)vs. n)が 2 次削減されます。

(defn sieve [potentials primes]    
  (if-let [p (first potentials)]
      (if (> (* p p) (last potentials))
        (concat primes potentials)
        (recur (filter (fn [n] (not= (mod n p) 0)) potentials)
               (conj primes p)))
    primes))

ideoneでは 16,000 回 (1862 回ではなく 30 回の繰り返しを実行) で正常に実行され、160,000 回でも正常に実行されます。.なしでも 5% 高速に実行できますdoall。

于 2017-01-12T19:06:49.300 に答える