9

私はClojureでエラトステネスの篩のこの実装を持っています:

(defn sieve [n]
  (loop [last-tried 2 sift (range 2 (inc n))]
    (if
      (or (nil? last-tried) (> last-tried n))
      sift
      (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
        (let [next-to-try (first (filter #(> % last-tried) filtered))]
        (recur next-to-try filtered))))))

それより大きいn(20000 など) 場合は、スタック オーバーフローで終了します。ここでテールコールの除去が機能しないのはなぜですか? 修正方法は？

4

3 に答える 3

12

問題:filter遅延評価を行うため、新しいレベルのフィルタリングがコール スタックに残ります。

修正: に変更(filter ...)し(doall (filter ...))ます。

説明はこちらをご覧ください。

于 2010-06-05T14:05:56.707 に答える
2

バックトレースを見ると

(try
 (sieve 200000)
 (catch java.lang.StackOverflowError e
  (.printStackTrace e)))

次のようになります。

...
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
at clojure.lang.RT.seq(RT.java:440)
at clojure.core$seq__4176.invoke(core.clj:103)
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751)
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
...

ループではなく、オーバーフローを引き起こしているのはフィルターが多すぎるためです。

残念ながら、これに対する明確な解決策はわかりません。

于 2010-06-05T13:55:02.243 に答える
0

cgrande の美しいインクリメンタル SoE のチェックに関する Michal Marczyk のコメントに同意します。レイジープライムジェネレーターのパフォーマンスに興味がある人のために、いくつかの非常に原始的なベンチマークを行い、それらをhttp://clojure.roboloco.net/?p=100に掲載しました。

于 2010-06-09T03:16:34.863 に答える