円周率をモンテカルロ法で求める vol.3
先日、モンテカルロ法で円周率を求めるプログラムをくんだ。
ちょっと気になることがあって確かめてみたら驚いた。
そのプログラムを振り返ってみよう。
はじめに二重ループを使ったシンプルなプログラム。
jp\yucchi\loop_motecarlo_pi\Loop_Motecarlo_PI.java |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
package jp.yucchi.loop_motecarlo_pi; public class Loop_Motecarlo_PI { private static final double TOTAL_THREAD = 16.0; private final static double NEEDLE = 1_000_000.0; public static void main(String[] args) { long stime = System.currentTimeMillis(); double totalPi = 0.0; for (double j = 0.0; j < TOTAL_THREAD; j++) { double hitCount = 0.0; double x, y, pi; for (double i = 0.0; i < NEEDLE; i++) { x = Math.random(); y = Math.random(); if (Math.pow(x, 2.0) + Math.pow(y, 2.0) < 1.0) { hitCount++; } } pi = 4.0 * hitCount / NEEDLE; System.out.println("Montecarlo PI : " + pi); totalPi += pi; } double avgPi = totalPi / TOTAL_THREAD; System.out.println("Mathクラスによる円周率は " + Math.PI); System.out.println("モンテカルロ法による円周率は " + avgPi); stime = System.currentTimeMillis() - stime; System.out.println("Time : " + stime + "ミリ秒"); } } |
その実行結果は次のようになりました。
run:
Montecarlo PI : 3.144016
Montecarlo PI : 3.143836
Montecarlo PI : 3.140812
Montecarlo PI : 3.142616
Montecarlo PI : 3.141592
Montecarlo PI : 3.139224
Montecarlo PI : 3.143332
Montecarlo PI : 3.140608
Montecarlo PI : 3.141352
Montecarlo PI : 3.139116
Montecarlo PI : 3.140224
Montecarlo PI : 3.141696
Montecarlo PI : 3.144996
Montecarlo PI : 3.142304
Montecarlo PI : 3.14044
Montecarlo PI : 3.14482
Mathクラスによる円周率は 3.141592653589793
モンテカルロ法による円周率は 3.141936500000001
Time : 1516ミリ秒
構築成功 (合計時間: 1 秒)
次に今時の PC はマルチコアが当たり前になってきてるので
並行処理をさせるように変更しました。
jp\yucchi\montecarlo_pi\Montecarlo_PI.java |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
package jp.yucchi.montecarlo_pi; import java.lang.management.ManagementFactory; import java.util.ArrayList; import java.util.List; import java.util.concurrent.*; import java.util.logging.Level; import java.util.logging.Logger; public class Montecarlo_PI implements Callable<List<Double>> { private static final double TOTAL_THREAD = 16.0; private final double NEEDLE = 1_000_000.0; public static void main(String[] args) { long stime = System.currentTimeMillis(); int procs = ManagementFactory.getOperatingSystemMXBean().getAvailableProcessors(); ExecutorService executor = Executors.newFixedThreadPool(procs); List<Future<List<Double>>> futures = new ArrayList<>(); for (double i = 0; i < TOTAL_THREAD; i++) { futures.add(executor.submit(new Montecarlo_PI())); } executor.shutdown(); List<Double> mPi = new ArrayList<>(); for (Future<List<Double>> future : futures) { try { List<Double> pi = future.get(); mPi.addAll(pi); } catch (InterruptedException | ExecutionException ex) { Logger.getLogger(Montecarlo_PI.class.getName()).log(Level.SEVERE, null, ex); } } double totalPi = 0.0; for (Double pi : mPi) { totalPi += pi; } double avgPi = totalPi / TOTAL_THREAD; System.out.println("Mathクラスによる円周率は " + Math.PI); System.out.println("モンテカルロ法による円周率は " + avgPi); stime = System.currentTimeMillis() - stime; System.out.println("Time : " + stime + "ミリ秒"); } @Override public List<Double> call() throws Exception { List<Double> pi = new ArrayList<>(); double hitCount = 0.0; for (double i = 0; i < NEEDLE; i++) { double x = Math.random(); double y = Math.random(); if (Math.pow(x, 2.0) + Math.pow(y, 2.0) < 1.0) { hitCount++; } } double _pi = 4.0 * hitCount / NEEDLE; System.out.println("Montecarlo PI : " + _pi); pi.add(_pi); return pi; } } |
実行結果は先ほどのプログラムを遙かに上回る結果となるはずだったんだけど・・・
run:
Montecarlo PI : 3.143472
Montecarlo PI : 3.141672
Montecarlo PI : 3.1408
Montecarlo PI : 3.140352
Montecarlo PI : 3.141668
Montecarlo PI : 3.13966
Montecarlo PI : 3.139112
Montecarlo PI : 3.142532
Montecarlo PI : 3.13982
Montecarlo PI : 3.143956
Montecarlo PI : 3.141428
Montecarlo PI : 3.138096
Montecarlo PI : 3.141932
Montecarlo PI : 3.143548
Montecarlo PI : 3.14172
Montecarlo PI : 3.141612
Mathクラスによる円周率は 3.141592653589793
モンテカルロ法による円周率は 3.14133625
Time : 22172ミリ秒
構築成功 (合計時間: 22 秒)
(゜◇゜)ガーン
な、なんと 遙かに遅い!
ExecutorService でスレッドプール作って処理させるほうがコストが高くつく!
この程度の計算ならシングルスレッドでもいいみたい。
そこで時間のかかる処理を無意味に追加した場合どうなるか確認した。
次のコードをそれぞれのプログラムに追加した。
for (int k = 0; k < 10_000; ++k) {
for (int n = 0; n < 10_000; ++n) {
double p = k * n;
p = Math.sqrt(p);
}
}
その結果は次のようになった。
二重ループのプログラムでは
run:
Montecarlo PI : 3.138036
Montecarlo PI : 3.144924
Montecarlo PI : 3.139508
Montecarlo PI : 3.14336
Montecarlo PI : 3.140848
Montecarlo PI : 3.14178
Montecarlo PI : 3.141744
Montecarlo PI : 3.143868
Montecarlo PI : 3.14006
Montecarlo PI : 3.143568
Montecarlo PI : 3.137936
Montecarlo PI : 3.141968
Montecarlo PI : 3.143396
Montecarlo PI : 3.142736
Montecarlo PI : 3.137876
Montecarlo PI : 3.141624
Mathクラスによる円周率は 3.141592653589793
モンテカルロ法による円周率は 3.141452
Time : 250579ミリ秒
構築成功 (合計時間: 4 分 10 秒)
時間が結構かかってますね!
平行処理プログラムでは次のようになりました。
run:
Montecarlo PI : 3.142172
Montecarlo PI : 3.140212
Montecarlo PI : 3.142544
Montecarlo PI : 3.14186
Montecarlo PI : 3.14264
Montecarlo PI : 3.143252
Montecarlo PI : 3.140788
Montecarlo PI : 3.140544
Montecarlo PI : 3.14346
Montecarlo PI : 3.144144
Montecarlo PI : 3.141128
Montecarlo PI : 3.140564
Montecarlo PI : 3.140828
Montecarlo PI : 3.13794
Montecarlo PI : 3.140336
Montecarlo PI : 3.141248
Mathクラスによる円周率は 3.141592653589793
モンテカルロ法による円周率は 3.1414787499999997
Time : 32468ミリ秒
構築成功 (合計時間: 32 秒)
(^_^)v 速い!
浮動小数点演算なんかをさせるとかなり違いがでるのかな?
なんでもかんでも並行処理させればいいってことじゃないのかなぁ・・・?
リソースモニターですべてのコアが 100% で動いてるのは圧巻だったけど
処理が遅くては本末転倒ですね。(^_^;)
TAGS: Java | 2012年6月17日9:02 PM | Comment : 0