平行演算法

平行模式連結庫 （PPL） 提供可同時對數據收集執行工作的演算法。 這些演算法類似於 C++ 標準連結庫所提供的演算法。

平行演算法是由並行運行時間中的現有功能所組成。 例如， concurrency：:p arallel_for 演算法會使用 並行：：structured_task_group 對象來執行平行迴圈反覆運算。 根據 parallel_for 可用的運算資源數目，演算法分割會以最佳方式運作。

區段

• parallel_for演算法

• parallel_for_each演算法

• parallel_invoke演算法

• parallel_transform和parallel_reduce演算法

  • parallel_transform演算法

  • parallel_reduce演算法

  • 範例：以平行的方式執行對應和縮減

• 數據分割工作

• 平行排序

  • 選擇排序演算法

parallel_for演算法

並行 ：:p arallel_for 演算法會重複執行相同的工作。 每個工作都是由反覆專案值參數化。 當您有循環主體不會在該迴圈反覆專案之間共用資源的循環主體時，此演算法很有用。

演算法會 parallel_for 以最佳方式分割平行執行的工作。 它會使用工作竊取演算法和範圍竊取，在工作負載不平衡時平衡這些分割區。 當一個迴圈反覆專案合作封鎖時，運行時間會將指派給目前線程的反覆專案範圍轉散發給其他線程或處理器。 同樣地，當線程完成一系列反覆專案時，運行時間會將工作從其他線程轉散發至該線程。 此 parallel_for 演算法也支援 巢狀平行處理原則。 當一個平行迴圈包含另一個平行迴圈時，運行時間會以有效率的方式協調迴圈主體之間的處理資源，以便平行執行。

演算法 parallel_for 有數個多載版本。 第一個版本會採用開始值、結束值和工作函式（Lambda 運算式、函式物件或函式指標）。 第二個版本會採用開始值、結束值、要逐步執行的值，以及工作函式。 此函式的第一個版本使用 1 作為步驟值。 其餘版本會採用數據分割器物件，這可讓您指定線程之間分割範圍的方式 parallel_for 。 分割器會在本檔分割工作一節中更詳細地說明。

您可以將許多 for 循環轉換成使用 parallel_for。 不過，演算法 parallel_for 會以下列方式與 for 語句不同：

• 演算法parallel_forparallel_for不會以預先決定的順序執行工作。

• 演算法 parallel_for 不支援任意終止條件。 當反覆運算變數的目前值小於 last時，演算法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();
   });
}

此範例會產生下列範例輸出：

1 2 4 3 5

parallel_for因為演算法會以平行的方式處理每個專案，因此值列印到主控台的順序會有所不同。

如需使用 parallel_for 演算法的完整範例，請參閱 如何：撰寫parallel_for迴圈。

[靠上]

parallel_for_each演算法

concurrency：:p arallel_for_each 演算法會在反覆容器上執行工作，例如平行C++標準連結庫所提供的容器。 它會使用演算法所使用的相同數據分割邏輯 parallel_for 。

此 parallel_for_each 演算法類似於 C++標準連結庫 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
*/

此範例會產生下列範例輸出：

4 5 1 2 3

parallel_for_each因為演算法會以平行的方式處理每個專案，因此值列印到主控台的順序會有所不同。

如需使用 parallel_for_each 演算法的完整範例，請參閱 如何：撰寫parallel_for_each迴圈。

[靠上]

parallel_invoke演算法

concurrency ：:p arallel_invoke 演算法會平行執行一組工作。 它不會傳回，直到每個工作完成為止。 當您有數個想要同時執行的獨立工作時，此演算法很有用。

此 parallel_invoke 演算法會採用其參數一系列的工作函式（Lambda 函式、函式物件或函式指標）。 演算法 parallel_invoke 會多載，以採用兩到十個參數。 您傳遞的每個 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;
}

這個範例會產生下列輸出：

108 11.2 HelloHello

如需使用 parallel_invoke 演算法的完整範例，請參閱 如何：使用parallel_invoke撰寫平行排序例程 和 如何：使用parallel_invoke執行平行作業。

[靠上]

parallel_transform和parallel_reduce演算法

concurrency：:p arallel_transform 和 concurrency：:p arallel_reduce 演演算法分別是 C++標準連結庫演算法 std：：transform 和 std：：accumulate 的平行版本。 並行運行時間版本的行為就像C++標準連結庫版本，不同之處在於作業順序不會因為平行執行而決定。 當您使用足以讓效能和延展性優勢平行處理的集合時，請使用這些演算法。

重要

parallel_transform和 parallel_reduce 演算法僅支援隨機存取、雙向和轉送反覆運算器，因為這些反覆運算器會產生穩定的記憶體位址。 此外，這些反覆運算器必須產生非const l 值。

parallel_transform演算法

您可以使用 parallel transform 演算法來執行許多資料平行處理作業。 例如，您可以：

• 調整影像的亮度，並執行其他影像處理作業。

• 加總或採用兩個向量之間的點乘積，並在向量上執行其他數值計算。

• 執行 3D 光線追蹤，其中每個反覆專案是指必須轉譯的一個圖元。

下列範例顯示用來呼叫 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 有兩個多載。 第一個多載會採用一個輸入範圍和一元函式。 一元函式可以是 Lambda 運算式，其接受一個自變數、函式物件或衍生自 unary_function的類型。 第二個多載會採用兩個輸入範圍和二進位函式。 二進位函式可以是採用兩個自變數、函式物件或衍生自 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      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.
*/

在許多情況下，您可以將 演算法與 concurrency：：combinable 類別一起使用，視為parallel_reduce速記parallel_for_each。

範例：以平行的方式執行對應和縮減

對應作業會將函式套用至序列中的每個值。 歸納作業會將序列的項目結合成一個值。 您可以使用C++標準連結庫 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
*/

如需另一個平行執行對應和縮減作業的範例，請參閱 如何：以平行方式執行對應和縮減作業。

[靠上]

數據分割工作

若要平行處理數據源上的作業，基本步驟是將 來源分割 成多個區段，讓多個線程可以同時存取。 數據分割器會指定平行演算法在線程之間分割範圍的方式。 如本檔先前所述，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());
}

不過，您必須將 對象當做非const l 值參考傳遞affinity_partitioner，讓演算法可以儲存狀態以供未來迴圈重複使用。 下列範例示範一個基本應用程式，該應用程式會平行對數據集執行相同作業多次。 的 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的現有程序代碼時，請小心。 這些數據分割器類型不會使用負載平衡或範圍竊取，因此可以改變應用程式的行為。

判斷是否在任何指定案例中使用分割器的最佳方式，是實驗和測量在代表性負載和計算機設定下完成作業所需的時間。 例如，在只有幾個核心的多核心電腦上，靜態分割可能會帶來顯著的加速效果，但在有較多核心的電腦上，則可能拖慢速度。

[靠上]

平行排序

PPL 提供三種排序演算法：concurrency：:p arallel_sort、concurrency：:p arallel_buffered_sort 和 concurrency：:p arallel_radixsort。 當您有數據集可受益於平行排序時，這些排序演算法很有用。 特別是，當您擁有大型數據集，或使用計算成本高昂的比較作業來排序數據時，平行排序會很有用。 每個演算法都會就地排序元素。

parallel_sort和 parallel_buffered_sort 演算法都是以比較為基礎的演算法。 也就是說，它們會依值比較元素。 演演算法 parallel_sort 沒有額外的記憶體需求，而且適用於一般用途的排序。 演演算法 parallel_buffered_sort 的執行效能可能比 更好 parallel_sort，但需要 O（N） 空間。

演算法 parallel_radixsort 是以哈希為基礎。 也就是說，它會使用整數索引鍵來排序專案。 藉由使用索引鍵，此演算法可以直接計算專案的目的地，而不是使用比較。 如同 parallel_buffered_sort，此演算法需要 O（N） 空間。

下表摘要說明三種平行排序演算法的重要屬性。

演算法	描述	排序機制	排序穩定性	記憶體需求	時間複雜度	Iterator 存取
parallel_sort	一般用途比較型排序。	以比較為基礎的 （遞增）	不穩定	無	O（N/P）記錄（N/P） + 2N（P-1）/P））	隨機
parallel_buffered_sort	更快速的一般用途比較型排序，需要 O（N） 空間。	以比較為基礎的 （遞增）	不穩定	需要額外的 O（N） 空間	O（N/P）記錄（N））	隨機
parallel_radixsort	需要 O（N） 空間的整數索引鍵型排序。	雜湊式	穩定	需要額外的 O（N） 空間	O（N/P）	隨機

下圖以圖形方式顯示三種平行排序演算法的重要屬性。

這些平行排序演算法遵循取消和例外狀況處理的規則。 如需並行運行時間中取消和例外狀況處理的詳細資訊，請參閱 取消平行演算法 和 例外狀況處理。

提示

這些平行排序演算法支持行動語意。 您可以定義移動指派運算符，讓交換作業更有效率地發生。 如需移動語意和移動指派運算子的詳細資訊，請參閱右值參考宣告子：&&和移動建構函式和移動指派運算符（C++）。 如果您沒有提供移動指派運算符或交換函式，排序演算法會使用複製建構函式。

下列基本範例示範如何使用 parallel_sort 來排序 vector int 值。 根據預設， 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 式提供給演算法。 此範例會排序 3D 點。 這些點會根據其與參考點的距離來排序。

// 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_sortsort指定大於數據集的區塊大小時呼叫 ;不過，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 當對等比較作業更昂貴或兩個作業都昂貴時，特別有用。

警告

實作良好的哈希函式需要您知道數據集範圍，以及數據集中的每個元素如何轉換成對應的不帶正負號值。 因為哈希作業適用於不帶正負號的值，所以如果無法產生不帶正負號的哈希值，請考慮不同的排序策略。

下列範例會比較 、parallel_sort、 parallel_buffered_sort和 parallel_radixsort 與 相同大型隨機數據集的效能sort。

// 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函式