書籍転載 文法からはじめるプログラミング言語Microsoft Visual C++入門 並列処理を行うための基礎知識（Visual C++） ――第13章 並列処理〜マルチスレッドプログラミング（前編）―― WINGSプロジェクト　矢吹 太朗（監修　山田 祥寛） 2010/04/13
Page1 Page2

■13.2　例題：素数の列挙

　この章ではマルチスレッドプログラミングのための例題として、素数を列挙するプログラムを作成します。この節では、その準備として逐次的なプログラムを作成し、マルチスレッド化のための戦略を考えます。

●13.2.1 素数の判定

　素数を列挙する方法としては、2から順にすべての数の倍数をふるい落としていく方法（エラトステネスのふるい）が有名ですが、ここでは単純に、「2から順に約数かどうかを調べていく」という方法を採用します。この方法を実現するプログラムはとても単純なため、マルチスレッドの本質をつかむのによい例だと思われます。

　まず初めに、与えられた数が素数かどうかを判定する関数を作成します。次の関数isPrime()は、引数nが素数かどうかをbool型で返します。

//引数が素数かどうかを判定する bool isPrime(int n) {   if (n<2) return false; //2未満なら素数ではない   if (n==2) return true; //2は素数   //for (int j=2; j<sqrt(double(n))+1; ++j) {   //この方がはるかに速い   for (int j=2; j<n; ++j) { //2以上のnは、     //2以上n未満の数で割り切れたら素数ではない     if (n%j==0) return false;   }   return true; }

［サンプル］number.h

　明らかに、for文の上限はnではなくnの平方根つまりsqrt(n)で十分です（sqrtの利用には<cmath>が必要です）。実際、for文の上限をnからsqrt(n)に変更することには、この章で導入するどんな並列化手法よりも効果があります。並列化によるパフォーマンスの向上はたかだか定数倍ですが、アルゴリズムの改良によるパフォーマンスの向上は、それよりもはるかに大きくなることがよくあります。ですから、高速化のために闇雲にプログラムを並列化するのではなく、アルゴリズムについてゆっくり考えることを習慣にするべきでしょう。しかしこの章では、マルチスレッドの効果を確認するためにあえて遅い方法を採用して先に進みます。

　結果を報告するための補助的な関数report()を定義します。この関数は、ランダムアクセス反復子で与えられた範囲の、最初と最後の10個の要素を表示します。

//要素の最初と最後の10個を表示する template<typename T> void report(T first, T last) {   const int num=10;   if (last-first<num) //num個未満ならすべて表示     for (T i=first; i!=last; i++) std::cout<<*i<<' ';   else {     for (T i=first; i!=first+num; i++) std::cout<<*i<<' ';     std::cout<<std::endl;     for (T i=last-num; i!=last; i++) std::cout<<*i<<' ';   }   std::cout<<std::endl; }

［サンプル］number.h

　関数isPrime()とreport()は頻繁に使うため、number.hにまとめておきます。

#ifndef NUMBER_H #define NUMBER_H #include <iostream> #include <cmath> （isPrime()の定義） （report()の定義） #endif //NUMBER_H

［サンプル］number.h

●13.2.2 素数の列挙

　前項で定義した関数isPrime()を用いて、2からNまでの素数を列挙するプログラムを書くと次のようになります。見つかったすべての素数を表示するのは大変なので、素数を一度vectorに格納し、すべてを調べ終わってから、見つかった素数の数と最初と最後の10個を表示するようにしています。後で並列化する際にその効果がわかるように、関数clock()を使って計算時間を測っています。この関数はCPUのクロック数を返すので、1秒あたりのクロック数CLOCKS_PER_SECで割って秒にしています*4。

*4　ここで利用している時間測定方法は、環境によっては正しい結果を返さないので注意してください。

#include <vector> #include <ctime> #include "number.h" using namespace std; const int N=100000; //ここまで調べる int main() {   clock_t start=clock(); //開始時間   vector<int>* primes=new vector<int>; //結果を格納するベクタ   for (int n=2; n<=N; ++n) { //素数が見つかったらvectorに格納     if (isPrime(n)) primes->push_back(n);   }   //素数の数を表示   cout<<"There are "<<primes->size()<<" prime numbers.\n";   //最初と最後の10個を表示   report(primes->begin(), primes->end());   clock_t finish=clock(); //終了時間     //経過時間の表示   double duration=double(finish-start)/CLOCKS_PER_SEC;   cout<<"Elapsed time: "<<duration<<" sec.\n"; }

［サンプル］13-primes-single.cpp

　プログラムを実行すると次のようになります。2から100000までには9592個の素数があることを、約9.4秒かけて計算しました。

There are 9592 prime numbers. 2 3 5 7 11 13 17 19 23 29 99877 99881 99901 99907 99923 99929 99961 99971 99989 99991 Elapsed time: 9.421 sec.

●13.2.3 並列化の方針

　前項では、2からNまでの整数を順番に調べることによって素数を列挙しました。次節以降では、この処理を並列化します。ここでは次のような方針で並列化することにします（図13-3）*5。

• スレッドを2つ使う
• 1番目のスレッドでは、3で割った余りが1のもの（3の倍数+1）のみを調べる
• 2番目のスレッドでは、3で割った余りが2のもの（3の倍数+2）のみを調べる

　いずれの方針も、最適だという合理的な理由のあるものではありません。スレッドを2つにするのは、デュアルCPUやデュアルコアのCPUで実行したときに、並列化の効果がわかりやすいと思われるからです。3で割った余りで数を分類するのは、スレッドが2つだからです（実際に割り算をするわけではないので、分類のための計算負荷は高くありません）。

*5　実際には、ここで示したような方針がまずあって、それから前項のような方法が決まりました。エラトステネスのふるいのような別の方法が先にあったら、このような方針を採用することはできないでしょう。

図13-3　並列処理で素数を列挙する方針

■

　次回も引き続き、並列処理について説明します。テーマは「標準C++におけるマルチスレッド」「.NETにおけるマルチスレッド」「OpenMP」の3つです。

INDEX
	［書籍転載］文法からはじめるプログラミング言語Microsoft Visual C++入門
	並列処理を行うための基礎知識（Visual C++）
	1．並列処理
	2．例題：素数の列挙

「文法からはじめるプログラミング言語Microsoft Visual C++入門」

＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）