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
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;
}
Im folgenden Beispiel werden die Funktionen is_prime und is_carmichael zum Berechnen der Sätze von Primzahlen und Carmichael-Zahlen verwendet.Im Beispiel wird die concurrency::parallel_invoke und concurrency::parallel_for Algorithmen berechnen jeweils parallel festgelegt.Weitere Informationen zu parallelen Algorithmen finden Sie unter Parallele Algorithmen.
In diesem Beispiel wird ein concurrency::concurrent_queue Objekt, das einen Satz von Carmichael Zahlen, da es später dieses Objekt als eine Warteschlange verwenden.Es verwendet ein concurrency::concurrent_vector Objekt, das den Satz von Primzahlen zurückgehalten werden, weil es dieses Set Primfaktor finden später durchlaufen wird.
// 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);
}
});
});
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 concurrency::parallel_for_each Algorithmus zum Durchlaufen der Auflistung von Primzahlen.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;
}
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 Aufgabenparallelität (Concurrency Runtime).
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();
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 und fügen Sie ihn in ein Visual Studio Projekt, oder fügen Sie ihn in eine Datei mit dem Namen Carmichael primes.cpp und führen Sie den folgenden Befehl in ein Visual Studio-Eingabeaufforderungsfenster.
cl.exe /EHsc carmichael-primes.cpp