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

Question

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

clojurereducers

4

我是Clojure的初学者，在阅读Reducers时发现了一些叫做可折叠集合的东西。

他们提到向量和映射是可折叠的集合，但列表不是。

我正在努力理解什么是可折叠集合，为什么向量和映射是可折叠的？

我没有找到任何关于可折叠集合的定义或解释。

- SANN3

1

一个技术上的答案是满足谓词 #(satisfies? r/CollFold %) 的任何值。不幸的是，这并不起作用，因为 r/CollFold 扩展到 Object，而任何值都是 Object... - glts

2个回答

1

有一场 Guy Steele 的演讲在 reducers 之前就出现了，可能是 reducers 的灵感来源。https://vimeo.com/6624203

- slipset

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alan Thompson · Accepted Answer

答案在文档中，尽管不是特别清晰：

此外，某些集合（持久化向量和映射）是可折叠的。Reducer上的Fold操作并行地执行减少操作…。

这个想法就是，随着现代硬件的发展，“减少”操作（例如对向量中所有元素求和）可以并行完成。例如，如果对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 命名空间中，但是在 clojure.core.reducers 命名空间中没有 reduce。相反，在 clojure.core.reducers 中有一个名为 fold 的类似函数。

请注意，fold 是将数据列表组合在一起的历史名称，就像我们的求和示例一样。有关更多信息，请参见维基百科条目。

由于折叠以非线性顺序访问数据（这对于链接列表非常低效），因此仅值得在像向量这样的随机访问数据结构上进行折叠。

更新＃1：

尽管如上所述，请记住谚语“过早优化是万恶之源”。下面是在 8 核机器上使用 (vec (range 1e7)) （即 1000 万个条目）的一些测量结果：

(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"

(时间 (r/fold + 数据))

"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上谈到了transducers/reducers设计问题，你可以在这个视频中找到有用的信息。基本思想是将折叠交给每个集合类型来执行，集合类型利用其实现细节的知识高效地执行折叠操作。

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