Clojure 中如何实现惰性序列? [英] How Are Lazy Sequences Implemented in Clojure?

问题描述

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

I like Clojure. One thing that bothers me about the language is that I don't know how lazy sequences are implemented, or how they work.

我知道惰性序列只评估序列中要求的项目.它是如何做到这一点的?

I know that lazy sequences only evaluate the items in the sequence that are asked for. How does it do this?

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

推荐答案

让我们这样做.

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

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

Lazy sequences (henceforth LS, because I am a LP, or Lazy Person) are composed of parts. The head, or the part(s, as really 32 elements are evaluated at a time, as of Clojure 1.1, and I think 1.2) of the sequence that have been evaluated, is followed by something called a thunk, which is basically a chunk of information (think of it as the rest of the your function that creates the sequence, unevaluated) waiting to be called. When it is called, the thunk evaluates however much is asked of it, and a new thunk is created, with context as necessary (how much has been called already, so it can resume from where it was before).

所以你 (take 10 (whole-numbers)) – 假设 whole-numbers 是一个惰性整数序列.这意味着您要强制对 thunk 进行 10 次评估(尽管在内部这可能会因优化而有所不同.

So you (take 10 (whole-numbers)) – assume whole-numbers is a lazy sequence of whole numbers. That means you're forcing evaluation of thunks 10 times (though internally this may be a little difference depending on optimizations.

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

一旦您阅读了之前的答案(我希望)，这就会变得更加清晰:除非您特别要求某些东西，否则不会评估任何内容.当您调用某些东西时，序列中的每个元素都可以单独评估，然后丢弃.

This becomes clearer once you read the previous answer (I hope): unless you call for something in particular, nothing is evaluated. When you call for something, each element of the sequence can be evaluated individually, then discarded.

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

If the sequence is not lazy, oftentimes it is holding onto its head, which consumes heap space. If it is lazy, it is computed, then discarded, as it is not required for subsequent computations.

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

请参阅上一个答案并考虑:lazy-seq 宏 (来自文档) 将

See the previous answer and consider: the lazy-seq macro (from the documentation) will

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:

Check out the filter function for a cool LS that uses recursion:

(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 周期.他们只是不会不断地敲打堆栈，并用获取序列元素所需的计算结果来填充它.

I'm not quite sure what you're asking here. LSs require memory and CPU cycles. They just don't keep banging the stack, and filling it up with results of the computations required to get the sequence elements.

• 惰性序列在哪些情况下效率低下?

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

When you're using small seqs that are fast to compute and won't be used much, making it an LS is inefficient because it requires another couple chars to create.

严肃地说，除非您想使某些东西极其具有高性能，否则 LS 是可行的方法.

In all seriousness, unless you're trying to make something extremely performant, LSs are the way to go.

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

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

When you're dealing with seqs that are huge and you're only using bits and pieces of them, that is when you get the most benefit from using them.

实际上，在方便性、易于理解(一旦掌握了它们)以及对代码的推理和速度方面，使用 LS 比使用非 LS 总是要好得多.

Really, it's pretty much always better to use LSs over non-LSs, in terms of convenience, ease of understanding (once you get the hang of them) and reasoning about your code, and speed.

这篇关于Clojure 中如何实现惰性序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！