我是 Clojure 的初学者,正在尝试阅读 Reducers我发现了一个叫做可折叠收藏的东西。
他们提到矢量和 map 是可折叠集合,但不是列表。
我试图了解什么是可折叠集合,为什么矢量和 map 是可折叠的?
我还没有找到可折叠集合的任何定义或解释。
最佳答案
答案就在文档中,尽管不是很清楚:
Additionally, some collections (persistent vectors and maps) are foldable. The fold operation on a reducer executes the reduction in parallel...
这个想法是,使用现代硬件,可以并行完成“归约”操作,例如对向量的所有元素求和。例如,如果对 400K 长度向量的所有元素求和,我们可以将它们分成 4 组 100K block ,并行求和,然后将 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
命名空间中,但 clojure.core.reducers
命名空间中没有 reduce
。相反,在 clojure.core.reducers
中有一个名为 fold
的类似工作函数。
请注意,fold
是一个历史名称,用于组合数据列表,就像我们的求和示例一样。 See the Wikipedia entry了解更多信息。
因为折叠以非线性顺序访问数据(这对于链表来说非常低效),所以折叠只值得在像向量这样的随机访问数据结构上进行。
<小时/>更新#1:
话虽如此,请记住这句格言:“过早的优化是万恶之源。”以下是 8 核机器上 (vec (range 1e7))
(即 10M 条目)的一些测量结果:
(时间(减少+数据))
"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"
(时间(r/折叠 + 数据))
"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 谈传感器/ reducer 的设计 at the 2014 Clojure Conj 。您可能会发现这些详细信息很有用。基本思想是,折叠被委托(delegate)给每个集合类型,它使用其实现细节的知识来有效地执行折叠。
由于 HashMap 在内部使用向量,因此它们可以有效地并行折叠。
关于clojure - Clojure 中的可折叠集合是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49031669/