std::experimental::parallel::reduce

 

C++

编译器支持

独立和托管

语言

标准库

标准库头文件

命名要求

特性测试宏 (C++20)

语言支持库

概念库 (C++20)

元编程库 (C++11)

诊断库

通用实用程序库

字符串库

容器库

迭代器库

范围库 (C++20)

算法库

数值库

本地化库

输入/输出库

文件系统库 (C++17)

正则表达式库 (C++11)

并发支持库 (C++11)

执行支持库 (C++26)

技术规范

符号索引

外部库

 

实验性

技术规范

文件系统库 (文件系统 TS)

库基础 (库基础 TS)

库基础 2 (库基础 TS v2)

库基础 3 (库基础 TS v3)

并行扩展 (并行 TS)

并行扩展 2 (并行 TS v2)

并发扩展 (并发 TS)

并发扩展 2 (并发 TS v2)

概念 (概念 TS)

范围 (范围 TS)

反射 (反射 TS)

数学特殊函数 (特殊函数 TR)

实验性 非 TS

模式匹配

线性代数

std::execution

契约

2D 图形

 

并行扩展

执行策略

parallel::execution_policy

parallel::sequential_execution_policyparallel::parallel_execution_policyparallel::parallel_vector_execution_policy

parallel::seqparallel::parparallel::par_vec

并行算法

并行异常

parallel::exception_list

现有算法的并行版本

新算法

parallel::for_eachparallel::for_each_n

parallel::reduce

parallel::exclusive_scan

parallel::inclusive_scan

parallel::transform_reduce

parallel::transform_exclusive_scan

parallel::transform_inclusive_scan

 

定义在头文件 <experimental/numeric> 中
template< class InputIt > typename std::iterator_traits<InputIt>::value_type reduce(     InputIt first, InputIt last );	(1)	(并行 TS)
template< class ExecutionPolicy, class InputIterator > typename std::iterator_traits<InputIt>::value_type reduce(     ExecutionPolicy&& policy, InputIt first, InputIt last );	(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,           InputIt first, InputIt last, T init, BinaryOp binary_op );	(6)	(并行 TS)

1) 等同于 reduce(first, last, typename std::iterator_traits<InputIt>::value_type{}).

3) 等同于 reduce(first, last, init, std::plus<>()).

5) 减少范围 [first, last)，可能以未指定的顺序排列和聚合，以及初始值 init 在 binary_op 上。

2,4,6) 等同于 (1,3,5)，但根据 policy 执行。

如果 binary_op 不具有结合性或不具有交换性，则行为是不确定的。

如果 binary_op 修改了 [first, last) 中的任何元素或使其中任何迭代器失效，则行为未定义。

参数

first, last	-	要应用算法的元素范围
init	-	广义和的初始值
policy	-	该 执行策略
binary_op	-	二元 函数对象，它将以未指定的顺序应用于对输入迭代器解引用结果、其他 binary_op 结果和 init 的结果。
类型要求
- InputIt 必须满足 LegacyInputIterator 的要求。

返回值

init 和 *first、*(first + 1)、... *(last - 1) 在 binary_op 上的广义和，

其中广义和 GSUM(op, a
1, ..., a
N) 定义如下

• 如果 N=1，则为 a
  1
• 如果 N > 1，则为 op(GSUM(op, b
  1, ..., b
  K), GSUM(op, b
  M, ..., b
  N))，其中

• b
  1, ..., b
  N 可以是 a1, ..., aN 的任何排列，并且
• 1 < K+1 = M ≤ N

换句话说，范围的元素可以以任意顺序分组和重新排列。

复杂度

O(last - first) 次 binary_op 应用。

异常

• 如果作为算法一部分调用的函数执行时抛出异常，

• 如果 policy 是 parallel_vector_execution_policy，则调用 std::terminate。
• 如果 policy 是 sequential_execution_policy 或 parallel_execution_policy，则算法退出并带有包含所有未捕获异常的 exception_list。如果只有一个未捕获异常，则算法可能会在不将其包装在 exception_list 中的情况下重新抛出它。在遇到第一个异常后，算法将执行多少工作才能返回是不确定的。
• 如果policy是其他类型，则行为是实现定义的。

• 如果算法无法分配内存（无论是为自己还是在处理用户异常时构造exception_list），则会抛出std::bad_alloc。

注释

如果范围为空，则返回未修改的init。

• 如果policy是sequential_execution_policy的实例，则所有操作都在调用线程中执行。
• 如果policy是parallel_execution_policy的实例，则操作可能在未指定的数量的线程中执行，这些线程彼此之间是无序的。
• 如果policy是parallel_vector_execution_policy的实例，则执行可以并行化和矢量化：函数体边界不被尊重，用户代码可以以任意方式重叠和组合（特别是，这意味着用户提供的可调用对象不能获取互斥锁来访问共享资源）。

示例

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

另请参阅

accumulate	将一系列元素加起来或折叠起来 (函数模板)
transform	将函数应用于一系列元素，并将结果存储在目标范围内 (函数模板)
transform_reduce (并行 TS)	应用一个函子，然后无序地减少 (函数模板)