并行集合中scala折叠的行为

Question

让我们多次运行以下代码行:

Set(1,2,3,4,5,6,7).par.fold(0)(_ - _)

结果非常有趣:

scala> Set(1,2,3,4,5,6,7).par.fold(0)(_ - _)
res10: Int = 8
scala> Set(1,2,3,4,5,6,7).par.fold(0)(_ - _)
res11: Int = 20

但显然它应该像顺序版本一样:

scala> Set(1,2,3,4,5,6,7).fold(0)(_ - _)
res15: Int = -28

我理解操作-对整数是非关联的,这就是这种行为背后的原因,但我的问题很简单:它不是意味着fold不应该在.par集合的实现中并行化吗？

Answer 1

当您查看标准库文档时,您会发现这fold是不确定的:

使用指定的关联二元运算符折叠此序列的元素.对元素执行操作的顺序是未指定的,并且可能是不确定的.

作为替代方案,有foldLeft:

将二元运算符应用于起始值以及此序列的所有元素,从左到右.将二元运算符应用于起始值以及此集合或迭代器的所有元素,从左到右.

注意:可能会为不同的运行返回不同的结果,除非基础集合类型是有序的或运算符是关联的和可交换的.

由于Set不是一个有序的集合,没有规范的顺序可以折叠元素,所以标准库允许自己甚至是不确定的foldLeft.如果您在这里使用有序序列,foldLeft那么在这种情况下将是确定性的.