Clojure：避免Erathosthene筛选中的堆栈溢出？ [英] Clojure: Avoiding stack overflow in Sieve of Erathosthene?
问题描述
这是我在Clojure中筛选Erathosthene的实现（基于SICP课程）：
（defn nats-from [n]
（iterate inc n））
（defn divide？[pq]
（zero？（rem qp）））
defn sieve [stream]
（lazy-seq（cons（first stream）
（sieve（remove＃（divide？（first stream）％）
（rest stream）））））））
（def primes（sieve（from 2）））
现在，当我服用前100个素数是肯定的：
（100个素数）
但是，如果我试图采取前1000个素数，程序中断，因为堆栈溢出。
我想知道是否可以改变某种方式函数筛选成尾递归，仍然保留算法的streamnes。
任何help
首先，这不是Sieve of Eratosthenes ...看我的评论。 >
其次，对于接近投票表示歉意，因为你的问题不是我指向的那个的实际重复...我的错。
正在发生的事情的说明
区别当然在于您正在尝试建立一个增量其中 remove 调用的范围是无限的，因此不可能在其周围包裹 doall 。解决方案是实现一个真正的增量SoE从我似乎链接到这些天很频繁的论文 - Melissa E. O'Neill的 Eratosthenes的真正筛子。
一个特别好的Clojure筛选实现这是由Christophe Grand撰写的，可以从这里为所有可能感兴趣的人的钦佩。强烈推荐阅读。
至于问题的根源，我最初认为你的问题是含有解释的重复，应该对你有用：参见这里和这里。
为什么尾递归不起作用
问题特别提到筛选函数尾递归作为一种可能的解决方案，我想我会在这里解决：转换惰性序列的函数一般不应该是尾递归。
b$ b
这是一个非常重要的一点要记住，并且一个很多没有经验的Clojure（或Haskell）程序员。原因是一个尾递归函数的必要性只有在就绪时才返回其值 - 在计算的最后。 （迭代过程可以在任何特定迭代结束时返回值或继续下一次迭代。）在对照中，生成延迟序列的函数应立即返回一个惰性序列对象，该对象封装了代码位，
因此，堆积延迟变换问题的答案不是使任何尾部递归，而是以合并变换。在这种特定情况下，可以通过使用定制方案来基于优先级队列或映射来融合滤波操作来获得最佳性能（参见上述文章）。
Here's my implementation of Sieve of Erathosthene in Clojure (based on SICP lesson on streams):
(defn nats-from [n]
(iterate inc n))
(defn divide? [p q]
(zero? (rem q p)))
(defn sieve [stream]
(lazy-seq (cons (first stream)
(sieve (remove #(divide? (first stream) %)
(rest stream))))))
(def primes (sieve (nats-from 2)))
Now, it's all OK when i take first 100 primes:
(take 100 primes)
But, if i try to take first 1000 primes, program breaks because of stack overflow. I'm wondering if is it possible to change somehow function sieve to become tail-recursive and, still, to preserve "streamnes" of algorithm?
Any help???
Firstly, this is not the Sieve of Eratosthenes... see my comment for details.
Secondly, apologies for the close vote, as your question is not an actual duplicate of the one I pointed to... My bad.
Explanation of what is happening
The difference lies of course in the fact that you are trying to build an incremental sieve, where the range over which the remove call works is infinite and thus it's impossible to just wrap a doall around it. The solution is to implement one of the "real" incremental SoEs from the paper I seem to link to pretty frequently these days -- Melissa E. O'Neill's The Genuine Sieve of Eratosthenes.
A particularly beatiful Clojure sieve implementation of this sort has been written by Christophe Grand and is available here for the admiration of all who might be interested. Highly recommended reading.
As for the source of the issue, the questions I originally thought yours was a duplicate of contain explanations which should be useful to you: see here and here. Once again, sorry for the rash vote to close.
Why tail recursion won't help
Since the question specifically mentions making the sieving function tail-recursive as a possible solution, I thought I would address that here: functions which transform lazy sequences should not, in general, be tail recursive.
This is quite an important point to keep in mind and one which trips up many an unexperienced Clojure (or Haskell) programmer. The reason is that a tail recursive function of necessity only returns its value once it is "ready" -- at the very end of the computation. (An iterative process can, at the end of any particular iteration, either return a value or continue on to the next iteration.) In constrast, a function which generates a lazy sequence should immediately return a lazy sequence object which encapsulates bits of code which can be asked to produce the head or tail of the sequence whenever that's desired.
Thus the answer to the problem of stacking lazy transformations is not to make anything tail recursive, but to merge the transformations. In this particular case, the best performance can be obtained by using a custom scheme to fuse the filtering operations, based on priority queues or maps (see the aforementioned article for details).
这篇关于Clojure：避免Erathosthene筛选中的堆栈溢出？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
