Stream reduce（）要求究竟需要什么？ [英] What do the Stream reduce() requirements exactly entail?

问题描述

在并行流上使用 reduce（）操作时，OCP考试书指出 reduce（）参数也必须坚持。这些参数如下：

When using the reduce() operation on a parallelstream the OCP exam book states that there are certain principles the reduce() arguments must adhere too. Those arguments are the following:

1. 必须定义标识，以便对于流u中的所有元素u，combiner.apply（identity，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）。

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) .

考试书提供了两个例子来说明这些原则，请参阅下面的代码：

The exam book gives two examples to illustrate these principles, please see the code below:

关联的例子：

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

OCP书中对此有何说法：

What the OCP book says about this:

由于累加器函数
违反了associativity属性，它可能输出-21,3或其他一些值。

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));

OCP书中对此有何说法：

What the OCP book says about this:

如果我们使用非
的身份参数确实是一个身份值，你可以看到其他问题。它可以输出XwXoXlXf。作为
并行流程的一部分，该身份将应用于
流中的多个元素，从而产生非常意外的数据。

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不同步，结果可能是不可预测的，因为竞争条件等的可能性，但为什么累加器不关联？ Woulden't （a + b）也导致不可预测的结果？我真的没有看到示例中使用的累加器有什么问题，以及为什么它没有关联，但是我仍然不能完全理解关联原理是什么。

I don't understand those examples. With the accumulator example the accumulator starts with 0 -1 = -1 then -1 -2 which is = -3 then -6 etc etc all the way to -21. I understand that, because the generated arraylist isen't synchronized the results maybe be unpredictable because of the possibility of race conditions etc, but why isen't the accumulator associative? Woulden't (a+b) cause unpredictable results too? I really don't see whats wrong with the accumulator being used in the example and why its not associative, but then again I still don't exactly understand what is being ment with the associative principle.

我也不了解身份的例子。据我所知，如果4个独立的线程同时开始与身份一起累积，那么结果确实可能是XwXoXlXf，但这与身份参数本身有什么关系呢？那么究竟什么是正确的身份呢？

I don't understand the identity example either. I understand that the result could indeed be XwXoXlXf if 4 separate threads were to start accumulating with the identity at the same time, but what does that have to do with the identity parameter itself? What exactly would be a proper identity to use then?

我想知道是否有人可以更多地了解这些原则。

I was wondering if anyone could enlighten me a bit more on these principles.

谢谢

推荐答案

让我举两个例子。首先是身份被破坏的地方：

Let me give two examples. First where the identity is broken:

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

基本上你违反了这条规则：身份value必须是累加器函数的标识。这意味着对于所有你来说，累加器（identity，u）等于u 。

Basically you have broken this rule: 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中的一些随机数据：

Or to make is simpler, let's see if that rule holds for some random data from our 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

基本上你违反了这个规则：此外，组合器函数必须与累加器函数或代码兼容：

Basically you have broken this rule: Additionally, the combiner function must be compatible with the accumulator function or in code :

 // 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

这篇关于Stream reduce（）要求究竟需要什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！