java - Stream reduce() 要求到底包含什么？

Question

在并行流上使用 reduce() 操作时，the OCP exam book说明 reduce() 参数必须遵守某些原则。这些原则如下:

1. The identity must be defined such that for all elements in the stream u, combiner.apply(identity, u) is equal to u.
2. The accumulator operator op must be associative and stateless such that (a op b) op c is equal to a op (b op c).
3. The combiner operator must also be associative and stateless and compatible with the identity, such that for all of u and t combiner.apply(u, accumulator.apply(identity, t)) is equal to accumulator.apply(u,t) .

书中给出了两个例子来说明这些原理，请看下面的代码:

关联示例:

System.out.println(
        Arrays.asList(1, 2, 3, 4, 5, 6)
                .parallelStream()
                .reduce(0, (a, b) -> (a - b)));

这本书是怎么说的:

It may output -21, 3, or some other value as the accumulator function violates the associativity property.

身份要求示例:

System.out.println(
        Arrays.asList("w", "o", "l", "f")
                .parallelStream()
                .reduce("X", String::concat));

这本书是怎么说的:

You can see other problems if we use an identity parameter that is not truly an identity value. It can output XwXoXlXf. As part of the parallel process, the identity is applied to multiple elements in the stream, resulting in very unexpected data.

我不明白那些例子。在累加器示例中，累加器以 0 - 1 开始，即 -1，然后是 -1 - 2，即 -3，然后 -6 等一直到 -21。我明白，因为生成的 arraylist 不同步，结果可能由于竞争条件等的可能性而无法预测，但为什么累加器不是关联的？ (a+b) 不会导致不可预测的结果吗？我真的不明白示例中使用的累加器有什么问题以及为什么它不是关联的，但话又说回来我仍然不完全理解“关联原则”的含义。

我也不明白身份示例。我知道如果 4 个单独的线程同时开始累积身份，结果确实可能是 XwXoXlXf，但这与身份参数本身有什么关系？到底什么才是合适的身份？

我想知道是否有人可以在这些原则上更多地启发我。

谢谢

Answer 1

why isn't the accumulator associative?

它不是关联的，因为减法运算的顺序决定了最终结果。

如果您运行串行 Stream，您将获得以下预期结果:

0 - 1 - 2 - 3 - 4 - 5 - 6 = -21

另一方面，对于并行 Stream，工作被拆分到多个线程。比如reduce在6个线程上并行执行，然后合并中间结果，可以得到不同的结果:

0 - 1   0 - 2   0 - 3      0 - 4     0 - 5    0 - 6
  -1     -2      -3         -4        -5        -6

  -1 - (-2)         -3 - (-4)          -5 - (-6)
      1                 1                  1
           1   -   1
               0            -     1

                        -1

或者，举一个简短的例子:

(1 - 2) - 3 = -4
1 - (2 - 3) =  2

因此减法不是关联的。

另一方面，a+b 不会导致同样的问题，因为加法是一个结合运算符(即 (a+b)+c == a+(b+ c)).

identity 示例的问题在于，当 reduce 在多个线程上并行执行时，“X”会附加到每个中间结果的开头。

What exactly would be a proper identity to use then?

如果将标识值更改为 "" :

System.out.println(Arrays.asList("w","o","l","f"))
.parallelStream()
.reduce("", String::concat));

你会得到“狼”而不是“XwXoXlXf”。