Procedura: utilizzare i contenitori paralleli per aumentare l'efficienza
In questo argomento viene illustrato come utilizzare i contenitori paralleli per archiviare e accedere ai dati in parallelo in modo efficiente.
Nel codice di esempio viene calcolato il set di numeri primi e di Carmichael in parallelo. Per ogni numero di Carmichael vengono quindi calcolati i fattori primi di tale numero.
Esempio
Nell'esempio seguente viene illustrata la funzione is_prime che determina se il valore di input è un numero primo e la funzione is_carmichael che determina se il valore di input è un numero di 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;
}
Nell'esempio seguente vengono utilizzate le funzioni is_prime e is_carmichael per calcolare i set di numeri primi e di Carmichael. Nell'esempio vengono utilizzati gli algoritmi Concurrency::parallel_invoke e Concurrency::parallel_for per calcolare ogni set in parallelo. Per ulteriori informazioni sugli algoritmi paralleli, vedere Algoritmi paralleli.
In questo esempio viene utilizzato un oggetto Concurrency::concurrent_queue per contenere il set di numeri di Carmichael poiché tale oggetto verrà utilizzato come coda di lavoro. Viene utilizzato un oggetto Concurrency::concurrent_vector per contenere il set di numeri primi poiché sarà necessario scorrere questo set per trovare i fattori primi.
// 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);
}
});
});
Nell'esempio seguente viene illustrata la funzione prime_factors_of che utilizza la divisione semplice (trial division) per trovare tutti i fattori primi del valore specificato.
Questa funzione utilizza l'algoritmo Concurrency::parallel_for_each per scorrere l'insieme di numeri primi. L'oggetto concurrent_vector consente al ciclo parallelo di aggiungere contemporaneamente i fattori primi al risultato.
// 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;
}
In questo esempio viene elaborato ogni elemento nella coda dei numeri di Carmichael chiamando la funzione prime_factors_of per calcolarne i relativi fattori primi. Viene utilizzato un gruppo di attività per eseguire questo lavoro in parallelo. Per ulteriori informazioni sui gruppi di attività, vedere Parallelismo delle attività (runtime di concorrenza).
In questo esempio vengono stampati i fattori primi per ogni numero di Carmichael se tale numero dispone di più di quattro fattori primi.
// 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();
Nel codice seguente viene illustrato l'esempio completo che utilizza i contenitori paralleli per calcolare i fattori primi dei numeri di 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();
}
Questo esempio produce l'output seguente:
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.
Compilazione del codice
Copiare il codice di esempio e incollarlo in un progetto di Visual Studio o incollarlo in un file denominato carmichael-primes.cpp, quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio 2010.
cl.exe /EHsc carmichael-primes.cpp
Vedere anche
Riferimenti
Concetti
Contenitori e oggetti paralleli
Parallelismo delle attività (runtime di concorrenza)