system
大橋 俊昭

2016.4.28システム開発 

代表取締役

大橋 俊昭

「どれだけ速く」なるかな!?(その2)

ご無沙汰しておりました、プログラマーの大橋です。花粉症からのやっと逃れられました。春は一年で最高の季節、ホントに過ごし易くなりました。。。

今回は「どれだけ速くできるか!?」の続編になります。チューンアップしてどこまで速くできたか!?

前回までの「おさらい」

前回は「1,000,000以下の素数」をチェックしていくにあたり、「一番ベタな方法」でサンプルプログラムを準備しました。開発言語は「Java」です。マシンスペックにも依存しますが、恐ろしく時間がかかる結果でした。

処理時間:119789ミリ秒
結果(取得数):78498件

早速、チューンアップにチャレンジ!!

チューンアップには「素数」の性質を知る必要がありますが、そこまで難しくならず、シンプルに考えてみると、以下のようなことが分かります。

(その1)1桁の素数(2、3、5、7)は算出する必要はありません。
(その2) 自分自身の半分以下の数でしか割り切ることはできません。
(その3) 割り切れるかどうかは素数のみでチェックすれば良いです。

(その2)については、厳密に言うと「自分自身の平方根」以下の数でしか割り切ることができない ということになりますので、厳密にチューンアップしていくことにします。

こんなプログラムになりました!!

前回からの変更点は微々たるものですが、これでチューンアップは完了です。さて、どのくらい速くなっているか、とても楽しみですね。

public static void main(String[] args) {
	// 初期処理
	long stTime = 0; // 開始ポイント
	long edTime = 0; // 終了ポイント

	boolean primeCk = true; // 判定
	List primeNo = new ArrayList(); // 結果(素数一覧)

	// 開始ポイント設定
	stTime = System.currentTimeMillis();

	// 処理実行(1,000,000以下の素数を取得)
	for (int targetNo = 2; targetNo <= 1000000; targetNo++) {

		// 自分自身以外で割り切れる場合、素数ではない
		primeCk = true;
		if (targetNo != 2 && targetNo != 3 && targetNo != 5 && targetNo != 7) {

			for (int i = 0; primeNo.get(i) < (int) Math.sqrt(targetNo) + 1; i++) {
				if (targetNo % primeNo.get(i) == 0) {
					primeCk = false;
					break;
				}
			}

		}

		// 結果(素数一覧)へ保存
		if (primeCk) {
			primeNo.add(targetNo);
		}
	}

	// 終了ポイント設定
	edTime = System.currentTimeMillis();

	// 結果表示
	System.out.println("処理時間:" + (edTime - stTime) + "ミリ秒");
	System.out.println("結果(取得数):" + primeNo.toArray().length + "件");
}

さて、結果はいかに!!

処理時間:204ミリ秒
結果(取得数):78498件

なんと 約600倍 も速くなりました。正直、ビックリですよ。結果は 1秒以下 でした。これであれば、もっとイケルはず、凄腕プログラマーの皆さん、是非チャレンジしてみてください!!<つづく>

システム開発サービスはこちら
ページTOPへ