Gewusst wie: Erhöhen der Effizienz mithilfe von parallelen Containern
In diesem Thema wird aufgezeigt, wie parallele Container verwendet werden, um Daten effizient zu speichern und parallel auf sie zuzugreifen.
Im Beispielcode werden der Satz von Primzahlen und Carmichael-Zahlen parallel berechnet. Anschließend berechnet der Code für jede Carmichael-Zahl die Primfaktoren dieser Zahl.
Beispiel: Ermitteln, ob ein Eingabewert eine Primzahl ist
Im folgenden Beispiel wird die is_prime-Funktion gezeigt, durch die bestimmt wird, ob ein Eingabewert eine Primzahl ist, und die is_carmichael-Funktion, durch die bestimmt wird, ob der Eingabewert eine Carmichael-Zahl ist.
// 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;
}
Beispiel: Berechnen von Prime- und Carmichael-Zahlen
Im folgenden Beispiel werden die Funktionen is_prime und is_carmichael zum Berechnen der Sätze von Primzahlen und Carmichael-Zahlen verwendet. Im Beispiel werden die "concurrency::p arallel_invoke " und "concurrency::p arallel_for "-Algorithmen verwendet, um jeden Satz parallel zu berechnen. Weitere Informationen zu parallelen Algorithmen finden Sie unter Parallel-Algorithmen.
In diesem Beispiel wird ein Parallelitätsobjekt::concurrent_queue-Objekt verwendet, um den Satz von Carmichael-Zahlen zu speichern, da es dieses Objekt später als Arbeitswarteschlange verwendet. Es verwendet ein Parallelitätsobjekt::concurrent_vector Objekt, um den Satz von Primzahlen zu speichern, da er später durchlaufen wird, um Primfaktoren zu finden.
// 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);
}
});
});
Beispiel: Suchen aller Prime-Faktoren eines bestimmten Werts
Im folgenden Beispiel wird die prime_factors_of-Funktion veranschaulicht, von der die Versuchsdivision verwendet wird, um alle Primfaktoren des angegebenen Werts zu suchen.
Diese Funktion verwendet die Parallelität::p arallel_for_each Algorithmus, um die Sammlung von Primzahlen zu durchlaufen. Das concurrent_vector-Objekt macht es möglich, dass die parallele Schleife dem Ergebnis gleichzeitig Primfaktoren hinzufügen kann.
// 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;
}
Beispiel: Verarbeitet jedes Element in der Warteschlange von Carmichael-Zahlen.
In diesem Beispiel wird jedes Element in der Warteschlange von Carmichael-Zahlen verarbeitet, indem zum Berechnen der Primfaktoren die prime_factors_of-Funktion aufgerufen wird. Es führt diese Arbeit mithilfe einer Aufgabengruppe parallel aus. Weitere Informationen zu Aufgabengruppen finden Sie unter Task Parallelism.
In diesem Beispiel werden die Primfaktoren für jede Carmichael-Zahl gedruckt, wenn diese Zahl mehr als vier Primfaktoren hat.
// 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();
Beispiel: Fertiges Beispiel für parallelen Containercode
Im folgenden Code wird das vollständige Beispiel veranschaulicht, in dem parallele Container zum Berechnen der Primfaktoren der Carmichael-Zahlen verwendet werden.
// 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();
}
Dieses Beispiel erzeugt die folgende Beispielausgabe.
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.
Kompilieren des Codes
Kopieren Sie den Beispielcode, fügen Sie ihn in ein Visual Studio-Projekt ein, oder fügen Sie ihn in eine Datei ein, die benannt carmichael-primes.cpp ist, und führen Sie dann den folgenden Befehl in einem Visual Studio-Eingabeaufforderungsfenster aus.
cl.exe /EHsc carmichael-primes.cpp
Siehe auch
Parallele Container und Objekte
Task-Parallelität
concurrent_vector-Klasse
concurrent_queue-Klasse
parallel_invoke-Funktion
parallel_for-Funktion
task_group-Klasse