Stream reduce（）要求到底包含什么？

Question

在reduce()并行流上使用操作时，OCP考试手册指出，reduce()论点必须遵守某些原则。这些原则如下：

1. 必须定义身份，以便对于流u中的所有元素，combiner.apply（identity，u）等于u。
2. 累加器运算符op必须是关联且无状态的，(a op b) op c等于a op (b op c)。
3. 组合器运算符还必须是关联且无状态的，并且必须与该身份兼容，以使得对于u和t combiner.apply(u, accumulator.apply(identity, t))都等于accumulator.apply(u,t)。
   
   

本书提供了两个示例来说明这些原理，请参见下面的代码：

关联的示例：

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

这本书怎么说：

由于累加器函数违反了关联性，它可能会输出-21、3或其他一些值。

身份要求示例：

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

这本书怎么说：

如果我们使用的标识参数不是真正的标识值，您还会看到其他问题。它可以输出XwXoXlXf。作为并行过程的一部分，标识将应用于流中的多个元素，从而导致非常意外的数据。

我不明白这些例子。与蓄能器例如蓄能器开始与0 - 1它是-1，则-1 - 2其是-3，则-6等一路-21。我知道，由于生成的arraylist不同步，结果可能由于竞争条件等而无法预测，但是为什么累加器不具有关联性呢？也不会(a+b)导致不可预测的结果吗？我真的看不到示例中使用的累加器有什么问题以及为什么它不具有关联性，但是我仍然不完全理解“关联性原理”的含义。

我也不了解身份示例。我知道，结果可能确实是XwXoXlXf如果4个单独的线程同时开始使用Identity进行累加，但是那与identity参数本身有什么关系呢？那么要使用的正确身份到底是什么？

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

谢谢

Answer 1

让我举两个例子。首先，身份被破坏：

int result = Stream.of(1, 2, 3, 4, 5, 6)
        .parallel()
        .reduce(10, (a, b) -> a + b);

System.out.println(result); // 81 on my run

基本上，您已经违反了以下规则：The identity value must be an identity for the accumulator function. This means that for all u, accumulator(identity, u) is equal to u。

或更简单地说，让我们看看该规则是否适用于Stream中的一些随机数据：

 Integer identity = 10;
 BinaryOperator<Integer> combiner = (x, y) -> x + y;
 boolean identityRespected = combiner.apply(identity, 1) == 1;
 System.out.println(identityRespected); // prints false

第二个例子：

/**
 * count letters, adding a bit more all the time
 */
private static int howMany(List<String> tokens) {
    return tokens.stream()
            .parallel()
            .reduce(0, // identity
                    (i, s) -> { // accumulator
                        return s.length() + i;
                    }, (left, right) -> { // combiner
                        return left + right + left; // notice the extra left here
                    });
}

然后使用以下命令调用它：

List<String> left = Arrays.asList("aa", "bbb", "cccc", "ddddd", "eeeeee");
List<String> right = Arrays.asList("aa", "bbb", "cccc", "ddddd", "eeeeee", "");

System.out.println(howMany(left));  // 38 on my run
System.out.println(howMany(right)); // 50 on my run

基本上，您已经违反了此规则：Additionally, the combiner function must be compatible with the accumulator function或在代码中：

// this must hold!
// combiner.apply(u, accumulator.apply(identity, t)) == accumulator.apply(u, t)

Integer identity = 0;
String t = "aa";
Integer u = 3; // "bbb"
BiFunction<Integer, String, Integer> accumulator = (Integer i, String s) -> i + s.length();
BinaryOperator<Integer> combiner = (left, right) -> left + right + left;

int first = accumulator.apply(identity, t); // 2
int second = combiner.apply(u, first); // 3 + 2 + 3 = 8

Integer shouldBe8 = accumulator.apply(u, t);

System.out.println(shouldBe8 == second); // false