mapreduce - 重温折叠和减少之间的区别

Question

我一直在读nice answer至Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)?由samthebest提供我不确定我是否理解所有细节:

• 根据答案(reduce 与 foldLeft):

  A big big difference (...) is that reduce should be given a commutative monoid, (...)

  This distinction is very important for Big Data / MPP / distributed computing, and the entire reason why reduce even exists.

  和

  Reduce is defined formally as part of the MapReduce paradigm,

  我不确定这两个陈述如何结合起来。谁能解释一下吗？

• 我测试了不同的集合，但没有发现 reduce 和 foldLeft 之间的性能差异。看起来 ParSeq 是一个特例，是吗？

• 我们真的需要顺序来定义fold吗？

  we cannot define fold because chunks do not have an ordering and fold only requires associativity, not commutativity.

  为什么它不能推广到无序集合？

Answer 1

正如评论中提到的，术语reduce在MapReduce上下文中使用时和在函数式编程上下文中使用时意味着不同的东西。

• 在 MapReduce 中，系统按给定键对 map 函数的结果进行分组，然后调用 reduce 操作来聚合每个组的值(因此每个组都会调用一次reduce)。您可以将其视为一个函数 (K, [V]) -> R，采用组键 K 以及属于组 [V 的所有值] 并产生一些结果。

• 在函数式编程中，reduce 是一种函数，当您为其提供可组合两个元素的操作时，该函数会聚合某个集合的元素。换句话说，您定义一个函数 (V, V) -> V，reduce 函数使用它来聚合集合 [V]转换成单个值V。

当你想使用+作为函数来添加数字[1,2,3,4]时，reduce函数可以做到它可以通过多种方式实现:

1. 它可以从头开始运行并计算((1+2)+3)+4)
2. 它还可以并行计算a = 1+2和b = 3+4，然后添加a+b!<

根据定义，foldLeft 操作始终从左侧进行，因此它始终使用 (1) 的求值策略。事实上，它也需要一个初始值，因此它的计算结果更像是 (((0+1)+2)+3)+4)。这使得 foldLeft 对于顺序很重要的操作非常有用，但这也意味着它无法用于无序集合(因为您不知道“left”是什么)。