什么是 Clojure 中的可折叠集合？

Question

我是 Clojure 的初学者，在尝试阅读Reducers 时，我发现了一个叫做foldable collection 的东西。

他们提到矢量和地图是可折叠的集合，但不是列表。

我想了解什么是可折叠收藏，为什么矢量和地图是可折叠的？

我还没有找到可折叠收藏的任何定义或解释。

Answer 1

答案在文档中，如果不是很清楚的话：

此外，一些集合（持久向量和映射）是可折叠的。reducer 上的折叠操作并行执行减少...

这个想法是，使用现代硬件，可以并行完成像对向量的所有元素求和这样的“归约”操作。例如，如果对 400K 长度向量的所有元素求和，我们可以将它们分成 4 组，每组 100K 块，并行求和，然后将 4 个小计合并为最终答案。这将比仅使用单线程（单 CPU 内核）快大约 4 倍。

Reducers 存在于clojure.core.reducers命名空间中。假设我们定义别名，如：

( ns demo.xyz
  (:require [clojure.core :as core]
            [clojure.core.reducers :as r] ))

与 相比clojure.core，我们有：

core/reduce   <=>   r/fold     ; new  name for `reduce`
core/map      <=>   r/map      ; same name for `map`
core/filter   <=>   r/filter   ; same name for `filter`

所以，命名并不是最好的。 reduce住在clojure.core命名空间中，但没有reduce在clojure.core.reducers命名空间。相反，有一个名为foldin的类似工作的函数clojure.core.reducers。

请注意，fold与我们的求和示例一样，这是用于组合数据列表的历史名称。 有关更多信息，请参阅维基百科条目。

因为折叠以非线性顺序访问数据（这对于链表非常低效），所以折叠只值得在随机访问数据结构（如向量）上进行）。

更新#1：

说了以上，请记住“过早优化是万恶之源”这句格言。以下是(vec (range 1e7))8 核机器上 的一些测量值，即 10M 条目：

(time (reduce + data))

"Elapsed time: 284.52735 msecs"
"Elapsed time: 119.310289 msecs"
"Elapsed time: 98.740421 msecs"
"Elapsed time: 100.58998 msecs"
"Elapsed time: 98.642878 msecs"
"Elapsed time: 105.021808 msecs"
"Elapsed time: 99.886083 msecs"
"Elapsed time: 98.49152 msecs"
"Elapsed time: 99.879767 msecs"

(time (r/fold + data))

"Elapsed time: 61.67537 msecs"
"Elapsed time: 56.811961 msecs"
"Elapsed time: 55.613058 msecs"
"Elapsed time: 58.359599 msecs"
"Elapsed time: 55.299767 msecs"
"Elapsed time: 62.989939 msecs"
"Elapsed time: 56.518486 msecs"
"Elapsed time: 54.218251 msecs"
"Elapsed time: 54.438623 msecs"

标准报告：

reduce   144 ms
r/fold    72 ms

更新 #2

Rich Hickey在 2014 Clojure Conj 上谈到了传感器/减速器的设计。您可能会发现这些详细信息很有用。基本思想是将折叠委托给每个集合类型，它使用其实现细节的知识来有效地执行折叠。

由于哈希映射在内部使用向量，因此它们可以有效地并行折叠。