アルゴリズムの違いによる素数探索プログラムの性能差

Javaの勉強を兼ねて遊んでみた

65000までの素数を求めるプログラムで
2通りのアルゴリズムの実行時間で評価すると
こうなる。


アルゴリズム
コマンドプロンプトのコピー
====================================================================

64717
64747
64763
64781
64783
64793
64811
64817
64849
64853
64871
64877
64879
64891
64901
64919
64921
64927
64937
64951
64969
64997
実行にかかった時間は 1902 ミリ秒です。


================================================================
アルゴリズム

64717
64747
64763
64781
64783
64793
64811
64817
64849
64853
64871
64877
64879
64891
64901
64919
64921
64927
64937
64951
64969
64997
実行にかかった時間は 5446 ミリ秒です。

================================================================


================================================================

※使用した計算機はCore i7搭載 MacMini 2012のサーバーモデルである。



65000までの探索なら大体2-3倍の差が出る。
ちょっとした計算でもプログラムを書く際には気をつけないと速度に
2-3倍の品質差が出てくるという事である。
やらなくていい事や冗長なロジックはプログラムに書いてはいけない。
性能の良いプログラムを書くにはやはり数学的発想、
常識をプログラムに反映させる事が大切
この例ではちょっとした数学知識を活かせるかどうかで
べた書きの場合と比べて最低2倍の品質差を生み出せる
ソフトウェアエンジニアになれるか決まるというのが分かる。
複数のモジュールを組み合わせて製品を作る
大規模なプロジェクトではその差が10倍にも100倍にもなりうる


※探索範囲の上限が100万の場合、単品でも処理時間が十分の一以下になる
アルゴリズム
====================================================================
999653
999667
999671
999683
999721
999727
999749
999763
999769
999773
999809
999853
999863
999883
999907
999917
999931
999953
999959
999961
999979
999983
実行にかかった時間は 22559 ミリ秒です。

====================================================================

================================================================
アルゴリズム
999631
999653
999667
999671
999683
999721
999727
999749
999763
999769
999773
999809
999853
999863
999883
999907
999917
999931
999953
999959
999961
999979
999983
実行にかかった時間は 275184 ミリ秒です。

====================================================

面白いからこれBigInteger型使って
もっと大きな数まで求めた場合の結果も比較してみようと思います。


※所感
現代の文明において数学に馴染もうとせず生きようとすると
文明に飲み込まれる可能性が高いと思う
自分で意思決定をしているつもりでも実はそれは事前に
計算機が用意した環境から自明に導かれる結論を出しただけではないだろうか?
何を持って自分で意思決定をしているという事になるのか
現代社会に生きる人々はこの問いに向かい合わざるを得ないだろう


















アルゴリズム① 
※Web上のJavaの入門ページから借用し
 http://www.geocities.jp/m_hiroi/java/abcjava02.html
 処理時間計測の機能を付加したもの
 探索範囲内の奇数以外の数で
 見つけた素数が順次約数か調べる
 ちなみに素数の2乗が調べたい数を超える場合は無視
 無駄な事はしない
 
public class PrimeNumberFas{
public static void main(String args){

long start = System.currentTimeMillis();
Timing timing = new Timing();
int limit=1000;
int prime_table
= new int [limit];
int prime_size = 1;
prime_table[0] = 2;

for(int n = 3; n < prime_table.length; n += 2){
boolean flag = true;
for(int i = 1; i < prime_size; i++){
int p = prime_table[i];
if(p * p > n){
break;
} else if(n % p == 0){
flag = false;
break;
}
}
if(flag) prime_table[prime_size++] = n;
}
for(int i = 0; i < prime_size; i++){
System.out.print(prime_table[i] + " \n");
}
long stop = System.currentTimeMillis();
System.out.println("実行にかかった時間は " + (stop - start) + " ミリ秒です。");
}
}


アルゴリズム②
※ひたすら1から順に約数があるか検索
 最後まで約数が見つからなければ素数と判定する

public class PrimeNumber{

public static void main(String[] args) {
// TODO Auto-generated method stub
long start = System.currentTimeMillis();
int limit=65000;
Timing timing = new Timing();

for(int i=1;i