如何：使用并行容器提高效率
此主题展示如何使用并行容器高效地并行存储和访问数据。
示例代码并行计算质数和卡迈克尔数的集合。 然后，对于每个卡迈克尔数，代码计算该数的质因子。
示例：确定输入值是否为质数
下面的示例展示了 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.
编译代码
复制示例代码，并将它粘贴到 Visual Studio 项目中，或粘贴到名为 carmichael-primes.cpp 的文件中，再在 Visual Studio 命令提示符窗口中运行以下命令。
cl.exe /EHsc carmichael-primes.cpp
另请参阅
并行容器和对象
任务并行
concurrent_vector 类
concurrent_queue 类
parallel_invoke 函数
parallel_for 函数
task_group 类
反馈
即将发布：在整个 2024 年，我们将逐步淘汰作为内容反馈机制的“GitHub 问题”，并将其取代为新的反馈系统。 有关详细信息，请参阅：https://aka.ms/ContentUserFeedback。
提交和查看相关反馈