関数プログラミングのアプローチ (4)
モンテカルロ法の関数的プログラム (1)
前回、関数的な乱数生成器を作成しました。これを用いて関数的なモンテカルロ法のプログラムを作成することはそれほど難しくありません。
以下は、命令的プログラムを関数的な乱数生成器を用いて書き換えたものです。
def main (): print math.sqrt(6.0 / estimate(cesaro_test, 10000, RandState.new())) def estimate (test, times, rs): x, y = 0.0, 0.0 for i in xrange(0,times): b, rs = test(rs) if b: x = x + 1 y = y + 1 return x / y def cesaro_test (rs): x, rs = rand(rs) y, rs = rand(rs) return 1 == gcd(x, y), rs def gcd(a, b): while b > 0: a, b = b, a % b return a
まず、最初にRandState.new()で乱数状態オブジェクトを生成し、それを用いて、cesaro_test()で乱数を生成しています。毎回のテストを行うたびに、乱数状態オブジェクトが更新されるため、cesaro_test()は更新された乱数オブジェクトを返します。
このプログラムは、関数的なので、何度実行しても同じ結果を得ることができます。RandState.new()は関数的なのでいつでも同じ状態で初期化された乱数状態オブジェクトを生成し、同じ状態の乱数状態オブジェクトをcesaro_test()に渡せば、常に同じ結果が得られるためです。
ここで疑問に思うことは、このように関数的に書き換えることは、はたして何のメリットがあるのでしょうか?
関数的なプログラムは、並列化が容易です。これは関数の実行処理が関数呼出ごとに独立しているために、実行順序に関する制約が少ないためです。では、このプログラムは並列化できるでしょうか?
実は、このプログラムは、そのままでは並列化できません。これは、関数プログラミングのメリットを損なっています。並列化できない理由は、乱数状態オブジェクトの受渡しにあります。
cesaro_test()は、乱数状態オブジェクトを受け取って、そこから乱数を必要な個数生成したの値に、更新された乱数状態オブジェクトを返します。この新しい乱数状態オブジェクトが、次のcesaro_test()の呼び出しで渡されて、次のテストが実行されます。この処理の流れによって、次のテストが呼び出される前に、前のテストが完了していなければならないことが強制されるのです。
これは、乱数状態オブジェクト rs によって、プログラムがシングルスレッド化されているということができます。そこで、このプログラムを変形して、シングルスレッド化されていないプログラムを作成するにはどうすればよいでしょうか?