在Stream reduce方法中,对于sum,标识总是0,对于乘法,1必须是1？

Question

我继续学习java 8.

我发现了有趣的行为:

让我们看看代码示例:

// identity value and accumulator and combiner
        Integer summaryAge = Person.getPersons().stream()
                //.parallel()  //will return surprising result
                .reduce(1, (intermediateResult, p) -> intermediateResult + p.age,
                        (ir1, ir2) -> ir1 + ir2);
        System.out.println(summaryAge);

和模型类:

public class Person {

    String name;

    Integer age;
    ///...

    public static Collection<Person> getPersons() {
        List<Person> persons = new ArrayList<>();
        persons.add(new Person("Vasya", 12));
        persons.add(new Person("Petya", 32));
        persons.add(new Person("Serj", 10));
        persons.add(new Person("Onotole", 18));
        return persons;
   }
}

12 + 32 + 10 + 18 = 72
对于序列流,此代码始终返回73(72 + 1),但对于并行,它始终返回76(72 + 4*1).4 - 流元素计数.

当我看到这个结果时,我认为并行流和序列流返回不同的结果是很奇怪的.

我在某个地方违约吗？

PS

对我来说73是预期的结果,但76 - 不是.

Answer 1

身份值是一个值,这样x op identity = x.这是一个并非Java独有的概念,Stream例如参见维基百科.

它列出了一些身份元素的例子,其中一些可以直接用Java代码表示,例如

• reduce("", String::concat)
• reduce(true, (a,b) -> a&&b)
• reduce(false, (a,b) -> a||b)
• reduce(Collections.emptySet(), (a,b)->{ Set<X> s=new HashSet<>(a); s.addAll(b); return s; })
• reduce(Double.POSITIVE_INFINITY, Math::min)
• reduce(Double.NEGATIVE_INFINITY, Math::max)

应当清楚的是,表达x + y == x为任意的x时,只能得到满足y==0,因而0是用于添加的标识元件.同样,1是乘法的标识元素.

更复杂的例子是

• 减少谓词流

  reduce(x->true, Predicate::and)
  reduce(x->false, Predicate::or)
  

• 减少功能流

  reduce(Function.identity(), Function::andThen)
  

Answer 2

该@holger答案大大解释一下什么是功能不同身份，但并不能解释为什么我们需要身份以及为什么你有不同的结果并行或连续流。

您的问题可以简化为¹，求和一个元素列表，知道如何对2个元素求和。

因此，让我们列出一个列表L = {12,32,10,18}和一个求和函数(a,b)-> a + b

就像您在学校学习一样，您将：

(12,32) -> 12 + 32 -> 44
(44,10)-> 44 + 10 -> 54
(54,18)-> 54 + 18 -> 72

现在想象一下我们的清单变成L = {12}如何对这个清单求和？身份（x op identity = x）出现了。

(0,12) -> 12

备注：一个空列表返回标识

因此，现在您可以理解为什么如果1不加0总和而不是+1，那么您将使用错误的值进行初始化。

(1,12) -> 1 + 12 -> 13
(13,32) -> 13 + 32 -> 45
(45,10)-> 45 + 10 -> 55
(55,18)-> 55 + 18 -> 73

那么，现在如何提高速度？平行化事物

如果我们可以拆分列表并将拆分后的列表分配给4个不同的线程（假设使用4core cpu）然后将其合并怎么办？让我们尝试这将给我们L1 = {12} L2 = {32} L3 = {10} L4 = {18}

因此，身分= 1

• 线程1：做 (1,12) -> 1+12 -> 13
• 线程2：做 (1,32) -> 1+32 -> 33
• 线程3：做 (1,10) -> 1+10 -> 11
• 线程4：做 (1,18) -> 1+18 -> 19

并结合（13 + 33 + 11 +19）= 76，这说明了为什么您的错误会传播4次。

在这种情况下，并行效率可能较低。

但是此结果取决于您的计算机，并且您输入的列表Java不会为1000个Elts创建1000个线程，并且随着输入的增长，错误会更慢地传播

尝试运行这段代码，将其累加成千个1，结果非常接近1000

public class StreamReduce {

public static void main(String[] args) {
        int sum = IntStream.range(0, 1000).map(i -> 1).parallel().reduce(1, (r, e) -> r + e);
        System.out.println("reduced : " + sum);
    }

}

因此，现在您应该了解，如果违反身份合同，为什么在并行或顺序结果之间会有不同的结果。

有关写总和的正确方法，请参见Oracle文档

¹问题的身份是什么？;）

Answer 3

是的,你违反了合并器功能的合同.作为第一要素的身份reduce必须满足combiner(identity, u) == u.引用Javadoc Stream.reduce:

标识值必须是组合器函数的标识.这意味着,对所有人来说u,combiner(identity, u)等于u.

但是,组合器函数执行添加并且1不是添加的标识元素; 0是.

• 更改用于的身份0,您将不会感到惊讶:两个选项的结果将是72.

• 为了您自己的娱乐,更改组合器功能以执行乘法(将标识保持为1),您也会注意到两个选项的相同结果.

让我们构建一个身份既不是0或1的示例.给定您自己的域类,请考虑:

System.out.println(Person.getPersons().stream()
                    .reduce("", 
                            (acc, p) -> acc.length() > p.name.length() ? acc : p.name,
                            (n1, n2) -> n1.length() > n2.length() ? n1 : n2));

这会将Person流减少为最长的人名.