windows C++ 并行编程-并行容器和对象

并行模式库 (PPL) 包括几个容器和对象，这些容器和对象提供对其元素的线程安全访问。

并发容器提供对最重要操作的并发安全访问。 在这里，并发安全意味着指针或迭代器始终有效。 它不保证元素初始化或特定的遍历顺序。 这些容器的功能与 C++ 标准库提供的功能类似。 例如，concurrency::concurrent_vector 类与 std::vector 类类似，但 concurrent_vector 类允许并行追加元素。 如果并行代码需要对同一容器进行读写访问，请使用并发容器。

并发对象在组件之间并发共享。 并行计算并发对象状态的进程生成的结果与连续计算相同状态的另一个进程相同。 concurrency::combinable 类是并发对象类型的一个示例。 combinable 类允许并行执行计算，然后将这些计算组合成最终结果。 如果要使用同步机制（例如互斥体）来同步对共享变量或资源的访问，请使用并发对象。

示例代码并行计算质数和卡迈克尔数的集合。 然后，对于每个卡迈克尔数，代码计算该数的质因子。

示例：确定输入值是否为质数

下面的示例展示了 is_prime 函数，它确定输入值是否为质数，以及 is_carmichael 函数，它确定输入值是否为卡迈克尔数。

// 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;
}

// Determines whether the input value is a Carmichael number.
bool is_carmichael(const int n) 
{
   if (n < 2) 
      return false;

   int k = n;
   for (int i = 2; i <= k / i; ++i) 
   {
      if (k % i == 0) 
      {
         if ((k / i) % i == 0) 
            return false;
         if ((n - 1) % (i - 1) != 0)
            return false;
         k /= i;
         i = 1;
      }
   }
   return k != n && (n - 1) % (k - 1) == 0;
}

示例：计算质数和卡迈克尔数

下面的示例使用 is_prime 和 is_carmichael 函数来计算质数和卡迈克尔数的集合。 该示例使用 concurrency::parallel_invoke 和 concurrency::parallel_for 算法并行计算每个集。 

此示例使用 concurrency::concurrent_queue 对象保存卡迈克尔数集，因为它稍后会将该对象用作工作队列。 它使用 concurrency::concurrent_vector 对象来保存质数集，因为它稍后将循环访问此集以查找质因子。

// The maximum number to test.
const int max = 10000000;

// Holds the Carmichael numbers that are in the range [0, max).
concurrent_queue<int> carmichaels;

// Holds the prime numbers that are in the range  [0, sqrt(max)).
concurrent_vector<int> primes;

// Generate the set of Carmichael numbers and the set of prime numbers
// in parallel.
parallel_invoke(
   [&] {
      parallel_for(0, max, [&](int i) {
         if (is_carmichael(i)) {
            carmichaels.push(i);
         }
      });
   },
   [&] {
      parallel_for(0, int(sqrt(static_cast<double>(max))), [&](int i) {
         if (is_prime(i)) {
            primes.push_back(i);
         }
      });
   });

示例：查找给定值的所有质因子

以下示例展示 prime_factors_of 函数，该函数使用试除法查找给定值的所有质因子。

此函数使用 concurrency::parallel_for_each 算法循环访问质数集合。 该 concurrent_vector 对象使并行循环能够并发地向结果中添加质数。

// Finds all prime factors of the given value.
concurrent_vector<int> prime_factors_of(int n, 
   const concurrent_vector<int>& primes)
{
   // Holds the prime factors of n.
   concurrent_vector<int> prime_factors;
   
   // Use trial division to find the prime factors of n.
   // Every prime number that divides evenly into n is a prime factor of n.
   const int max = sqrt(static_cast<double>(n));
   parallel_for_each(begin(primes), end(primes), [&](int prime)
   {
      if (prime <= max)
      {         
         if ((n % prime) == 0)
            prime_factors.push_back(prime);
      }
   });

   return prime_factors;
}

 示例：处理卡迈克尔数队列中的每个元素

此示例通过调用 prime_factors_of 函数计算其质因子，来处理卡迈克尔数队列中的每个元素。 它使用任务组，以并行方式实现此操作。 有关任务组的详细信息，请参阅任务并行。

此示例为每个具有四个以上质因子的卡迈克尔数打印其质因子。

// Use a task group to compute the prime factors of each 
// Carmichael number in parallel.
task_group tasks;

int carmichael;
while (carmichaels.try_pop(carmichael))
{
   tasks.run([carmichael,&primes] 
   {
      // Compute the prime factors.
      auto prime_factors = prime_factors_of(carmichael, primes);

      // For brevity, print the prime factors for the current number only
      // if there are more than 4.
      if (prime_factors.size() > 4)
      {
         // Sort and then print the prime factors.
         sort(begin(prime_factors), end(prime_factors));

         wstringstream ss;
         ss << L"Prime factors of " << carmichael << L" are:";

         for_each (begin(prime_factors), end(prime_factors), 
            [&](int prime_factor) { ss << L' ' << prime_factor; });
         ss << L'.' << endl;

         wcout << ss.str();
      }
   });
}

// Wait for the task group to finish.
tasks.wait();

示例：完成的并行容器代码示例

以下代码展示了完整示例，该示例使用并行容器来计算卡迈克尔数的质因子。

// carmichael-primes.cpp
// compile with: /EHsc
#include <ppl.h>
#include <concurrent_queue.h>
#include <concurrent_vector.h>
#include <iostream>
#include <sstream>

using namespace concurrency;
using namespace std;

// 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;
}

// Determines whether the input value is a Carmichael number.
bool is_carmichael(const int n) 
{
   if (n < 2) 
      return false;

   int k = n;
   for (int i = 2; i <= k / i; ++i) 
   {
      if (k % i == 0) 
      {
         if ((k / i) % i == 0) 
            return false;
         if ((n - 1) % (i - 1) != 0)
            return false;
         k /= i;
         i = 1;
      }
   }
   return k != n && (n - 1) % (k - 1) == 0;
}

// Finds all prime factors of the given value.
concurrent_vector<int> prime_factors_of(int n, 
   const concurrent_vector<int>& primes)
{
   // Holds the prime factors of n.
   concurrent_vector<int> prime_factors;
   
   // Use trial division to find the prime factors of n.
   // Every prime number that divides evenly into n is a prime factor of n.
   const int max = sqrt(static_cast<double>(n));
   parallel_for_each(begin(primes), end(primes), [&](int prime)
   {
      if (prime <= max)
      {         
         if ((n % prime) == 0)
            prime_factors.push_back(prime);
      }
   });

   return prime_factors;
}

int wmain()
{
   // The maximum number to test.
   const int max = 10000000;
   
   // Holds the Carmichael numbers that are in the range [0, max).
   concurrent_queue<int> carmichaels;

   // Holds the prime numbers that are in the range  [0, sqrt(max)).
   concurrent_vector<int> primes;
   
   // Generate the set of Carmichael numbers and the set of prime numbers
   // in parallel.
   parallel_invoke(
      [&] {
         parallel_for(0, max, [&](int i) {
            if (is_carmichael(i)) {
               carmichaels.push(i);
            }
         });
      },
      [&] {
         parallel_for(0, int(sqrt(static_cast<double>(max))), [&](int i) {
            if (is_prime(i)) {
               primes.push_back(i);
            }
         });
      });

   // Use a task group to compute the prime factors of each 
   // Carmichael number in parallel.
   task_group tasks;

   int carmichael;
   while (carmichaels.try_pop(carmichael))
   {
      tasks.run([carmichael,&primes] 
      {
         // Compute the prime factors.
         auto prime_factors = prime_factors_of(carmichael, primes);

         // For brevity, print the prime factors for the current number only
         // if there are more than 4.
         if (prime_factors.size() > 4)
         {
            // Sort and then print the prime factors.
            sort(begin(prime_factors), end(prime_factors));

            wstringstream ss;
            ss << L"Prime factors of " << carmichael << L" are:";

            for_each (begin(prime_factors), end(prime_factors), 
               [&](int prime_factor) { ss << L' ' << prime_factor; });
            ss << L'.' << endl;

            wcout << ss.str();
         }
      });
   }

   // Wait for the task group to finish.
   tasks.wait();
}

输出如下:

Prime factors of 9890881 are: 7 11 13 41 241.
Prime factors of 825265 are: 5 7 17 19 73.
Prime factors of 1050985 are: 5 13 19 23 37.