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

Question

据我所知aggregate,fold这是一种概括,反过来又是一种概括reduce.

类似地combineByKey,aggregateByKey这是一种概括,其反过来又是概括,foldByKey而反过来又是概括reduceByKey.

但是,我很难找到这七种方法中的每种方法的简单例子,而这些方法又可以仅由它们表达,而不是它们不那么通用的版本.例如,我找到了http://blog.madhukaraphatak.com/spark-rdd-fold/给出一个例子fold,但我也能够reduce在相同的情况下使用.

到目前为止我发现了什么:

• 我读到更通用的方法可以更有效,但这将是一个非功能性的要求,我想得到无法用更具体的方法实现的示例.
• 我也读了如传递给函数fold只要是关联的,而一个reduce必须是可交换另外:/sf/answers/1761115331/(不过,我还是不知道有什么好的简单例如.)在/sf/answers/1864514991/中,我读到折叠需要两个属性才能保持...
• 我们可以将零值视为一个特征(例如fold结束reduce),如"添加所有元素并添加3"并使用3作为零值,但这会产生误导,因为每个分区都会添加3个,而不仅仅是一旦.此外,fold根据我的理解,这根本不是目的- 它不是一个特征,而是实现它以便能够采用非交换函数的必要性.

这七种方法的简单例子是什么？

Answer 1

让我们通过逻辑上的实际需要来解决问题.

首先,请注意,如果您的集合是无序的,那么它上面的任何一组(二进制)操作都需要是可交换的和关联的,或者您将根据每次选择的(任意)顺序得到不同的答案.因为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是double值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"操作.

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

底线是,aggregate不是简单的概括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从这里删除's,它的效果非常好,实际上相当于if (empty) z else reduce.但它还有另一种方式可行.如果操作#也是可交换的,并且 z实际上不是零,而只是占据固定点#(意味着z#z == z但z#a不一定只是a),那么你可以运行相同的东西,并且由于通信可以让你切换顺序,你在概念上可以在开头将所有z重新排序,然后将它们合并在一起.

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

(注意,即使对于无序集合,操作必须是关联和可交换的,fold也不aggregate是严格概括reduce,因为某些操作没有合理的零!例如,以最短的长度减少字符串将"零"作为最长的字符串从概念上讲不存在,实际上是对记忆的荒谬浪费.)

fold需要的缔合减少操作加上任一零值或一减少操作这是可交换加一个定点值

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

但是,请注意,您可以将零和操作fold插入aggregate并获得完全相同的结果,因此aggregate 是一个适当的泛化fold.

所以,底线:

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

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

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