방법: 병렬 컨테이너를 사용하여 효율성 향상
이 항목에서는 병렬 컨테이너를 사용하여 데이터를 병렬로 효율적으로 저장하고 액세스하는 방법을 보여 줍니다.
예제 코드는 소수 및 카마이클 숫자 집합을 병렬로 계산합니다. 그런 다음, 각 카마이클 번호에 대해 코드는 해당 숫자의 주요 요소를 계산합니다.
예: 입력 값이 소수인지 확인
다음 예제에서는 입력 값이 is_prime 소수인지 여부를 결정하는 함수와 is_carmichael 입력 값이 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_carmichael 함수를 사용하여 is_prime 소수 및 카마이클 숫자 집합을 계산합니다. 이 예제에서는 concurrency::p arallel_invoke 및 concurrency::p arallel_for 알고리즘을 사용하여 각 집합을 병렬로 계산합니다. 병렬 알고리즘에 대한 자세한 내용은 병렬 알고리즘을 참조 하세요.
이 예제에서는 동시성::concurrent_queue 개체를 사용하여 나중에 해당 개체를 작업 큐로 사용하기 때문에 Carmichael 숫자 집합을 저장합니다. 동시성::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 줍니다.
이 함수는 동시성::p arallel_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 하여 Carmichael 숫자 큐의 각 요소를 처리하여 주요 요소를 계산합니다. 작업 그룹을 사용하여 이 작업을 병렬로 수행합니다. 작업 그룹에 대한 자세한 내용은 작업 병렬 처리를 참조하세요.
이 예제에서는 해당 숫자에 4개 이상의 주요 요소가 있는 경우 각 카마이클 번호의 주요 요소를 인쇄합니다.
// 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 숫자의 주요 요소를 계산하는 전체 예제를 보여 줍니다.
// 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();
}
이 예제에서는 다음 샘플 출력을 생성합니다.
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.
코드 컴파일
예제 코드를 복사하여 Visual Studio 프로젝트에 붙여넣거나 이름이 지정된 carmichael-primes.cpp 파일에 붙여넣은 다음 Visual Studio 명령 프롬프트 창에서 다음 명령을 실행합니다.
cl.exe /EHsc carmichael-primes.cpp
참고 항목
병렬 컨테이너 및 개체
작업 병렬 처리
concurrent_vector 클래스
concurrent_queue 클래스
parallel_invoke 함수
parallel_for 함수
task_group 클래스