为什么Clojure的core.reducers比lazy collection函数更快

Question

在许多关于Reducers的资源中（例如Rich Hickey的经典博客文章），声称Reducers比常规集合函数（(map ... (filter ...))等）更快，因为减少了开销。

避免的额外开销是什么？如果我理解正确，即使是惰性集合函数最终也会遍历原始序列一次。差异在于如何计算中间结果吗？

指向Clojure实现中有助于理解差异的相关位置的指针也将非常有帮助。

- zlatanski

Answer 1

我认为一个关键的洞见在于以下来自原博客文章的段落：

(require '[clojure.core.reducers :as r])
(reduce + (r/filter even? (r/map inc [1 1 1 2])))
;=> 6

That should look familiar - it's the same named functions, applied in the same order, with the same arguments, producing the same result as the Clojure's seq-based fns. The difference is that, reduce being eager, and these reducers fns being out of the seq game, there's no per-step allocation overhead, so it's faster. Laziness is great when you need it, but when you don't you shouldn't have to pay for it.

实现惰性序列的过程中会带来（线性）分配成本：每次实现惰性序列的另一个元素时，该序列的剩余部分都存储在一个新的thunk中，并且这种“thunk”的表示形式是新的clojure.lang.LazySeq对象。

我认为这些LazySeq对象是引用中提到的分配开销。使用reducers时，没有惰性序列元素的逐步实现，因此根本不需要实例化LazySeq thunk。

- glts

---

谢谢 - 这个回答对我来说听上去更正确。另一个回答暗示整个序列在每一步之间都被实现了，这不可能是真的。这种分配成本是我理解得更有意义的，也是我们不想要承担的成本，这就是为什么reducers更快的原因。 - zlatanski

我想你可以这样阅读第一个答案……我认为这可能是一种无意识的阅读方式，但如果它强烈地向你暗示，那么当然会误导你。惰性序列处理一次处理一个元素或一个块（最多32个元素的块），只有在需要时才会实现新的元素或块。我认为原始答案试图表达的正确观点是，当您堆叠惰性序列转换时，每个层需要为其分配自己的惰性序列对象，每个元素或块都有一个“单元格”（尽管它们将被惰性地实现）。 - Michał Marczyk

@MichałMarczyk：第一个答案说：“当你结合像map、filter这样的操作时，这些函数会迭代一个集合并返回一个新的集合，然后将其传递给下一个函数”，听起来明显是错误的。nha在评论中一直为这个观点辩护，所以我放弃了争论。后来似乎他/她修补了答案，使其更加通用。 - zlatanski

它们实际上都返回一个新的集合，只是这些集合是惰性序列对象，因此它们以未实现的形式进入生活，并且仅在从“最外层”的惰性序列对象中提取元素时才从“外部向内部”实现。 - Michał Marczyk

不可否认，你引用的那句话可能会让人觉得map等函数是对它们的输入进行迭代然后再返回一个新集合，但事实并非如此——它们立即返回新集合，并在其中嵌入了迭代逻辑（在请求实际元素时调用）。 - Michał Marczyk