scala – 聚合概括折叠和折叠概括如何减少？

首先,请注意,如果您的集合是无序的,那么它上面的任何一组(二进制)操作都需要是可交换的和关联的,或者您将根据每次选择的(任意)顺序得到不同的答案.由于reduce,fold和aggregate都使用二进制操作,如果在无序(或被视为无序)的集合上使用这些东西,则所有内容都必须是可交换的和关联的.

reduce是一个实现的想法,如果你可以把两件事情变成一件事,你可以将任意长的集合折叠成一个元素.只要你最终将它们全部配对并保持从左到右的顺序不变,那么关联性就是你无论如何配对都无关紧要的属性,这正是你所需要的.

a   b   c   d          a   b   c   d           a   b   c   d
a # b   c   d          a # b   c   d           a   b # c   d
(a#b)   c # d          (a#b) # c   d           a   (b#c)   d
(a#b) # (c#d)          ((a#b)#c) # d           a # ((b#c)#d)

只要操作(此处称为#)是关联的,上述所有内容都是相同的.没有理由交换左边的东西和右边的东西,所以操作不需要是可交换的(另外是：a b == b a; concat不是：ab！= ba).

reduce在数学上很简单,只需要一个关联操作

但是,Reduce是有限的,因为它不适用于空集合,并且您无法更改类型.如果你按顺序工作,你可以使用一个新类型和旧类型的函数,并生成一个新类型的函数.这是一个连续的折叠(如果新类型在左侧,则向左折叠,如果在右侧则向右折叠).关于这里的操作顺序是没有选择的,所以交换性和关联性以及一切都是无关紧要的.只有一种方法可以按顺序处理列表. (如果你希望你的左折和右折总是相同的,那么操作必须是关联的和可交换的,但由于左右折叠通常不会被意外交换,这对于确保.)

当你想并行工作时,问题就出现了.你不能顺序完成你的收藏;根据定义,这不是平行的！所以你必须在多个地方插入新类型！让我们调用我们的折叠操作@,我们会说新类型在左边.此外,我们会说我们总是以相同的元素Z开头.现在我们可以做以下任何一个(以及更多)：

a     b     c     d        a     b     c     d         a     b     c     d
 Z@a    b     c     d       Z@a    b    Z@c    d        Z@a   Z@b   Z@c   Z@d
(Z@a) @ b     c     d      (Z@a) @ b   (Z@c) @ d
((Z@a)@b)  @  c     d
(((Z@a)@b)@c)    @  d

现在我们收集了一种或多种新类型的东西. (如果原始集合是空的,我们只需要Z.)我们知道如何处理它！降低！所以我们为我们的新类型做一个reduce操作(让我们称之为$,并记住它必须是关联的),然后我们有聚合：

a     b     c     d        a     b     c     d         a     b     c     d
 Z@a    b     c     d       Z@a    b    Z@c    d        Z@a   Z@b   Z@c   Z@d
(Z@a) @ b     c     d      (Z@a) @ b   (Z@c) @ d        Z@a $Z@b   Z@c $Z@d
((Z@a)@b)  @  c     d      ((Z@a)@b) $((Z@c)@d)    ((Z@a)$(Z@b)) $((Z@c)$(Z@d))
(((Z@a)@b)@c)    @  d

现在,这些东西看起来都很不一样.我们怎样才能确保它们最终成为一样？没有一个概念可以描述这个,但是Z @操作必须是零的,并且$和@必须是同态的,因为我们需要(Z @ a)@b ==(Z @ a)$(Z @b).这就是你需要的实际关系(它在技术上与半群同态非常相似).即使一切都是联想和可交换的,也有各种各样的方式来挑选.例如,如果Z是双精度值0.0且实际上是@,那么Z是零,而@是关联和可交换的.但如果$实际上是*,也是联想和可交换的,那么一切都会出错：

(0.0+2) * (0.0+3) == 2.0 * 3.0 == 6.0
((0.0+2) + 3)     == 2.0 + 3   == 5.0

非trival聚合的一个示例是构建集合,其中@是“追加元素”运算符,$是“concat two collections”操作.

聚合是棘手的,需要一个关联的reduce操作,加上一个类似零的值和一个与reduce同态的折叠式操作

底线是聚合不仅仅是减少的概括.

但如果您实际上没有更改类型,则会有一种简化(不太通用的形式).如果Z实际上是z并且是实际零,我们可以将它粘贴在我们想要的任何地方并使用reduce.同样,我们在概念上不需要交换;我们只是坚持一个或多个z并减少,我们的@和$操作可以是同一个东西,即我们在减少时使用的原始#

a   b   c   d             () <- empty
 z#a z#b                    z
 z#a (z#b)#c
 z#a ((z#b)#c)#d
(z#a)#((z#b)#c)#d

如果我们只是从这里删除z,它可以很好地工作,实际上相当于if(empty)z else reduce.但它还有另一种方式可行.如果操作#也是可交换的,并且z实际上不是零,而只是占据#的固定点(意思是z#z == z但是z#a不一定只是a),那么你可以运行相同的东西,并且由于传感器允许您切换顺序,因此您可以在概念上将所有z重新排序在一起,然后将它们全部合并在一起.

这是一个平行的折叠,实际上是一个相当不同的野兽而不是顺序折叠.

(请注意,折叠和聚合都不是对reduce的严格概括,即使对于无序集合,其中操作必须是关联的和可交换的,因为一些操作没有合理的零！例如,以最短的长度减少字符串具有其“零”最长的字符串,在概念上不存在,实际上是一种荒谬的记忆浪费.)

fold需要一个关联的reduce操作加上一个零值或一个可交换的reduce操作加一个定点值

现在,你何时会使用不仅仅是reduceOrElse(零)的平行折叠？实际上,从来没有,尽管它们可以存在.例如,如果你有一个戒指,你通常会有我们需要的固定点.例如,10％45 ==(10 * 10)％45,并且*在整数mod 45中是关联的和可交换的.因此,如果我们的集合是数字mod 45,我们可以折叠为“零”10和*的操作,并且我们请尽可能并行化,同时仍然得到相同的结果.很奇怪.

但是,您可以将零点和折叠操作插入到聚合中并获得完全相同的结果,因此聚合是折叠的正确概括.

所以,底线：

> Reduce只需要关联合并操作,但不会更改类型,也不适用于空集合.
>并行折叠尝试扩展reduce,但需要一个真零或一个固定点,并且合并操作必须是可交换的.
> Aggregate通过(概念上)运行顺序折叠然后(并行)reduce来改变类型,但是reduce操作和fold操作之间存在复杂的关系 – 基本上它们必须做“相同的事情”.
>无序集合(例如集合)总是需要对上述任何一个进行关联和交换操作.

关于byKey的东西：它与此相同,只是它只将它应用于与(可能重复的)键相关的值集合.

如果Spark实际上需要交换性,而上述分析并不表明需要它,那么可以合理地考虑一个错误(或者至少是对实现的不必要限制,因为map和filter等操作会保留有序RDD上的顺序).