平行演算法

平行模式程式庫 (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 演算法也支援「巢狀平行處理原則」(Nested Parallelism)。 當某個平行迴圈包含另一個平行迴圈時，執行階段會以對平行執行最有效率的方式，在迴圈主體之間協調處理資源。

parallel_for 演算法具有多個多載版本。 第一個版本會接受起始值、結束值和工作函式 (Lambda 運算式、函式物件或函式指標)。 第二個版本會接受起始值、結束值、間距值和工作函式。 這個函式的第一個版本會使用 1 當做間距值。 其餘的版本採用 Partitioner 物件，可讓您指定 parallel_for 應該如何分割在執行緒中的範圍。 Partitioner 在本文件的 分割工作 一節中有進一步的說明。

您可以將許多 for 迴圈轉換成使用 parallel_for。 不過，parallel_for 演算法與 for 陳述式具有下列差異：

• parallel_for 演算法 parallel_for 不會按照預先決定的順序執行工作。

• parallel_for 演算法不支援任意終止條件。 當反覆運算變數目前的值比 _Last 少一時，parallel_for 演算法就會停止。

• _Index_type 型別參數必須是整數類資料型別。 整數類資料型別可以是帶正負號或不帶正負號。

• 迴圈反覆項目必須是順向。 如果 _Step 參數小於 1，parallel_for 演算法就會擲回 std::invalid_argument 型別的例外狀況。

• parallel_for 演算法的例外狀況處理機制不同於 for 迴圈的例外狀況處理機制。 如果同時在平行迴圈主體中發生多個例外狀況，執行階段只會將其中一個例外狀況傳播至呼叫 parallel_for 的執行緒。 此外，當一個迴圈反覆項目擲回例外狀況時，執行階段不會立即停止整體迴圈， 而是讓迴圈處於取消狀態，而且執行階段會捨棄任何尚未啟動的工作。 如需例外狀況處理和平行演算法的詳細資訊，請參閱並行執行階段的例外狀況處理。

雖然 parallel_for 演算法不支援任意終止條件，不過您可以使用取消來停止所有工作。 如需取消的詳細資訊，請參閱 PPL 中的取消。

注意事項
負載平衡和取消等功能支援所產生的排程成本可能大於平行執行迴圈主體的好處，特別是在迴圈主體相當小時。藉由使用平行迴圈的 Partitioner ，可以降至最低額外負荷。如需詳細資訊，請參閱稍後文件的 分割工作 。

範例

下列範例會示範 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();
   });
}

這個範例 (Example) 會產生下列範例 (Sample) 輸出：

因為 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 演算法可同時處理順向 Iterator 和隨機存取 Iterator，不過隨機存取 Iterator 的執行效能比較好。

範例

下列範例會示範 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
*/

這個範例 (Example) 會產生下列範例 (Sample) 輸出：

因為 parallel_for_each 演算法平行作用於每個項目，所以列印到主控台之值的順序可能會不同。

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

[上方]

parallel_invoke 演算法

concurrency::parallel_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;
}

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

如需使用 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 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 演算法有兩個多載。 第一個多載接受一個項目的範圍和一元運算的函式。 一元的函式可以是採用一個引數、函式物件或型別衍生自 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_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 類別。

範例: 平行執行對應和簡化

對應作業將函式套用至序列的每個值。 取消 作業合併序列中的項目的值。 您可以使用 Standard Template Library (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
*/

如需執行對應並以平行方式取消作業的其他範例，請參閱 如何：平行執行對應和縮減作業。

[上方]

分割工作

若要將對資料來源執行的作業平行化，其中一個必要步驟是將來源「分割」(Partition) 成多個可供多個執行緒並行存取的區段。 Partitioner 指定平行演算法應如何分割在執行緒中的範圍。 如中所說明的先前在文件中，使用 PPL 分成建立初始工作量並使用竊取一個工作竊取演算法和範圍來平衡這些分割的機制的預設，當工作負載不平衡時。 例如，當一個迴圈反覆項目完成某個反覆項目範圍時，執行階段也會將工作從其他執行緒重新分配到該執行緒。 不過，在某些案例中，您可能想要指定更符合為您的問題的一個分割的機制。

parallel_for、 parallel_for_each和 parallel_transform 演算法提供接受其他參數的多載版本，則為 _Partitioner。 這個參數定義除了運作的 Partitioner 型別。 這個 PPL 定義的 Partitioner 種類:

• concurrency::affinity_partitioner
  劃分工作加入至範圍中 (通常是可用在重複工作的數字固定數目的背景工作執行緒)。 這個 Partitioner 型別類似於 static_partitioner，不過，改善便會以範圍對應到背景工作執行緒的快取相似。 這個 Partitioner 型別可以改善效能，並重複執行在相同的資料集多次 (例如在迴圈中的迴圈) 和資料相容的快取。 這個 Partitioner 不完全參與取消。 它也不會使用合作式封鎖語意也不能與具有向前相依性的平行迴圈一起使用。

• concurrency::auto_partitioner
  劃分工作加入至範圍中 (通常是可用在重複工作的數字初始數目的背景工作執行緒)。 執行階段使用這個型別為預設，當呼叫採用 _Partitioner 參數之的多載的平行演算法時。 每個範圍可以分為子範圍和讓負載平衡發生。 當一個工作的範圍完成時，執行階段也會將工作的小範圍從其他執行緒重新分配到該執行緒。 請使用這個 Partitioner，如果您的工作負載不屬於其他分類的其中一個您取消或合作式封鎖需要的完整支援。

• concurrency::simple_partitioner
  劃分運作輸入範圍，每個範圍是由指定的區塊大小指定反覆項目的數目。 這個 Partitioner 型別參與負載平衡；不過，執行階段不區分範圍的子範圍。 對於每個背景工作，取消的執行階段負載平衡在 _Chunk_size 反覆運算後的檢查並執行完成。

• concurrency::static_partitioner
  劃分工作加入至範圍中 (通常是可用在重複工作的數字固定數目的背景工作執行緒)。 這個 Partitioner 型別可以改善效能，因為它不會使用工作竊取也較低額外負荷。 請使用這個 Partitioner 型別，在平行迴圈反覆項目執行一個固定且一致的工作量時，並不會取消需要支援也不轉送合作式封鎖。

一般來說，這些 Partitioner 以相同方法來使用，除了 affinity_partitioner。 大部分的 Partitioner 型別不會維護狀態且執行階段不會修改。 如下列範例所示，因此您可以在呼叫位置建立這些 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);
    }
}

判斷在任何指定情節中是否使用 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) 空間。

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

演算法	說明	排序機制	排序穩定	記憶體需求	時間複雜度	Iterator 存取
parallel_sort	通用以比較為基礎的排序。	以比較為基礎 (遞增)	不穩定。	無	O((N/P)log(N/P) + 2N((P-1)/P))	隨機
parallel_buffered_sort	要求的運算速度的通用以比較為基礎的排序需要 O(N) 空間。	以比較為基礎 (遞增)	不穩定。	需要額外的 O(N) 空間	O((N/P)log(N))	隨機
parallel_radixsort	整數運算的 Key 為基礎的排序需要 (N) 空間。	以雜湊為基礎	穩定	需要額外的 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<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_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 演算法改善雙調排序演算法的效能。
如何：使用 parallel_invoke 執行平行作業	顯示如何使用 parallel_invoke 演算法，改善對共用資料來源執行多個作業的程式效能。
如何：平行執行對應和縮減作業	示範如何使用 parallel_transform 和 parallel_reduce 演算法執行對應和減少計算字數事件在檔案的作業。
平行模式程式庫 (PPL)	描述 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 函式