マルチスレッドプログラミング

マルチスレッドは普段あまり扱わないので…

本当の目的はIdeoneでマルチスレッドプログラミングが有効かどうか調べたかっただけです。


n未満の全ての自然数に対して素数か否かを判定するプログラムを設計する(とします)。
言語は、マルチスレッドプログラミングが簡単(だと勝手に思っている)Javaです。

プログラムではn=1000100になってます。





メモ:
・変な入力・引数は考慮しない
・変なアルゴリズムについては深く考えない(偶数処理など)
・深刻なコメント不足

マルチスレッドの効果が見たいだけなので。


シングルスレッドプログラミング(ideone)


class Prime{
public int num;
public boolean[] primeData;
public boolean[] primeDataSolved;

public Prime(int n){
num=n;
initialize();
solve();
for (int i=-8;i<=8;i++)
System.out.println("isPrime("+(num/2+i)+") -> "+isPrime(num/2+i));
}

public static void main(String[] args){
new Prime(1000100);
}

public void initialize(){
primeData = new boolean[num]; // 全てfalse
primeDataSolved = new boolean[num]; // 全てfalse
primeData[0]=false; // ?
primeData[1]=false;
primeData[2]=true;

}

public void solve(){
for (int i=3;i<num;i++){
int j;
if (primeDataSolved[i]==true) continue;
primeDataSolved[i]=true;
for (j=2;j*j<i;j++)
if (i%j==0) break;
if (i%j!=0){
primeData[i]=true;
for (j=1;j*i<num;j++)
primeDataSolved[j*i]=true;
}
}
}

public boolean isPrime(int i){
if (i<0 || num<=i) return false;
return primeData[i];
}

}

軽く解説を加えると、7が素数ならば14,21,28,...は素数ではない、といった判定です。平凡。


マルチスレッドプログラミング(ideone)
4人のスレッドが頑張ります。
主にPrimeMT.solve()の中身が大きく変わってます。

class PrimeMT{
public int num;
public boolean[] primeData;
public boolean[] primeDataSolved;

public PrimeMT(int n){
num=n;
initialize();
solve();
for (int i=-8;i<=8;i++)
System.out.println("isPrime("+(num/2+i)+") -> "+isPrime(num/2+i));
}

public static void main(String[] args){
new PrimeMT(1000100);
}

public void initialize(){
primeData = new boolean[num]; // 全てfalse
primeDataSolved = new boolean[num]; // 全てfalse
primeData[0]=false; // ?
primeData[1]=false;
primeData[2]=true;
}

public void solve(){
Thread t1=new SolveThread(this);
Thread t2=new SolveThread(this);
Thread t3=new SolveThread(this);
Thread t4=new SolveThread(this);
try{
t1.start();t2.start();t3.start();t4.start();
t1.join();t2.join();t3.join();t4.join();
}catch (InterruptedException e){
e.printStackTrace();
}
}

public boolean isPrime(int i){
if (i<0 || num<=i) return false;
return primeData[i];
}

public synchronized int getNext(int offset){
for (;offset<num;offset++)
if (!primeDataSolved[offset]){
primeDataSolved[offset]=true;
return offset;
}
return -1;
}
}

class SolveThread extends Thread{
PrimeMT prime;
int current;
int num;
public SolveThread(PrimeMT p){
super();
prime=p;
num=p.num;
current=3;
}
public void run(){
while ((current=prime.getNext(current))!=-1){
int j;
for (j=2;j*j<current;j++)
if (current%j==0) break;
if (current%j!=0){
prime.primeData[current]=true;
for (j=1;j*current<num;j++)
prime.primeDataSolved[j*current]=true;
}
}
}
}


実行結果(cygwin)。

$ time java Prime
isPrime(500042) -> false
isPrime(500043) -> false
isPrime(500044) -> false
isPrime(500045) -> false
isPrime(500046) -> false
isPrime(500047) -> false
isPrime(500048) -> false
isPrime(500049) -> false
isPrime(500050) -> false
isPrime(500051) -> false
isPrime(500052) -> false
isPrime(500053) -> false
isPrime(500054) -> false
isPrime(500055) -> false
isPrime(500056) -> false
isPrime(500057) -> true
isPrime(500058) -> false

real 0m0.436s
user 0m0.031s
sys 0m0.031s

----------------------------------

$ time java PrimeMT
isPrime(500042) -> false
isPrime(500043) -> false
isPrime(500044) -> false
isPrime(500045) -> false
isPrime(500046) -> false
isPrime(500047) -> false
isPrime(500048) -> false
isPrime(500049) -> false
isPrime(500050) -> false
isPrime(500051) -> false
isPrime(500052) -> false
isPrime(500053) -> false
isPrime(500054) -> false
isPrime(500055) -> false
isPrime(500056) -> false
isPrime(500057) -> true
isPrime(500058) -> false

real 0m0.276s
user 0m0.015s
sys 0m0.047s


若干早くなってます。


ところで、肝心なIdeoneでの実行速度はどうなんだ。

個人版では実行時間が表示されなかったので、CodeIQのサンドボックスを使って測定。

Prime -> 0.3s
Priment -> 0.31s


速くなってない。「ですよねー!」以外の感想はありません。

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

tag : Java

コメントの投稿

非公開コメント

プロフィール

舞葉(ぶよう)

Author:舞葉(ぶよう)
github.io
はてなブログ(競プロ)

古い記事のソースコードは色分けしていないので、高機能テキストエディタに貼り付けたほうが見やすいかも。

検索フォーム
このブログについて
自分がつまづいた話題、なんとなく書きたいと思ったこと、ググったけど殆ど資料なかったぞオイ な話等をアップする予定。通りすがりでも、参考になっていただければと。プログラムの例外入力、メモリリークは責任負いません。投稿された記事は修正・削除する場合があります。
カテゴリ
タグ

HSP3アルゴリズムとデータ構造c++RubyJavaUnity画像解析C機械学習C#LinuxcodeIQKinectMinecraftTonyuSystemraspberrypiPythonHTML5音声制御Simulinkruby俺ルール通信制御Javascriptシミュレーション

counter-shinobi
固定記事
最新記事
最新コメント
月別アーカイブ
ブロとも申請フォーム

この人とブロともになる

アクセスランキング
[ジャンルランキング]
コンピュータ
1253位
アクセスランキングを見る>>

[サブジャンルランキング]
プログラミング
219位
アクセスランキングを見る>>