【java】100,000までの素数の数を並列処理(Thread)で求めたい

Question

【java】100,000までの素数の数を並列処理(Thread)で求めたい

java8にて、100,000までの素数の数及び以下の内容を4つの並列処理(Thread)で求めたいです。

・素数の数の算出には近似式は用いず，繰り返し処理を用いて総当たりで求める.
・2つ以上のスレッドにより並列処理することによって，なるべく高速に結果を得るように実装する.

スレッドの概念を正しく理解できていないため、以下のコードでは４回処理を繰り返すだけの機能となってしまっておます。

並列処理の実装方法をご教授ください。

該当のソースコード

public class Prog4Lec14Sub2{
	static Counter counter = new Counter();

	public static void main(String[] args) {

		MyThread1 threads1 = new MyThread1();
		MyThread2 threads2 = new MyThread2();
		MyThread3 threads3 = new MyThread3();
		MyThread4 threads4 = new MyThread4();


		long startTime;
		long estimatedTime;

		startTime = System.nanoTime();

		threads1.start();
		threads2.start();
		threads3.start();
		threads4.start();

//		スレッドの処理待ち
		try {
				threads1.join();
				threads2.join();
				threads3.join();
				threads4.join();
			}
			catch(InterruptedException e) {
				System.out.println(e);
			}
		estimatedTime = System.nanoTime() - startTime;
		System.out.println(estimatedTime/1000 + "ns");
	}
}

public class Counter {
	int count;
	public void countUp() {

		for(int i=2; i<100; i++) {
			for(int j=2; i%j != 0 && j<i || j == i; j++) {
				if(j == i) {
					System.out.println(i + ":素数");
				}
			}
		}
	}
}

//これを、MyThread1~4.javaまで準備
public class MyThread1 extends Thread {
	public void run() {
		Prog4Lec14Sub2.counter.countUp();
	}
}

Comments

[otn]

並列処理の勉強目的であれば、素数は適当な題材で無いと思います。
素数を高速に求めることの方が目的であれば、並列処理するので無く、「エラトステネスのふるい」など、アルゴリズムの改善が効果的です。

[astro_taaka]

素数でなく、単なる加算の並列処理でも結構です。

[dodox86]

質問のポイントがどこにあるのか分かりづらいのですが、

> スレッドの概念を正しく理解できていないため、以下のコードでは４回処理を繰り返すだけの機能となってしまっておます。

それぞれのスレッドで違う変数の値（例えば、違う範囲の計算をする為の値）を割り当て、その値に応じてそれぞれ独自の処理をさせるにはどうしたらよいのか、というようなことでしょうか。

Answer 1

問題解釈

力ずくで素数を求める処理を、スレッドを利用して効率化する問題だと解釈します。方針を決めます。

• データを分割してそれぞれをスレッドで処理する
  分割データは共通部分を待たず互いに素な集合にする（パーティション）
  当然、パーティションの和集合は元のデータになります
• 全てのスレッドが終了した後で結果を合成する

データを分割する目的は、データを共有せず、同期化のオーバヘッドをなくすことにあります。

スレッド定義

スレッドを以下のように改良します。求めるのは素数の個数だとします。下限から上限までの連続した数の素数判定を行います。

• start 素数判定の下限
• end 素数判定の上限
• counter 素数の数

public class PrimeCounter extends Thread {  
  private final int start;
  private final int end;
  private int counter;  
  public PrimeCounter(int start, int end) {
    this.start = start;
    this.end = end;
    this.counter = 0;
  }  
  public int getCounter() {
    return counter;
  }
  @Override
  public void run() {  
    for (int i = start; i <= end; i++) {
      for (int j = 2; i % j != 0 && j < i || j == i; j++) {
        if (j == i) {
          counter++; //System.out.println(i + ":素数");
        }
      }
    }   
  }
}

スレッドをデータチャンクごとに生成して実行し、結果を集計します。

【追記】

• データは均等分割してください。分割は、連続した区間ではなく、スレッドの数（4）ごとに間隔をあけることでもできます。（どちらが効率的かは試してください）
• スレッド数は利用可能なCPUコアの数にします。
• 実行速度は、素数判定を平方根までの整数で割る方法に変更すると劇的に改善します。（問題が適切でないと思います）