折和减重之间的区别 [英] Difference between fold and reduce revisted

问题描述

我一直在阅读 /25158780/7337271>功能编程(尤其是Scala和Scala API)中reduce和foldLeft/fold之间的区别?由提供samthebest ，我不确定我是否了解所有细节:

I've been reading a nice answer to Difference between reduce and foldLeft/fold in functional programming (particularly Scala and Scala APIs)? provided by samthebest and I am not sure if I understand all the details:

• 根据答案(reduce与foldLeft):

一个很大的不同(...)是reduce应该被赋予一个可交换的等分线(...)

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

这种区别对于大数据/MPP/分布式计算非常重要，而减少的全部原因甚至存在.

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

和

Reduce正式定义为MapReduce范例的一部分

Reduce is defined formally as part of the MapReduce paradigm,

我不确定这两个语句如何结合.谁能对此有所启示?

I am not sure how this two statements combine. Can anyone put some light on that?

我测试了不同的集合，但没有看到reduce和foldLeft之间的性能差异.看来ParSeq是特例，对吗?

I tested different collections and I haven't seen performance difference between reduce and foldLeft. It looks like ParSeq is a special case, is that right?

我们真的需要命令来定义fold吗?

Do we really need order to define fold?

我们无法定义折叠，因为大块没有排序，折叠只需要关联性，而不是可交换性.

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

为什么不能将其概括为无序集合?

Why it couldn't be generalized to unordered collection?

推荐答案

如注释中所述，术语 reduce 在MapReduce的上下文中使用和在MapReduce的上下文中使用时含义不同.功能编程.

As mentioned in the comments, the term reduce means different thing when used in the context of MapReduce and when used in the context of functional programming.

• 在MapReduce中，系统通过给定键将map函数的结果分组，然后调用reduce操作以汇总每个组的值(因此，每个组一次调用reduce) .您可以将其视为函数(K, [V]) -> R，它使用组键K以及属于组[V]的所有值并产生一些结果.

• In MapReduce, the system groups the results of the map function by a given key and then calls the reduce operation to aggregate values for each group (so reduce is called once for each group). You can see it as a function (K, [V]) -> R taking the group key K together with all the values belonging to the group [V] and producing some result.

在函数式编程中，reduce是一个函数，当您给某个集合提供可以合并两个元素的操作时，该函数将集合某些集合的元素.换句话说，您定义一个函数(V, V) -> V，而reduce函数使用该函数将集合[V]聚合为单个值V.

In functional programming, reduce is a function that aggregates elements of some collection when you give it an operation that can combine two elements. In other words, you define a function (V, V) -> V and the reduce function uses it to aggregate a collection [V] into a single value V.

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

When you want to add numbers [1,2,3,4] using + as the function, the reduce function can do it in a number of ways:

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

1. It can run from the start and calculate ((1+2)+3)+4)
2. It can also calculate a = 1+2 and b = 3+4 in parallel and then add a+b!

根据定义，foldLeft操作始终从左开始，因此始终使用(1)的评估策略.实际上，它也需要一个初始值，因此它的计算结果更像(((0+1)+2)+3)+4).这使foldLeft对于顺序很重要的操作很有用，但是这也意味着它不能用于无序集合(因为您不知道左"是什么).

The foldLeft operation is, by definition always proceeding from the left and so it always uses the evaluation strategy of (1). In fact, it also takes an initial value, so it evaluates something more like (((0+1)+2)+3)+4). This makes foldLeft useful for operations where the order matters, but it also means that it cannot be implemented for unordered collections (because you do not know what "left" is).

这篇关于折和减重之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！