Практическое руководство. Использование параллельных контейнеров для повышения эффективности
В этом разделе показано, как использовать параллельные контейнеры для эффективного хранения данных и доступа к данным в параллельном режиме.
Код примера выполняет параллельное вычисление набора простых чисел и чисел Кармайкла. Затем для каждого числа Кармайкла вычисляются простые множители этого числа.
Пример
В следующем примере показана функция 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();
}
В данном примере получается следующий результат.
Компиляция кода
Скопируйте код примера и вставьте его в проект Visual Studio или в файл с именем carmichael-primes.cpp, затем выполните в окне командной строки Visual Studio следующую команду.
cl.exe /EHsc carmichael-primes.cpp