std::experimental::parallel::reduce
From cppreference.com
< cpp | experimental
| ヘッダ <experimental/numeric> で定義 |
||
| template< class InputIt > typename std::iterator_traits<InputIt>::value_type reduce( |
(1) | (並列処理 TS) |
| template< class ExecutionPolicy, class InputIterator > typename std::iterator_traits<InputIt>::value_type reduce( |
(2) | (並列処理 TS) |
| template< class InputIt, class T > T reduce( InputIt first, InputIt last, T init ); |
(3) | (並列処理 TS) |
| template< class ExecutionPolicy, class InputIt, class T > T reduce( ExecutionPolicy&& policy, InputIt first, InputIt last, T init ); |
(4) | (並列処理 TS) |
| template< class InputIt, class T, class BinaryOp > T reduce( InputIt first, InputIt last, T init, BinaryOp binary_op ); |
(5) | (並列処理 TS) |
| template< class ExecutionPolicy, class InputIt, class T, class BinaryOp > T reduce( ExecutionPolicy&& policy, |
(6) | (並列処理 TS) |
1) reduce(first, last, typename std::iterator_traits<InputIt>::value_type{}) と同じ。
3) reduce(first, last, init, std::plus<>()) と同じ。
5) init を初期値として、範囲
[first, last) を、binary_op で（順序は未指定で）順序を入れ替えたり集約したりして削減します。2,4,6) (1,3,5) と同じですが、policy に従って実行されます。
binary_op が結合的でも可換でもない場合、動作は非決定論的です。
binary_op が範囲 [first, last) 内の要素を変更したり、イテレータを無効にしたりした場合、動作は未定義です。
目次 |
[edit] パラメータ
| first, last | - | アルゴリズムを適用する要素の範囲 |
| init | - | 一般化された合計の初期値 |
| policy | - | 実行ポリシー |
| binary_op | - | 入力イテレータの逆参照の結果、他の binary_op の結果、および init に適用される（順序未指定の）二項演算子 FunctionObject |
| 型要件 | ||
-InputIt は LegacyInputIterator の要件を満たす必要があります。 | ||
[edit] 戻り値
init と *first、*(first + 1)、...、*(last - 1) を、binary_op で汎化された和。
汎化された和 GSUM(op, a1, ..., aN) は以下のように定義されます。
- N=1 の場合、a1
- N > 1 の場合、op(GSUM(op, b1, ..., bK), GSUM(op, bM, ..., bN)) ただし
- b1, ..., bN は a1, ..., aN の任意の置換であり、
- 1 < K+1 = M ≤ N
言い換えると、範囲の要素は任意の順序でグループ化および並べ替えられる可能性があります。
[edit] 計算量
binary_op の適用回数は O(last - first)。
[edit] 例外
- アルゴリズムの一部として呼び出された関数が例外をスローした場合、
policyがparallel_vector_execution_policyの場合、std::terminate が呼び出されます。policyがsequential_execution_policyまたはparallel_execution_policyの場合、アルゴリズムは、すべての例外をラップした exception_list を伴って終了します。例外が 1 つだけ捕捉されなかった場合、アルゴリズムはexception_listでラップせずに再スローする可能性があります。最初に例外が検出された後にアルゴリズムがどれだけの作業を行うかは未指定です。policyがその他の型の場合、動作は実装定義です。
- アルゴリズムがメモリの割り当てに失敗した場合（自身のため、またはユーザー例外を処理する際の
exception_listの構築のため）、std::bad_alloc がスローされます。
[edit] 注記
範囲が空の場合、init は変更されずに返されます。
policyがsequential_execution_policyのインスタンスの場合、すべての操作は呼び出しスレッドで実行されます。policyがparallel_execution_policyのインスタンスの場合、操作は未指定のスレッド数で、互いに順序が不定に実行される可能性があります。policyがparallel_vector_execution_policyのインスタンスの場合、実行は並列化およびベクトル化される可能性があります。関数本体の境界は尊重されず、ユーザーコードは任意の順序でオーバーラップおよび結合される可能性があります（特に、ユーザー提供の Callable が共有リソースにアクセスするためにミューテックスを取得してはならないことを意味します）。
[edit] 例
reduce は std::accumulate の順序不定バージョンです。
このコードを実行
#include <chrono> #include <experimental/execution_policy> #include <experimental/numeric> #include <iostream> #include <numeric> #include <vector> int main() { std::vector<double> v(10'000'007, 0.5); { auto t1 = std::chrono::high_resolution_clock::now(); double result = std::accumulate(v.begin(), v.end(), 0.0); auto t2 = std::chrono::high_resolution_clock::now(); std::chrono::duration<double, std::milli> ms = t2 - t1; std::cout << std::fixed << "std::accumulate result " << result << " took " << ms.count() << " ms\n"; } { auto t1 = std::chrono::high_resolution_clock::now(); double result = std::experimental::parallel::reduce( std::experimental::parallel::par, v.begin(), v.end()); auto t2 = std::chrono::high_resolution_clock::now(); std::chrono::duration<double, std::milli> ms = t2 - t1; std::cout << "parallel::reduce result " << result << " took " << ms.count() << " ms\n"; } }
実行結果の例
std::accumulate result 5000003.50000 took 12.7365 ms parallel::reduce result 5000003.50000 took 5.06423 ms
[edit] 関連情報
| 範囲の要素を合計または畳み込む (関数テンプレート) | |
| 範囲内の要素に関数を適用し、結果を結果範囲に格納する (関数テンプレート) | |
| (並列処理 TS) |
ファンクタを適用し、順序不定で削減します。 (関数テンプレート) |
