mud*_*dge 29 lisp clojure lazy-evaluation lazy-sequences
我喜欢Clojure.困扰我的一个问题是我不知道如何实现懒惰的序列,或者它们是如何工作的.
我知道懒惰序列只评估序列中要求的项目.它是如何做到的？
Isa*_*aac 32
我们开工吧.
• 我知道懒惰序列只评估序列中要求的项目,它是如何做到的？
懒惰的序列(以下称LS,因为我是LP,或懒惰的人)由部分组成.对于已经评估过的序列的头部或部分(s,实际上是32个元素,一次评估,如Clojure 1.1,我认为1.2)之后是一个叫做thunk的东西,它基本上是一个块信息(将其视为创建序列的其余部分,未评估)等待被调用.当它被调用时,thunk会对它进行评估,然后会根据需要创建一个新的thunk(已经调用了多少内容,因此它可以从之前的位置恢复).
所以你(take 10 (whole-numbers))- 假设whole-numbers是一个整数的懒惰序列.这意味着你要强制评估10次thunk(虽然内部这可能会有所不同,具体取决于优化.
• 什么使得延迟序列如此高效以至于它们不会消耗太多堆栈？
一旦你阅读了之前的答案(我希望),这一点就会变得更加清晰:除非你特别要求某些东西,否则不会评估任何东西.当你调用某个东西时,可以单独评估序列的每个元素,然后丢弃.
如果序列不是懒惰的,那么它通常会保持在头部,这会消耗堆空间.如果它是惰性的,则计算,然后丢弃,因为后续计算不需要它.
• 为什么你可以在延迟序列中包装递归调用,并且不再为大型计算获得堆栈溢出？
请参阅上一个答案并考虑:lazy-seq宏(来自文档)将
will invoke the body only the first time seq
is called, and will cache the result and return it on all subsequent
seq calls.
查看filter使用递归的酷LS 的函数:
(defn filter
"Returns a lazy sequence of the items in coll for which
(pred item) returns true. pred must be free of side-effects."
[pred coll]
(let [step (fn [p c]
(when-let [s (seq c)]
(if (p (first s))
(cons (first s) (filter p (rest s)))
(recur p (rest s)))))]
(lazy-seq (step pred coll))))
• 懒惰序列消耗什么资源来完成它的工作？
我不太清楚你在这里问的是什么.LS需要内存和CPU周期.他们只是不会继续敲打堆栈,并用获取序列元素所需的计算结果填充它.
• 什么情况下懒惰序列效率低下？
当你使用快速计算并且不会被大量使用的小seq时,使它成为LS是低效的,因为它需要另外几个chars来创建.
说真的,除非你试图做出一些非常高效的东西,否则LS就是你要走的路.
• 什么情况下懒惰序列最有效？
当你处理巨大的seqs并且你只使用它们的零碎时,那就是你从使用它们中获得最大收益的时候.
实际上,在方便性,易于理解(一旦掌握它们)以及推理代码和速度方面,使用LS而不是非LS更好总是更好.
Mic*_*zyk 16
我知道懒惰序列只评估序列中要求的项目,它是如何做到的？
我认为以前发布的答案已经很好地解释了这一部分.我只会补充说,一个懒惰序列的"强制"是一个隐含的 - 无法释放!:-) - 函数调用; 也许这种思考方式会让事情变得更加清晰.还要注意,强制一个懒惰的序列涉及一个隐藏的变异 - 强制thunk需要产生一个值,将它存储在缓存中(变异!)并扔掉它的可执行代码,这将不再需要(再次变异!) .
我知道懒惰序列只评估序列中要求的项目,它是如何做到的？
什么使得延迟序列如此高效以至于它们不会消耗太多堆栈？
懒惰序列消耗什么资源来做它做的事情？
它们不消耗堆栈,因为它们会消耗堆.延迟序列是一种生活在堆上的数据结构,它包含一小段可执行代码,如果需要,可以调用它来生成更多的数据结构.
为什么你可以在延迟序列中包装递归调用,并且不再为大型计算获得堆栈溢出？
首先,正如dbyrne所提到的,如果thunk本身需要使用非常深层嵌套的调用结构来执行代码,那么在使用延迟序列时,你很可能会得到一个SO.
但是,从某种意义上说,你可以使用lazy seqs代替尾递归,并且在某种程度上这对你很有用,你可以说它们有助于避免SO.事实上,相当重要的是,产生延迟序列的函数不应该是尾递归的; 使用lazy seq生成器保留堆栈空间源于前面提到的堆栈 - >堆转移,任何以尾递归方式编写它们的尝试都只会破坏事物.
关键的见解是懒惰序列是一个对象,在第一次创建时,它不包含任何项目(严格的序列始终如此); 当一个函数返回一个惰性序列时,在发生任何强制之前,只有这个"惰性序列对象"被返回给调用者.因此,在发生任何强制之前,弹出返回延迟序列的调用所用的堆栈帧.我们来看一个示例生成器函数:
(defn foo-producer [] ; not tail recursive...
(lazy-seq
(cons :foo ; because it returns the value of the cons call...
(foo-producer)))) ; which wraps a non-tail self-call
这是有效的,因为立即lazy-seq返回,因此也立即返回,并立即弹出外部调用使用的堆栈帧.内部调用隐藏在序列的一部分中,这是一个thunk; 如果/当该thunk被强制时,它将在堆栈上短暂地使用它自己的帧,但是然后如上所述立即返回等.(cons :foo (foo-producer))foo-producerfoo-producerrest
Chunking(由dbyrne提到)稍微改变了这张图片,因为在每一步产生了更多的元素,但原理保持不变:当生成lazy seq的相应元素时,每个步骤都用完了一些堆栈,然后在更多强制发生之前回收该堆栈.
在什么情况下懒惰序列效率低下？
在什么情况下懒惰序列最有效？
如果你无论如何都需要同时握住整个东西,那就没有意义了.一个懒惰的序列在每个步骤进行堆分配时,不分块或每个块 - 每32个步骤一次 - 分块时; 避免这种情况可以在某些情况下为您带来性能提升.
但是,延迟序列支持流水线模式的数据处理:
(->> (lazy-seq-producer) ; possibly (->> (range)
(a-lazy-seq-transformer-function) ; (filter even?)
(another-transformer-function)) ; (map inc))
以严格的方式执行此操作无论如何都会分配大量的堆,因为您必须保留中间结果以将它们传递到下一个处理阶段.而且,你需要保持整个事物,这实际上是不可能的(range)- 一个无限的序列! - 当可能时,通常效率低下.
最初,Clojure中的懒惰序列在需要时逐项评估.在Clojure 1.1中添加了分块序列以提高性能.而不是逐项评估,一次评估32个元素的"块".这减少了懒惰评估产生的开销.此外,它允许clojure利用底层数据结构.例如,PersistentVector实现为32个元素数组的树.这意味着要访问元素,必须遍历树,直到找到相应的数组.使用分块序列,一次抓取整个阵列.这意味着在需要重新遍历树之前,可以检索32个元素中的每一个.
已经讨论过在需要完全懒惰的情况下提供强制逐项评估的方法.但是,我认为它还没有添加到该语言中.
为什么你可以在延迟序列中包装递归调用,并且不再为大型计算获得堆栈溢出？
你有一个你的意思的例子吗？如果你有一个与lazy-seq的递归绑定,它肯定会导致堆栈溢出.