방법: 병렬 컨테이너를 사용하여 효율성 향상

아티클
08/09/2011

이 항목에서는 병렬 컨테이너를 사용하여 병렬 방식에 따라 효율적으로 데이터를 저장하고 액세스하는 방법을 보여 줍니다.

예제 코드에서는 소수와 카마이클 수 집합을 병렬로 계산합니다. 그런 다음 각 카마이클 수에 대해 해당 수의 소인수를 계산합니다.

예제

다음 예제에서는 입력 값이 소수인지 여부를 확인하는 is_prime 함수와 입력 값이 카마이클 수인지 여부를 확인하는 is_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_prime 및 is_carmichael 함수를 사용하여 소수 및 카마이클 수 집합을 계산합니다. 이 예제에서는 Concurrency::parallel_invoke 및 Concurrency::parallel_for 알고리즘을 사용하여 각 집합을 병렬로 계산합니다. 병렬 알고리즘에 대한 자세한 내용은 병렬 알고리즘을 참조하십시오.

이 예제에서는 나중에 작업 큐로 사용할 수 있도록 Concurrency::concurrent_queue 개체를 사용하여 카마이클 수의 집합을 저장합니다. 또한 나중에 이 집합을 반복하여 소인수를 찾을 수 있도록 Concurrency::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);
         }
      });
   });

다음 예제에서는 나누기 시도(trial division)라는 알고리즘을 사용하여 지정된 값의 모든 소인수를 찾는 prime_factors_of 함수를 보여 줍니다.

이 함수는 Concurrency::parallel_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(primes.begin(), primes.end(), [&](int prime)
   {
      if (prime <= max)
      {         
         if ((n % prime) == 0)
            prime_factors.push_back(prime);
      }
   });

   return prime_factors;
}

이 예제에서는 prime_factors_of 함수를 호출한 후 소인수를 계산하여 카마이클 수의 큐에서 각 요소를 처리합니다. 여기에서는 작업 그룹을 사용하여 이 작업을 병렬로 수행합니다. 작업 그룹에 대한 자세한 내용은 작업 병렬 처리(동시성 런타임)를 참조하십시오.

이 예제에서는 각 카마이클 수에 소인수가 5개 이상 있는 경우 해당 카마이클 수의 소인수를 출력합니다.

// 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();

다음 코드에서는 병렬 컨테이너를 사용하여 카마이클 수의 소인수를 계산하는 전체 예제를 보여 줍니다.

// 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();
}

이 예제를 실행하면 다음과 같은 샘플 결과가 출력됩니다.

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 2010 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc carmichael-primes.cpp

참고 항목

다음을 통해 공유

방법: 병렬 컨테이너를 사용하여 효율성 향상

예제

코드 컴파일

참고 항목

참조

개념

기타 리소스

추가 리소스