Como: Use os recipientes paralelas para aumentar a eficiência
Este tópico mostra como usar o paralelos recipientes para armazenar de forma eficiente e acessar dados em paralelo.
O código de exemplo calcula o conjunto de prime e números de Carmichael em paralelo. Em seguida, para cada número de Carmichael, o código calcula os fatores primos desse número.
Exemplo
A exemplo a seguir mostra a is_prime função, que determina se um valor de entrada é um número primo, e o is_carmichael a função, que determina se o valor de entrada é um número de 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;
}
O exemplo a seguir usa a is_prime e is_carmichael funções para calcular os conjuntos de prime e números de Carmichael. O exemplo usa o Concurrency::parallel_invoke e Concurrency::parallel_for um conjunto de algoritmos para calcular cada em paralelo. Para obter mais informações sobre algoritmos paralelos, consulte Algoritmos paralelos.
Este exemplo usa um Concurrency::concurrent_queue números de objeto para armazenar o conjunto de Carmichael, pois posteriormente usará esse objeto como uma fila de trabalho. Ele usa um Concurrency::concurrent_vector o objeto para armazenar o conjunto de números primos, porque ela irá iterar este conjunto de fatores primos de localizar posteriormente.
// 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);
}
});
});
A exemplo a seguir mostra a prime_factors_of a função, que usa a divisão de avaliação para localizar todos os fatores primos de determinado valor.
Essa função usa o Concurrency::parallel_for_each o algoritmo para iterar na coleção dos números primos. O concurrent_vector objeto permite que o loop paralelo adicionar simultaneamente os fatores primos do resultado.
// 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(primes.begin(), primes.end(), [&](int prime)
{
if (prime <= max)
{
if ((n % prime) == 0)
prime_factors.push_back(prime);
}
});
return prime_factors;
}
Esse exemplo processa cada elemento na fila de números de Carmichael, chamando o prime_factors_of a função para calcular seus fatores principais. Ele usa um grupo de tarefas para realizar esse trabalho em paralelo. Para obter mais informações sobre grupos de tarefas, consulte Paralelismo de tarefas (Runtime de simultaneidade).
Este exemplo imprime os fatores primos para cada número de Carmichael se esse número tiver mais de quatro fatores primos.
// 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(prime_factors.begin(), prime_factors.end());
wstringstream ss;
ss << L"Prime factors of " << carmichael << L" are:";
for_each (prime_factors.begin(), prime_factors.end(),
[&](int prime_factor) { ss << L' ' << prime_factor; });
ss << L'.' << endl;
wcout << ss.str();
}
});
}
// Wait for the task group to finish.
tasks.wait();
O código a seguir mostra o exemplo completo, que utiliza recipientes paralelas para computar os fatores primos dos números de Carmichael.
// 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(primes.begin(), primes.end(), [&](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(prime_factors.begin(), prime_factors.end());
wstringstream ss;
ss << L"Prime factors of " << carmichael << L" are:";
for_each (prime_factors.begin(), prime_factors.end(),
[&](int prime_factor) { ss << L' ' << prime_factor; });
ss << L'.' << endl;
wcout << ss.str();
}
});
}
// Wait for the task group to finish.
tasks.wait();
}
Este exemplo produz a saída de exemplo a seguir.
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.
Compilando o código
Copie o código de exemplo e colá-lo em um Visual Studio do projeto, ou colá-lo em um arquivo que é chamado carmichael primes.cpp e, em seguida, execute o seguinte comando um Visual Studio 2010 janela do Prompt de comando.
cl.exe /EHsc carmichael-primes.cpp
Consulte também
Referência
Conceitos
Paralelo recipientes e objetos
Paralelismo de tarefas (Runtime de simultaneidade)