为什么顺序流和并行流的减少结果不同？

Question

我有以下列表integers(所有数字从0到999,999):

List<Integer> integers = new ArrayList<>();
for (int i = 0; i != 10_000_000; ++i) {
    integers.add(i);
}

我正在尝试将以下内容作为Java 8 Stream运行:

int sum = 0;
for (Integer i : integers) {
    sum = i % 2 == 0 ? i - sum : i + sum;
}
System.out.println(sum);

我期待以下输出:

0 - 0 = 0  
1 + 0 = 1  
2 - 1 = 1   
3 + 1 = 4  
4 - 4 = 0  
5 + 0 = 5  
6 - 5 = 1  
7 + 1 = 8
8 - 8 = 0   
...
999,998 - 999,997 = 1
999,999 + 1 = 10,000,000

10,000,000(顺便说一下,有人可以用数学表达这个吗？我不能......)

如果我运行这个:

int sum = integers.stream().reduce(
                0,
                (sum, i) -> i % 2 == 0 ? i - sum : i + sum
            );

sum是预期的金额,10,000,000.

但是,如果我将流更改为并行:

int sum = integers.parallelStream().reduce(
                0,
                (sum, i) -> i % 2 == 0 ? i - sum : i + sum
            );

sum是0!

我似乎无法弄清楚为什么会这样,有人可以解释一下吗？

Answer 1

Javadoc reduce:

使用关联累加函数执行此流的元素的减少,

注意"associative"这个词:这是你的还原功能所不具备的属性.

关联性是并行化的关键:操作的应用顺序没有定义,没有关联性,结果在重新排序时不会是不变的.

如果您有两个以上availableProcessors,您可以使用以下代码来说服自己,答案取决于子任务的数量(请注意,您不应该使用10_000_000作为问题大小,因为它的因子分解中必须有两个;使用10_000_001):

System.setProperty("java.util.concurrent.ForkJoinPool.common.parallelism", "2");
System.out.println(IntStream.range(0,10_000_001).parallel().reduce(0,
    (sum, i) -> i % 2 == 0 ? i - sum : i + sum
));

当您更改系统属性的值时,结果也会更改.