的Clojure - 埃拉託塞尼

的尾遞歸篩餘有此實現埃拉託塞尼的Clojure中篩的：的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）將其與堆棧溢出結束。爲什麼不在這裏尾呼消除工作？如何解決它？

來源

2010-06-05 Konrad Garus

作爲一個附註，但這不是Eratosthenes的篩子。 SoE不執行剩餘操作，只是添加和「交叉」。參見http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf進行擴展討論（這是一篇很棒的閱讀！）;對於Christophe Grand在Clojure中一個漂亮的「增量」SoE實現，請參閱http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/（它也是最快的迄今爲止我見過的版本）。 – 2010-06-05 14:18:29

@MichałMarczyk謝謝。我會說「交叉」等同於「過濾」，並且此算法中的「加法」相當於「乘法」，因此也就是「餘數」。 – 2010-06-05 14:32:18

不是。結果當然是一樣的，但算法的複雜性是非常不同的。 – 2010-06-05 14:33:21

問題：filter做了懶惰的評估，因此每個新的過濾級別都會在調用堆棧上掛起。

修復：將(filter ...)更改爲(doall (filter ...))。

請參閱說明here。

來源

2010-06-05 14:05:56

如果你看一下回溯

(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-05 13:55:02 cobbal

線索在LazySeq中。 Clojures對懶惰的實現有一些問題，這就是其中之一。 – 2010-06-06 04:40:20

您已經正確識別了主要算法問題（與技術相對）。一個明顯的解決方案是在不需要過濾時立即停止過濾。也就是說，當'（>（* last-tried last-tried）n）'。對於20000，這意味着交易遞歸深度大約爲2000，大約爲30. – 2017-01-12 17:36:47

（實際上[對於16,000]（http://stackoverflow.com/a/41621006/849891）它是30對1862嵌套過濾器）。 – 2017-01-12 19:19:30

我第二次Michal Marczyk關於檢查cgrande美麗增量SoE的評論。我做了一些非常原始的基準測試，並把它們放在http://clojure.roboloco.net/?p=100，對於那些對懶惰的發電機性能感興趣的人。

來源

2010-06-09 03:16:34 ivar

的Clojure - 埃拉託塞尼

回答

相關問題