scala - 聚集泛化和折叠泛化如何减少？

Question

据我了解，aggregate是fold的泛化，而这又是reduce的泛化。

类似地，combineByKey是aggregateByKey的泛化，而这又是foldByKey的泛化，而这又是reduceByKey的泛化。

但是，我很难为这七个方法中的每一个找到简单的示例，而这些示例只能由它们表示，而不能由它们的通用性较低的版本表示。例如，我发现http://blog.madhukaraphatak.com/spark-rdd-fold/给出了fold的示例，但是我也能够在相同的情况下使用reduce。

到目前为止，我发现了什么：


我读到，更通用的方法可能更有效，但这是一项非功能性的要求，我想举一些无法用更具体的方法实现的示例。
我也读过传递给fold的函数只必须是关联的，而reduce的那个函数还必须是可交换的：https://stackoverflow.com/a/25158790/4533188（但是，我仍然不知道任何简单的示例。）而在https://stackoverflow.com/a/26635928/4533188中，阅读该折叠需要两个属性才能保持...
我们可以将零值视为一种功能（例如，对于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。）我们知道该怎么做！减少！因此，我们对新类型进行了归约运算（我们将其称为$，并记住它必须是关联的），然后进行聚合：

  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

非平凡聚合的一个示例是构建集合，其中@是“追加元素”运算符，而$是“ concat两个集合”运算。

aggregate非常棘手，需要关联的reduce操作，加上零值和与redho同构的fold-like操作

底线是aggregate不仅仅是reduce的概括。

但是，如果您实际上没有更改类型，则可以进行简化（简化形式）。如果Z实际上是z并且是实际零，则可以将其粘贴在所需的任何位置并使用reduce。同样，我们从概念上讲不需要交换性。我们只是坚持使用一个或多个z并进行归约，而我们的@和$操作可以是同一件事，即我们在reduce上使用的原始#

  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一起重新排序，然后将它们全部合并在一起。

这是平行折叠，实际上是与连续折叠完全不同的野兽。

（请注意，即使对于必须将操作进行关联和可交换的无序集合，fold和aggregate都不是reduce的严格概括，因为某些操作没有一个合理的零！例如，将字符串缩短为最短长度具有作为其“零”，是最长的字符串，从概念上讲是不存在的，实际上是对内存的荒唐浪费。）

fold需要关联的归约运算加上零值或可交换的归约运算加上定点值

现在，您何时会使用不只是reduceOrElse（zero）的平行折叠？尽管它们可以存在，但实际上可能永远不会。例如，如果您有一个圆环，那么您通常会得到我们需要的固定点类型。例如，10％45 ==（10 * 10）％45，并且*在整数mod 45中既是关联的又是可交换的。因此，如果我们的集合是数字mod 45，则可以用<零的< cc>和10的运算，并并行化，但是我们仍然得到相同的结果。很奇怪

但是，请注意，您可以将*的零和运算插入fold并获得完全相同的结果，因此aggregate是aggregate的适当概括。

因此，底线是：


Reduce只需要关联的合并操作，但不更改类型，并且不适用于空的colleciton。
平行折叠尝试扩展fold，但需要为零或固定点，并且合并操作必须是可交换的。
聚合通过（按概念）运行顺序折叠然后进行（并行）缩小来更改类型，但是在reduce操作和fold操作之间存在复杂的关系-基本上，它们必须做“同一件事”。
对于任何上述情况，无序集合（例如集合）始终需要关联和可交换操作。


关于reduce内容：与此相同，只是它仅将其应用于与（可能重复的）键关联的值的集合。

如果Spark实际上需要交换性，而上述分析并未表明需要交换性，则可以合理地考虑一个bug（或者至少是对实现的不必要限制，因为byKey和map这样的操作会保留有序RDD的顺序） 。