29

我喜欢 Clojure。该语言困扰我的一件事是我不知道惰性序列是如何实现的，或者它们是如何工作的。

我知道惰性序列只评估序列中被要求的项目。它是如何做到的？

  • 是什么让惰性序列如此高效以至于它们不会消耗太多堆栈？
  • 为什么你可以将递归调用包装在一个惰性序列中，而不再让堆栈溢出来进行大型计算？
  • 惰性序列会消耗哪些资源来完成它的工作？
  • 在什么情况下惰性序列效率低下？
  • 在什么情况下惰性序列最有效？
4

3 回答 3

32

我们开工吧。

•我知道惰性序列只评估序列中被请求的项目，它是如何做到的？

惰性序列（以下称为 LS，因为我是 LP，或惰性人）由部分组成。从 Clojure 1.1 开始，我认为是 1.2的头部，或部分（s，实际上是一次评估 32 个元素），之后是一个叫做thunk的东西，它基本上是一个块等待被调用的信息（将其视为创建序列的函数的其余部分，未评估）。当它被调用时，无论要求多少，thunk 都会评估，并创建一个新的 thunk，并根据需要使用上下文（已经调用了多少，因此它可以从以前的位置恢复）。

所以你(take 10 (whole-numbers))- 假设whole-numbers是一个懒惰的整数序列。这意味着您要强制对 thunk 进行 10 次评估（尽管在内部这可能会有所不同，具体取决于优化。

•是什么让惰性序列如此高效以至于它们不会消耗太多堆栈？

一旦您阅读了先前的答案（我希望），这就会变得更加清楚：除非您特别要求某些东西，否则不会对任何内容进行评估。当您调用某些东西时，可以单独评估序列中的每个元素，然后将其丢弃。

如果序列不是惰性的，通常它会抓住它的头部，这会消耗堆空间。如果它是惰性的，则计算它，然后丢弃它，因为后续计算不需要它。

•为什么您可以将递归调用包装在一个惰性序列中，而不再让堆栈溢出以进行大型计算？

请参阅上一个答案并考虑：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 周期。他们只是不会不断地敲打堆栈，并用获取序列元素所需的计算结果来填充它。

• 在什么情况下惰性序列效率低下？

当您使用计算速度快且不会大量使用的小型序列时，将其设为 LS 效率低下，因为它需要创建另外几个字符。

严肃地说，除非你试图让一些东西表现得非常出色，否则 LS 是要走的路。

• 在什么情况下惰性序列最有效？

当您处理巨大的 seq 并且您只使用它们的零碎部分时，那就是您从使用它们中获得最大收益的时候。

确实，在方便、易于理解（一旦你掌握了它们）、对代码的推理和速度方面，使用 LS 总是比非 LS 更好。

于 2010-07-14T14:55:34.663 回答
16

我知道惰性序列只评估序列中被要求的项目，它是如何做到的？

我认为之前发布的答案已经很好地解释了这部分。我只会补充一点，惰性序列的“强制”是隐含的——没有括号！:-) -- 函数调用；也许这种思考方式会让一些事情变得更清楚。另请注意，强制延迟序列涉及隐藏的突变——被强制的 thunk 需要产生一个值，将其存储在缓存中（突变！）并丢弃其不再需要的可执行代码（再次突变！） .

我知道惰性序列只评估序列中被要求的项目，它是如何做到的？

是什么让惰性序列如此高效以至于它们不会消耗太多堆栈？

惰性序列会消耗哪些资源来完成它的工作？

它们不消耗堆栈，因为它们消耗的是堆。惰性序列是一种存在于堆上的数据结构，其中包含一小部分可执行代码，如果需要，可以调用这些代码来生成更多数据结构。

为什么你可以将递归调用包装在一个惰性序列中，而不再让堆栈溢出来进行大型计算？

首先，正如 dbyrne 所提到的，如果 thunk 本身需要执行具有非常深嵌套的调用结构的代码，则在使用惰性序列时您可以很好地获得 SO。

但是，在某种意义上，您可以使用惰性序列来代替尾递归，并且在这对您有用的程度上，您可以说它们有助于避免 SO。事实上，更重要的是，产生惰性序列的函数不应该是尾递归的；惰性 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

分块（由 dbyrne 提到）稍微改变了这幅画，因为每一步都会产生更多的元素，但原理保持不变：当惰性序列的相应元素产生时，每一步都会占用一些堆栈，然后该堆栈在更多强制发生之前被回收。

在什么情况下惰性序列效率低下？

在什么情况下惰性序列最有效？

如果您无论如何都需要一次握住整个东西，那么懒惰是没有意义的。惰性序列在未分块时在每一步进行堆分配，或者在分块时在每个块（每 32 步一次）进行堆分配；在某些情况下，避免这种情况可以为您带来性能提升。

但是，惰性序列启用了数据处理的流水线模式：

(->> (lazy-seq-producer)               ; possibly (->> (range)
     (a-lazy-seq-transformer-function) ;               (filter even?)
     (another-transformer-function))   ;               (map inc))

无论如何，以严格的方式执行此操作会分配大量堆，因为您必须保留中间结果才能将它们传递到下一个处理阶段。此外，您需要保留整个内容，这在(range)无限序列的情况下实际上是不可能的！——如果可能的话，它通常是低效的。

于 2010-07-14T17:13:29.980 回答
8

最初，Clojure 中的惰性序列是根据需要逐项评估的。Clojure 1.1 中添加了块序列以提高性能。不是逐项评估，而是一次评估 32 个元素的“块”。这减少了惰性求值带来的开销。此外，它还允许 clojure 利用底层数据结构。例如，PersistentVector实现为 32 个元素数组的树。这意味着要访问一个元素，您必须遍历树，直到找到合适的数组。使用分块序列，一次抓取整个数组。这意味着可以在需要重新遍历树之前检索 32 个元素中的每一个。

已经讨论过在需要完全惰性的情况下提供一种强制逐项评估的方法。但是，我认为它尚未添加到语言中。

为什么你可以将递归调用包装在一个惰性序列中，而不再让堆栈溢出来进行大型计算？

你有一个例子说明你的意思吗？如果你有一个到惰性序列的递归绑定，它肯定会导致堆栈溢出。

于 2010-07-14T14:37:33.980 回答