通过

并行算法

  • 项目

并行模式库 (PPL) 提供了可用于同时对多个数据集合执行操作的算法。 这些算法与标准模板库 (STL) 提供的算法类似。

并行算法由并发运行时中的现有功能组成。 例如，concurrency::parallel_for 算法使用一 concurrency::structured_task_group 对象执行并行循环迭代。 在给定可用数量的计算资源的情况下，parallel_for 算法会按照最佳方式对工作进行分区。

各节内容

  • parallel_for 算法

  • parallel_for_each 算法

  • parallel_invoke 算法

  • parallel_transform 和 parallel_reduce 算法

    • parallel_transform 算法

    • parallel_reduce 算法

    • 示例：执行映射和并行降低

  • 分区工作

  • 并行排序

    • 选择了排序算法

parallel_for 算法

concurrency::parallel_for 算法并行重复执行相同任务。 其中每个任务都由迭代值进行参数化。 当一个循环体不在该循环的各个迭代之间共享资源时，此算法很有用。

parallel_for 算法会按照最佳方式对任务进行分区以便并行执行。 以便对量是平衡时，它使用窃取了工作窃取算法和的大小平衡这些分区。 当以协作方式阻止某个循环迭代时，运行时会将指派给当前线程的迭代范围重新发布给其他线程或处理器。 类似地，当某个线程完成迭代范围时，运行时会将其他线程的工作重新发布给该线程。 parallel_for 算法还支持嵌套并行。 当一个并行循环包含另一个并行循环时，运行时会以一种适合并行执行的高效方式在循环主体之间协调处理资源。

parallel_for 算法具有多个重载版本。 第一个版本采用起始值、结束值和工作函数（lambda 表达式、函数对象或函数指针）。 第二个版本采用起始值、结束值、步长值和工作函数。 此函数的第一个版本使用 1 作为步长值。 其余的版本采用分区程序对象，如何使您能够指定 parallel_for 如果线程中的分区大小。 分区程序在部分 分区工作 中更详细说明了文档。

可以将很多 for 循环转换为使用 parallel_for。 但是，parallel_for 算法与 for 语句在以下方面存在差异：

  • parallel_for 算法 parallel_for 不按照预定的顺序执行任务。

  • parallel_for 算法不支持任意终止条件。 当迭代变量的当前值比 _Last 小 1 时，parallel_for 算法将停止。

  • _Index_type 类型参数必须是整型。 此整型可以带符号或者不带符号。

  • 循环迭代必须是向前的。 如果 _Step 参数小于 1，则 parallel_for 算法会引发 std::invalid_argument 类型的异常。

  • parallel_for 算法的异常处理机制与 for 循环的不同。 如果并行循环主体中同时发生多个异常，则运行时仅传播其中一个异常给名为 parallel_for 的线程。 另外，当某个循环迭代引发异常时，运行时不会立即停止整个循环。 而是将循环置于取消状态，并且运行时会放弃任何尚未开始的任务。 有关异常处理和并行算法的更多信息，请参见并发运行时中的异常处理。

虽然 parallel_for 算法不支持任意终止条件，但您可以通过取消操作来停止所有任务。 有关取消操作的更多信息，请参见 PPL 中的取消操作。

备注

尽管因负载平衡和功能支持（例如取消）而产生了一些计划成本，但这并不能抵消并行执行循环主体所带来的好处相比，特别是在循环主体相对比较小的情况下。您可以通过在的并行循环，的分区程序可以最小化此开销。有关更多信息，请参见 分区工作 文档中。

Dd470426.collapse_all(zh-cn,VS.110).gif示例

下面的示例显示了 parallel_for 算法的基本结构。 本示例在控制台上并行打印 [1, 5] 范围内的每个值。

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

此示例产生下面的示例输出：

由于 parallel_for 算法并行作用于每个项目，因此值打印在控制台的顺序将会有所变化。

有关使用 parallel_for 算法的完整示例，请参见如何：编写 parallel_for 循环。

[顶级]

parallel_for_each 算法

concurrency::parallel_for_each 算法迭代容器执行任务，如 STL 提供的任务，并行。 此算法使用的分区逻辑与 parallel_for 算法使用的分区逻辑相同。

parallel_for_each 算法与 STL std::for_each 算法类似，只是 parallel_for_each 算法并发执行任务。 与其他并行算法一样，parallel_for_each 不按特定的顺序执行任务。

虽然 parallel_for_each 算法既可用于向前迭代器，又可用于随机访问迭代器，但此算法更适用于随机访问迭代器。

Dd470426.collapse_all(zh-cn,VS.110).gif示例

下面的示例显示了 parallel_for_each 算法的基本结构。 本示例在控制台上并行打印 std::array 对象内的每个值。

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

此示例产生下面的示例输出：

由于 parallel_for_each 算法并行作用于每个项目，因此值打印在控制台的顺序将会有所变化。

有关使用 parallel_for_each 算法的完整示例，请参见如何：编写 parallel_for_each 循环。

[顶级]

parallel_invoke 算法

concurrency::parallel_invoke 算法并行执行一组任务。 在完成所有任务之前，此算法不会返回。 当您需要同时执行多个独立的任务时，此算法很有用。

parallel_invoke 算法采用一系列工作函数（lambda 函数、函数对象或函数指针）作为其参数。 可对 parallel_invoke 算法进行重载以采用 2 到 10 个参数。 传递给 parallel_invoke 的每个函数都必须采用零个参数。

与其他并行算法一样，parallel_invoke 不按特定的顺序执行任务。 主题任务并行（并发运行时）说明 parallel_invoke 算法如何关联至任务和任务组。

Dd470426.collapse_all(zh-cn,VS.110).gif示例

下面的示例显示了 parallel_invoke 算法的基本结构。 本示例对三个局部变量并发调用 twice 函数并将结果打印到控制台。

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

该示例产生下面的输出：

有关使用 parallel_invoke 算法的完整示例，请参见如何：使用 parallel_invoke 来编写并行排序运行时和如何：使用 parallel_invoke 来执行并行操作。

[顶级]

parallel_transform 和 parallel_reduce 算法

concurrency::parallel_transform 和 concurrency::parallel_reduce 算法分别用于 STL 算法 std::transform 和 std::accumulate的并行版本，即。 并发运行时版本的行为与 STL 版本，但操作顺序并不确定的，因为它们并行执行。 使用这些算法，将是从并行处理的足够大捕获性能和伸缩性优点设置的一起使用。

重要

因为这些迭代器生成稳定的内存地址，parallel_transform 和 parallel_reduce 算法支持随机访问，双向和仅向前迭代器。此外，这些迭代器必须生成非const 左值。

Dd470426.collapse_all(zh-cn,VS.110).gifparallel_transform 算法

可以使用 parallel transform 算法执行大量数据并行化操作。 例如，您可以：

  • 调整图像的状态，并执行其他图像处理操作。

  • 计算或带点积在两个矢量之间，并对矢量的其他数值计算。

  • 执行三维光线跟踪，每次迭代引用像素必须呈现。

下面的示例演示用于调用 parallel_transform 算法的基本结构。 此示例求反 std::vector 对象的每个元素有两种方法。 第一种方法使用 lambda 表达式。 第二种方法是使用 std::negate，从 std::unary_function派生。

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

警告

此示例演示如何使用 parallel_transform的基本用法。由于工作函数不执行大量工作，在性能的大量增加不应在本例中为。

parallel_transform 算法具有两个超负载。 第一个超加载采用一个输入的大小和一个一元运算符功能。 一元"功能可以是带有一个参数、函数对象或类型从 unary_function派生的 lambda 表达式。 第二个超加载采用两个输入的大小和二进制功能。 该二进制功能可以是采用两个参数、函数对象或类型从 std::binary_function派生的 lambda 表达式。 下面的示例演示了这些差异。

//
// Demonstrate use of parallel_transform together with a unary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), 
    begin(results), [](int n) { 
        return -n;
    });

// Alternatively, use the negate class:
parallel_transform(begin(values), end(values), 
    begin(results), negate<int>());

//
// Demonstrate use of parallel_transform together with a binary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), [](int n, int m) {
        return n * m;
    });

// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), multiplies<int>());

重要

为 parallel_transform 输出提供的迭代器必须完全重叠输入迭代器或根本不重叠。如果输入和输出迭代器部分重叠，此算法行为是未指定的。

Dd470426.collapse_all(zh-cn,VS.110).gifparallel_reduce 算法

parallel_reduce 算法很有用，当您具有足够关联的属性操作时的序列。 (此算法不需要该可交换的属性。)这是您执行与 parallel_reduce的某些操作：

  • 矩阵乘以序列生成矩阵。

  • 用矢量以矩阵序列生成矢量。

  • 计算字符串序列的长度。

  • 组合元素列表，例如字符串，到一个元素。

下面的基本示例演示如何使用 parallel_reduce 算法合并字符串序列组合为一个字符串。 与 parallel_transform的示例，性能增益此基本示例中不需要。

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string> 
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a vector of strings.
    vector<wstring> words;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(L"elit.");

    // Reduce the vector to one string in parallel.
    wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

在大多数情况下，可以将 parallel_reduce 作为简写为 parallel_for_each 算法将使用具有 concurrency::combinable 选件类。

Dd470426.collapse_all(zh-cn,VS.110).gif示例：执行映射和并行降低

映射 操作将函数应用于序列的每个值。 减少 操作合并序列的元素添加到一个值。 您可以使用标准模板库 (STL) std::transformstd::accumulate 选件类执行映射和减少操作。 但是，对于许多问题，可以使用 parallel_transform 算法并行执行映射操作，并 parallel_reduce 算法并行执行减少操作。

下面的示例比较它采用按顺序并行计算质数的和的时间。 映射阶段转换非类值为 0，并减少阶段要求和值。

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms

   1709600813
   parallel time: 1969 ms
*/

有关如何执行映射和并行降低操作的其他示例，请参见 如何：并行执行映射和减少操作。

[顶级]

分区工作

若要对数据源操作进行并行化，一个必要步骤是将源 分区 为可由多个线程同时访问的多个部分。 如果线程中，的分区范围分区程序如何指定并行算法。 遵循声明之前。本文档，PPL 使用分区创建一个初始大小然后使用工作窃取了工作窃取算法和的大小平衡这些分区结构的默认值，以便对量是平衡时。 例如，那么，当某个循环迭代完成迭代的大小时，运行时重新分配从其他线程的工作给该线程。 但是，对于某些情况，您可能希望指定更适合您的问题的一个不同的分区的结构。

parallel_for、parallel_for_each和 parallel_transform 算法提供采用一个参数的重载版本，_Partitioner。 此参数定义划分工作的分区程序类型。 这是 PPL 定义的命名分区程序：

  • concurrency::affinity_partitioner
    除工作范围内中 (通常是数目的一个固定数量的可用在循环工作) 的线程。 此分区程序类型类似于 static_partitioner，不过，提高它的方式引起范围映射到辅助线程的缓存关联。 此分区程序类型可以提高性能，则执行循环在相同的设置数据多次 (例如循环中的循环) 以及数据放入缓存。 此分区程序不完全参与取消。 它还不使用协作停滞语义不能用于与向前依赖项的并行循环。

  • concurrency::auto_partitioner
    除工作范围内 (通常是数目的最初值可用在循环工作) 的线程。 运行时使用此类型默认情况下，当没有调用接受 _Partitioner 参数的重载并行算法时。 每个范围可划分为子范围从而使负载平衡发生。 当工作范围完成时，运行时将工作重新分配的子范围从其他线程到该线程。 请使用此分区程序，如果工作大小不属于其他类别之一或需要取消或协作停滞完全支持。

  • concurrency::simple_partitioner
    除工作范围内这样每个范围具有由特定块范围指定迭代的至少数。 此分区程序类型参与负载平衡；但是，运行时不将范围为子范围。 对于每个辅助，运行时检查取消并在完全 _Chunk_size 的迭代之后执行负载平衡。

  • concurrency::static_partitioner
    除工作范围内中 (通常是数目的一个固定数量的可用在循环工作) 的线程。 此分区程序类型可以改善性能，因为它不使用工作窃取和的系统开销较小。 请使用此分区程序类型，当一个并行循环的每次迭代开始内置和统一工作量时，不需要取消支持或转发协作停滞。

警告

parallel_for_each 和 parallel_transform 算法支持使用随机访问迭代器的容器 (如 std::vector) 为静态的，简单且仅关联分区程序。使用双向和向前迭代的使用容器会导致编译时错误。默认值分区程序，auto_partitioner，支持所有这三个迭代器类型。

通常，这些分区程序来使用，但 affinity_partitioner。 不保持状态和运行时不修改大多数分区程序类型。 如下面的示例所示，因此可以在调用站点创建这些分区程序，对象。

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

但是，您必须通过 affinity_partitioner 对象作为非const，左值引用，以便算法可以存储将来的循环的状态可以重用。 下面的示例演示对并行数据集的相同操作多次的基本应用程序。 因为该数组可能包含缓存，使用 affinity_partitioner 改善性能。

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;

int wmain()
{    
    // Create an arry and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    //
    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {        
        parallel_for_each(begin(data), end(data), [](unsigned char& c) {
            c++;
        }, ap);
    }
}

警告

请注意，当修改依赖于协作停滞使用语义 static_partitioner 或 affinity_partitioner的现有代码时。这些分区程序类型不使用负载平衡也不排列窃取，并能更改应用程序的行为。

最好办法确定使用分区程序在任何给定方案是否将测试和测量花费操作完成在有代表性的负载和计算机配置下。 例如，静态分区在只有少量核心的多核计算机上的速度可能会明显加快，但在具有相对较多核心的计算机上则可能会导致速度下降。

[顶级]

并行排序

PPL 提供了三种排序算法：concurrency::parallel_sort、concurrency::parallel_buffered_sort和 concurrency::parallel_radixsort。 这些排序算法，则可将受益并行排序的数据设置。 具体而言，并行排序很有用，则大型数据集时，或者当您使用的计算开销大时比较操作排序您的数据。 这些算法中的每一个排序就地元素。

parallel_sort 和 parallel_buffered_sort 算法是两个基于比较的算法。 即由值比较元素。 parallel_sort 算法没有更多的内存需求，并适用于泛型排序。 parallel_buffered_sort 算法更好地 parallel_sort可以执行，但是，它需要 O(N) 空间。

parallel_radixsort 哈希算法根据。 即使用整数键序列元素。 通过使用键，此算法可以直接计算元素的目标而不是使用比较。 与 parallel_buffered_sort，此算法要求 O(N) 空间。

下表总结了三个并行排序算法的重要属性。

算法

描述

排序结构

排序稳定性

内存要求

复杂时间

迭代器访问

parallel_sort

基于比较的泛型排序。

基于比较 (ascending)

不稳定

无

O((N/P)log(N/P) + 2N((P-1)/P))

随机

parallel_buffered_sort

需要 O 基于比较的筛选器的更快泛型排序 increase(n) 空间。

基于比较 (ascending)

不稳定

需要额外的 O(N) 空间

O((N/P)log(N))

随机

parallel_radixsort

需要 O 基于键的整数排序 increase(n) 空间。

基于哈希

稳定

需要额外的 O(N) 空间

O(N/P)

随机

下图以图形方式显示三个并行排序算法的重要属性。

排序算法比较

这些排序算法的并行遵循规则取消和异常处理。 有关取消和异常处理并发运行时的更多信息，请参见 取消并行算法 和 并发运行时中的异常处理。

提示

这些排序算法的并行支持移动语义。可以定义移动赋值运算符启用交换操作更有效地发生。有关移动语义和移动赋值运算符的更多信息，请参见 Rvalue引用声明:&&和 如何:编写一个移动构造函数。如果未提供个移动赋值运算符也不交换功能，排序算法使用复制构造函数。

下面的基本示例演示如何使用 parallel_sort 排序 int 值 vector。 默认情况下，parallel_sort 使用 std::less 对值进行比较。

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

此示例演示如何提供自定义比较函数。 它使用 std::complex::real 方法对升序的 std::complex<double> 值。

// For this example, ensure that you add the following #include directive:
// #include <complex>

// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
    [](const complex<double>& left, const complex<double>& right) {
        return left.real() < right.real();
    });

// Print a few values.
wcout << "V(0)        = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
   V(0)        = (383,0)
   V(12500000) = (2.1479e+009,0)
   V(24999999) = (4.29497e+009,0)
*/

此示例演示如何提供哈希函数。parallel_radixsort 算法。 此示例对三维点。 点方法对其从引用的距离点。

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

对图，此示例使用设置的相对较小的数据。 可以提高了个矢量的初始大小测试大型性能改进数据设置。

此示例使用 lambda 表达式用作哈希函数。 还可以使用其中一个 std::hash 选件类的内置实现或定义自己的专用化。 如以下示例所示，您还可以使用自定义哈希函数对象，例如：

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));

哈希函数必须返回整数类型 (std::is_integral::value 必须是 true)。 此整型必须转换为类型 size_t。

Dd470426.collapse_all(zh-cn,VS.110).gif选择了排序算法

在大多数情况下，parallel_sort 提供速度和内存性能的最佳平衡。 但是，在中，在添加设置的数据的大小，可用处理器的数目或复杂的比较函数，parallel_buffered_sort 或 parallel_radixsort 可以更佳。 最佳方式确定哪个排序算法使用在任何给定方案是测试和测量花费排序的典型数据在有代表性的计算机配置下。 当选择一个排序的方法时，请注意以下准则。

  • 设置的数据的大小。 在本文档，小型 数据集包含 1,000 个元素，即 数据集包含 10,000 到 100,000 个元素之间，并且，大型 数据集包含多 100,000 个元素。

  • 您的比较函数或哈希函数的工作的执行。

  • 量可用计算资源。

  • 设置的数据的特性。 例如，一个算法可能很好地执行为已关闭的排序数据，但是，不是完全未排序的数据。

  • 块范围。 选项 _Chunk_size 参数指定从并行算法切换到序列化的时间排序实现，则所有排序工作分解为较小单元。 例如，因此，如果您提供 512，对于序列化的实现，工作单元包含 512 或更少的元素的算法切换。 串行实现可以改善整体性能，因为它消除需要并行处理数据的开销。

并行排序小的数据集可能不必要的，因此，即使您具有大量可用计算资源或您比较函数或哈希函数执行相对大量工作。 可以使用 std::sort 功能排序小的数据集。 (parallel_sort 和 parallel_buffered_sort 调用 sort，当您指定大于的块范围数据集；但是，parallel_buffered_sort 必须分配 O(N) 空间，可以使用其他时间由于锁争用或内存分配。)

如果必须保存内存或您的内存分配器受锁争用的限制，请使用 parallel_sort 排序中型数据集。 parallel_sort 不需要额外的空格；其他算法要求 O(N) 空间。

请使用 parallel_buffered_sort 排序中型数据集，并且，当应用程序与其他 O(N) 空间要求。 如果您具有大量计算资源或一昂贵比较函数或哈希函数时，parallel_buffered_sort 尤其有用。

请使用 parallel_radixsort 排序大型数据集，并且，当应用程序与其他 O(N) 空间要求。 parallel_radixsort 尤其有用，将等效比较操作是开销更大的时，或者当两个运算是成本高昂的时。

警告

实现一个好的哈希函数需要知道数据集范围，然后在数据集的每个组件如何将转换为相应的无符号值。由于哈希操作无符号值，请考虑一个不同的排序方法，如果未签名的哈希值不会导致。

下面的示例对同一种比较 sort、parallel_sort、parallel_buffered_sort和 parallel_radixsort 性能设置随机数据。

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

在排序时，在此示例中，假设，分配 O(N) 空间可接受，parallel_radixsort 执行此数据集的最佳此计算机配置。

[顶级]

相关主题

标题

描述

如何：编写 parallel_for 循环

演示如何使用 parallel_for 算法来执行矩阵乘法。

如何：编写 parallel_for_each 循环

显示如何使用 parallel_for_each 算法并行计算 std::array 对象中质数的计数。

如何：使用 parallel_invoke 来编写并行排序运行时

演示如何使用 parallel_invoke 算法来提高 bitonic 排序算法的性能。

如何：使用 parallel_invoke 来执行并行操作

演示如何使用 parallel_invoke 算法来提高对共享数据源执行多项操作的程序的性能。

如何：并行执行映射和减少操作

演示如何使用 parallel_transform 和 parallel_reduce 算法执行映射和减少计数字匹配项文件中的操作。

并行模式库 (PPL)

描述提供了命令性编程模型的 PPL，该模型提升了可伸缩性和易用性，以便开发并发应用程序。

PPL 中的取消操作

说明取消操作在 PPL 中的作用、如何取消并发工作以及如何确定取消任务组的时间。

并发运行时中的异常处理

说明并发运行时中异常处理的作用。

引用

parallel_for 函数

parallel_for_each 函数

parallel_invoke 函数

affinity_partitioner 类

auto_partitioner 类

simple_partitioner 类

static_partitioner 类

parallel_sort 函数

parallel_buffered_sort 函数

parallel_radixsort 函数