私は遭遇しました配列.parallelPrefixJava 8 で導入されました。
このオーバーロードされたメソッドは、入力配列の各要素に対して累積的な方法で操作を実行します。たとえば、ドキュメントから:
指定された関数を使用して、指定された配列の各要素を並列に累積します。たとえば、配列が最初に [2, 1, 0, 3] を保持し、演算が加算を実行する場合、戻り時に配列は [2, 3, 3, 6] を保持します。大規模な配列の場合、通常、並列プレフィックス計算は順次ループよりも効率的です。
parallel
では、ある項に対する演算が前の項に対する演算結果などに依存する場合、Java はこのタスクをどのように実現するのでしょうか。
自分でコードを確認してみましたが、 は使用されていますForkJoinTasks
が、結果をマージして最終的な配列を取得する方法はそれほど単純ではありません。
ベストアンサー1
重要な点は、オペレーターが
副作用なし、連想的な関数
この意味は
(a op b) op c == a op (b op c)
したがって、配列を 2 つに分割し、parallelPrefix
各半分にメソッドを再帰的に適用すると、後で配列の後半の各要素に操作を適用し、前半の最後の要素を適用することで、部分的な結果をマージできます。
追加の例を考えてみましょう[2, 1, 0, 3]
。配列を 2 つに分割し、それぞれの半分に対して演算を実行すると、次のようになります。
[2, 3] and [0, 3]
次に、それらを結合するために、3 (前半の最後の要素) を後半の各要素に追加して、次の結果を得ます。
[2, 3, 3, 6]
編集: この回答は、配列のプレフィックスを並列に計算する 1 つの方法を示しています。これは必ずしも最も効率的な方法ではなく、JDK 実装で使用される方法とも異なります。この問題を解決するための並列アルゴリズムについてさらに読むことができます。ここ。