scala - Scala 聚合函数的示例

Question

我一直在寻找，但找不到 aggregate 的示例或讨论。我能理解的 Scala 函数。它似乎非常强大。

这个函数可以用来减少元组的值来制作多图类型的集合吗？例如:

val list = Seq(("one", "i"), ("two", "2"), ("two", "ii"), ("one", "1"), ("four", "iv"))

应用聚合后:

Seq(("one" -> Seq("i","1")), ("two" -> Seq("2", "ii")), ("four" -> Seq("iv"))

另外，你能举个参数 z的例子吗？ , segop , 和 combop ?我不清楚这些参数的作用。

Answer 1

聚合函数不这样做(除了它是一个非常通用的函数，它可以用来做到这一点)。你要groupBy .至少接近。当您从 Seq[(String, String)] 开始时，然后通过获取元组中的第一项进行分组(即 (String, String) => String) ，它将返回 Map[String, Seq[(String, String)] )。然后您必须丢弃 Seq[String, String)] 值中的第一个参数。

所以

list.groupBy(_._1).mapValues(_.map(_._2))

你会得到一个 Map[String, Seq[(String, String)] .如果你想要一个 Seq而不是 Map , 拨打 toSeq结果上。我不认为你对结果 Seq 中的顺序有保证

聚合是一个更难的函数。

首先考虑reduceLeft 和reduceRight。
让 as是一个非空序列 as = Seq(a1, ... an)类型的元素 A , 和 f: (A,A) => A以某种方式组合 A 类型的两个元素成一。我将把它记为一个二元运算符 @ , a1 @ a2而不是 f(a1, a2) . as.reduceLeft(@)将计算 (((a1 @ a2) @ a3)... @ an) . reduceRight将括号放在另一边， (a1 @ (a2 @... @ an)))) .如 @恰好是关联的，一个人不关心括号。可以将其计算为 (a1 @... @ ap) @ (ap+1 @...@an) (在 2 个大括号内也会有括号，但我们不要在意)。然后可以并行执行这两个部分，而 reduceLeft 或 reduceRight 中的嵌套括号强制执行完全顺序计算。但只有在 @ 时才可以并行计算已知是关联的，而 reduceLeft 方法无法知道这一点。

不过，可能还有方法 reduce ，其调用者将负责确保操作是关联的。然后 reduce会按照它认为合适的方式对调用进行排序，可能会并行执行。确实有这样的方法。

然而，各种reduce 方法都存在局限性。 Seq 的元素只能组合成相同类型的结果: @必须是 (A,A) => A .但是，将它们组合成 B 可能会有更普遍的问题。 .一个以值 b 开头类型 B ，并将其与序列的每个元素组合。运营商 @是 (B,A) => B ，然后计算 (((b @ a1) @ a2) ... @ an) . foldLeft这样做。 foldRight做同样的事情，但从 an 开始.在那里， @操作没有机会被关联。当一个人写 b @ a1 @ a2 ，它一定意味着 (b @ a1) @ a2 , 如 (a1 @ a2)将是错误的类型。所以 foldLeft 和 foldRight 必须是连续的。

然而，假设每个 A可以变成 B ，我们用 !来写吧, a!类型为 B .此外假设还有一个 +操作 (B,B) => B ，以及 @是这样的 b @ a实际上是 b + a! .与其将元素与 @ 结合，不如先用 ! 将它们全部转换为 B。 ，然后将它们与 + 结合起来.那将是 as.map(!).reduceLeft(+) .如果 +是关联的，那么可以用reduce来完成，而不是顺序的:as.map(!).reduce(+)。可能有一个假设的方法 as.associativeFold(b, !, +)。

聚合非常接近。然而，可能有一种更有效的方式来实现 b@a比 b+a!例如，如果输入 B是 List[A] ，而 b@a 是 a::b，那么 a!将是 a::Nil , 和 b1 + b2将是 b2 ::: b1 . a::b 比 (a::Nil):::b 好得多。从关联性中受益，但仍使用 @ , 第一个 split b + a1! + ... + an! , 进入 (b + a1! + ap!) + (ap+1! + ..+ an!) ，然后返回使用 @与 (b @ a1 @ an) + (ap+1! @ @ an) .一个仍然需要!在 ap+1 上，因为必须从某个 b 开始。 + 仍然是必要的，出现在括号之间。要做到这一点， as.associativeFold(!, +)可以改为 as.optimizedAssociativeFold(b, !, @, +) .

返回 + . +是关联的，或等效地， (B, +)是一个半群。实际上，编程中使用的大多数半群碰巧也是幺半群，即它们包含一个中性元素 z (对于零)在 B 中，因此对于每个 b , z + b = b + z = b .在这种情况下， !有意义的操作很可能是 a! = z @ a .此外，由于 z 是中性元素 b @ a1 ..@ an = (b + z) @ a1 @ an这是 b + (z + a1 @ an) .所以总是可以用 z 开始聚合。如 b想要代替，你做 b + result在末尾。有了所有这些假设，我们可以做一个 s.aggregate(z, @, +) .就是这样 aggregate做。 @是 seqop参数(应用于序列 z @ a1 @ a2 @ ap )和 +是 combop (适用于已经部分组合的结果，如 (z + a1@...@ap) + (z + ap+1@...@an) )。

总结一下， as.aggregate(z)(seqop, combop)计算与 as.foldLeft(z)( seqop) 相同的东西前提是

(B, combop, z)是幺半群

seqop(b,a) = combop(b, seqop(z,a))

聚合实现可以使用 combop 的关联性来根据需要对计算进行分组(但不交换元素，+ 不必是可交换的，::: 不是)。它可以并行运行它们。

最后，使用 aggregate 解决初始问题留给读者作为练习。提示:使用 foldLeft 实现，然后找到 z和 combo这将满足上述条件。