Java 8中新引入的Arrays.parallelPrefix（...）是如何工作的？

重点是运算符是

无副作用，联想功能

这意味着

(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实现使用的方式。您可以在此处进一步阅读有关解决该问题的并行算法的信息。

如 Eran 的答案中所述，此操作利用函数的结合性属性。

然后，有两个基本步骤。第一个是实际的前缀操作（在需要前一个元素进行评估的意义上），并行应用于数组的各个部分。每个部分操作的结果（与生成的最后一个元素相同）是剩余数组的偏移量。

例如，对于以下数组，使用 sum 作为前缀操作，以及四个处理器

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

我们得到

  4 → 13 → 18 → 19    0 →  5 →  6 → 12    6 → 10 → 16 → 21    1 →  7 → 16 → 19  
                 ↓                   ↓                   ↓                   ↓  
                19                  12                  21                  19  

现在，我们利用关联性首先将前缀操作应用于偏移量

                 ↓                   ↓                   ↓                   ↓  
                19         →        31         →        52         →        71  

然后，我们进入第二阶段，即将这些偏移量应用于下一个块的每个元素，这是一个完全可并行化的操作，因为不再依赖于前一个元素。

                     19   19   19   19   31   31   31   31   52   52   52   52  
                      ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

当我们对八个线程使用相同的示例时，

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

  4 → 13    5 →  6    0 →  5    1 →  7    6 → 10    6 → 11    1 →  7    9 → 12  
       ↓         ↓         ↓         ↓         ↓         ↓         ↓         ↓  
      13         6         5         7        10        11         7        12  

       ↓         ↓         ↓         ↓         ↓         ↓         ↓         ↓  
      13    →   19    →   24    →   31    →   41    →   52    →   59    →   71  

           13   13   19   19   24   24   31   31   41   41   52   52   59   59  
            ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

我们看到会有一个明显的好处，即使我们使用更简单的策略，使两个步骤的工作块保持不变，换句话说，在第二阶段接受一个空闲的工作线程。第一阶段需要大约 1/8n，第二阶段需要 1/8n，操作需要总计 1/4n（其中 n 是整个阵列的顺序前缀评估的成本）。当然，在最好的情况下，只是粗略的。

相反，当我们只有两个处理器时

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  


  4 → 13 → 18 → 19 → 19 → 24 → 25 → 31    6 → 10 → 16 → 21 → 22 → 28 → 37 → 40  
                                     ↓                                       ↓  
                                    31                                      40  

                                     ↓                                       ↓  
                                    31                   →                  71  

                                         31   31   31   31   31   31   31   31  
                                          ↓    ↓    ↓    ↓    ↓    ↓    ↓    ↓  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

只有当我们重新分配第二阶段的工作时，我们才能获得好处。如前所述，这是可能的，因为第二阶段的工作不再依赖于元素。因此，我们可以任意拆分此操作，尽管它会使实现复杂化，并且可能会引入额外的开销。

当我们在两个处理器之间分配第二阶段的工作时，第一阶段需要大约1/2n，第二阶段需要1/4n，产生3/4n的总数，如果阵列足够大，这仍然是一个好处。

作为补充说明，您可能会注意到，在准备第二阶段时计算的偏移量与块的最后一个元素的结果相同。因此，只需分配该值，即可将每个区块所需的操作数减少一次。但典型的情况是只有几个块（随着处理器数量而扩展）具有大量元素，因此每个块保存一个操作无关紧要。