java - Java 8 中新引入的 Arrays.parallelPrefix(...) 是如何工作的？

Question

我遇到了Arrays.parallelPrefix在 Java 8 中引入。

此重载方法以累积方式对输入数组的每个元素执行操作。例如来自文档:

Cumulates, in parallel, each element of the given array in place, using the supplied function. For example if the array initially holds [2, 1, 0, 3] and the operation performs addition, then upon return the array holds [2, 3, 3, 6]. Parallel prefix computation is usually more efficient than sequential loops for large arrays.

那么，当一个term的运算依赖于上一个term的运算结果，以此类推时，Java如何在parallel中完成这个任务？

我自己尝试过代码，他们确实使用了 ForkJoinTasks，但他们如何合并结果以获得最终数组并不是那么简单。

Answer 1

重点是操作符是一个

side-effect-free, associative function

这意味着

(a op b) op c == a op (b op c)

因此，如果将数组分成两半，并在每一半上递归地应用 parallelPrefix 方法，则稍后可以通过对后半的每个元素应用操作来合并部分结果包含前半部分最后一个元素的数组。

考虑 [2, 1, 0, 3] 加法示例。如果你把数组分成两半，对每一半进行运算，你会得到:

[2, 3]    and    [0, 3]

然后，为了合并它们，你将 3(前半部分的最后一个元素)添加到后半部分的每个元素中，并得到:

[2, 3, 3, 6]

编辑:这个答案提出了一种并行计算数组前缀的方法。它不一定是最有效的方式，也不一定是 JDK 实现使用的方式。您可以进一步阅读解决该问题的并行算法 here .