并行算法

项目
06/09/2015

并行模式库 (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 中的取消操作。

备注

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

示例

下面的示例显示了 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 循环。

[Top]

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 算法既可用于向前迭代器，又可用于随机访问迭代器，但此算法更适用于随机访问迭代器。

示例

下面的示例显示了 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), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

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

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

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

[Top]

parallel_invoke 算法

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

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

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

示例

下面的示例显示了 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 来执行并行操作。

[Top]

parallel_transform 和 parallel_reduce 算法

concurrency::parallel_transform concurrency::parallel_reduce 算法和分别 STL 算法和 std::transform std::accumulate的并行版本，即。并发运行时版本行为与 STL 版本，但操作命令不是确定的，因为它们并行执行。请使用这些算法，当您具有足够大从并行处理获取性能和伸缩性优点的集一起使用时。

重要

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

parallel_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 提供输出的迭代器必须完全声明输入迭代器或根本不重叠。如果输入和输出迭代器重叠部分，则此算法是未指定的行为。

parallel_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。

示例: 并行执行映射和降低

映射操作将函数应用于序列的每个值。化简操作合并序列的元素分为一个值。可以使用标准模板库 (STL) (STL) std::transform std::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
*/

有关并行执行映射和化简操作的另一个示例，请参见如何：并行执行映射和减少操作。

[Top]

分区工作

若要对数据源操作进行并行化，其中一个必要步骤是将源分区为可由多个线程同时访问的多个部分。分区程序并行算法指定应如何对线程之间的范围。下面演示前面在文档，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;
using namespace std;

int wmain()
{
    // Create an array 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的现有代码。这些分区程序类型不使用负载平衡也不排列功能，并且可以更改应用程序的行为。

确定在任何给定方案中是否使用分区的最佳方式是：体验并度量操作在有代表性的负载和计算机配置下要花多长时间完成。例如，静态分区在只有少量核心的多核计算机上的速度可能会明显加快，但在具有相对较多核心的计算机上则可能会导致速度下降。

[Top]

并行排序

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	基于泛型比较进行排序。	基于比较 (登高)	不稳定	无	O((N/P)log(N/P) + 2N((P-1)/P))	随机
parallel_buffered_sort	要求操作的更快基于泛型比较的顺序排列 (或者按 Ctrl+R 空间。	基于比较 (登高)	不稳定	O(N) 需要额外的空间	O((N/P)log(N))	随机
parallel_radixsort	O 需要整数的基于键的排序 (或者按 Ctrl+R 空间。	基于哈希	稳定	O(N) 需要额外的空间	O(N/P)	随机

下面图以图形方式显示三种并行排序算法的基本属性。

排序算法比较

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

提示

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

下面的基本示例演示如何使用 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<双倍行距> 升序排序值。

// 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。

选择排序算法

在许多情况下，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 执行此数据集的最佳此计算机上配置。

[Top]

标题	说明
如何：编写 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 中的作用、如何取消并发工作以及如何确定取消任务组的时间。
并发运行时中的异常处理	说明并发运行时中异常处理的作用。