reduceとscan
parallel algorithmの導入に併せて数値アルゴリズム<numeric>にreduceとscanが追加されています。
reduce：並列版accumulate
reduce(policy, first, last, init, binary_op)
binary_opは二項演算（引数2つの関数オブジェクト）、これを◎で表すと：
init ◎*first ◎*(first+1)◎... ◎*(last-1)
を求めます。このとき二項演算が結合則：(x ◎y) ◎z = x ◎(y ◎z) および交換則：x ◎y = y ◎xを満足するなら、上式はどこからどんな順序で計算しても同じ結果が得られます。この性質を利用して並列化しようって魂胆です。a ◎b ◎c ◎dに対しa ◎b とc ◎dを並列に（同時に）計算しても構わんのですから。
array<int,1000> data; iota(data.begin(), data.end(), 1); // 1, 2, 3... で埋める // 1 + 2 +...+ 1000 を求める int sum = reduce(execution::par, data.begin(), data.end(), 0, plus<int>()); cout << sum << endl; // 500500
transform_reduce：並列版inner_product
tranform_reduce(policy, first, last, init, binary_op, unary_op)
二項演算：binary_opを◎、単項演算：unary_opをf()で表すと：
init ◎f(*first) ◎f(*(first+1))◎... ◎f(*(last-1))
を求めます。
array<int,7> data = { 1, 2, 3, 4, 5, 6, 7 };
// 1 + 3 + 5 + ... は平方数
int sum = transform_reduce(execution::par, data.begin(), data.end(), 0, plus<int>(), [](int n) { return 2*n-1; });
cout << sum << endl; // 49 (7^2)
入力シーケンスを2つ与えるタイプもあって
tranform_reduce(policy, first1, last1, first2, init, binary_op1, binary_op2)
二項演算：binary_op1, binary_op2をそれぞれ◎とf()で表すと：
init ◎f(*first1,*first2) ◎f(*(first1+1),*(first2+1)◎...
を求めます。binary_op1, binary_op2が加算,乗算なら、2つのベクトルの内積（inner_product）を求めることになります。
inclusive_scan：並列版partial_sum
inclusive_scan(policy, first, last, out, binary_op, init)
*outにはinit ◎*first、*(out+1)にはinit ◎*first ◎*(first+1)、……、*(out+i)にはfirstからfirst+iまでのreduce()の結果が求まります。
array<int,7> data = { 1, 3, 5, 7, 9, 11, 13 };
array<int,7> out;
// 1 + 3 + 5 + ... は平方数
inclusive_scan(execution::par, data.begin(), data.end(), out.begin(), plus<int>(), 0);
for ( int sum : out ) {
cout << sum << ' '; // 1 4 9 16 25 36 49
}
reduce()と同様、入力シーケンスを2つ与えるタイプも定義されています。
exclusive_scan
ふるまいはinclusive_scan()とほとんど同じ、異なるのは*(out+i)にはfirstからfirst+iの"直前"までのreduce()の結果が得られること。i番目の結果にi番目の入力が含まれないので"exclusive"なのです。
あとtransform_inclusive_scan, transform_exclusive_scanがあるけど……説明割愛！
繰り返しになりますが、reduce／scanは与える二項演算が結合則と交換則を満たさないと、その動作は非決定的（non-deterministic）、つまり結果が一意に定まらないのでご注意を。
……待ってたんですよparallel algorithms、こんなにお手軽な並列化が標準C++でサポートされるんだから、三途の川の向こう岸から還ってきた甲斐がありました。thread poolやconcurrent containerの類が標準化されるとステキなんですけど……もうしばらく、生きてみましょかね♪
