主にプログラミングに関して。Python, .NET Framework(C#), JavaScript, その他いくらか。
記事にあるサンプルやコードは要検証。使用に際しては責任を負いかねます

スポンサーサイト

                
tags:
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

誕生日のパラドックスを検証(Python multiprocessingモジュールを使って)

                
tags:
誕生日のパラドックス検証スクリプトをPythonで。

誕生日のパラドックスというものがある。「何人集まればその中に同じ誕生日の人がいる確率が50%を超えるか」。百数十人だろうか。実は意外と少ない人数で、23人である。勘から導いた確率と、実際に導出される確率が大きくかい離していることがわかる。このかい離を指して誕生日のパラドックスと呼ぶ。

これを一般式から人数を導出せずに、乱数を使ってシミュレートすることで統計的に求めてみる。統計的に求めるとなると、相応のシミュレート回数が必要になる。そうするとマルチコアを使う意義が出てくる。よってお遊びの中でmultiprocessingモジュールが、シミュレート実行時間にどう影響を与えるかも見てみる。

アルゴリズムは簡単。22個、23個の乱数(1以上365以下)を発生させて、その中で同一の数値が現れていれば「成功」としてカウント。任意の回数だけこの試行を繰り返し、「成功」数を試行数で割る。22個の乱数の場合では成功率が50%を切り、23個の乱数の場合では50%を超えていれば誕生日のパラドックスが正しいということだ。

試行回数が十分になれば算出される成功率は収束する。何度か試したところ、試行回数が100万回を超えたあたりで、それぞれの試行によるバラつき誤差が安定した。しかし100万回とは相当な計算量だ。処理時間は55秒程だった。

ここで試行環境。OS Win 7 Ult 64bit, CPU: i3 M370, Python2.6.6 for win32。

さて、マルチコアの恩恵をあずかろうとしてみよう。すでに書いてあったスクリプトに、multiprocessingモジュールを使ったスクリプトを書き足した。まずは同時展開スレッド数を2にしてみる。上が計算から出された成功率、下が処理時間[s]だ。
******
>>>
0.507298
31.3040001392
******

シングルでの処理時間を24秒も短縮した。では次は4スレッド展開で。CPUがハイパースレッディング対応で2コアなので、4スレッド処理ができるはずなので。
******
>>>
0.507137
25.8539998531
******

処理時間がさらに減った。劇的にではないけれど。計算量が多ければ、マルチスレッドを展開する価値は十分あるとわかった。

ちなみに。100万回も試行をしない場合、数百、数千程度ならmultiprocessingモジュールを使わない方が処理が速かった。

from random import randint
from multiprocessing import Pool
from time import time
from numpy import average as np_average

def loop(foo):
entered = []
for x in range(1, 24):
num = randint(1, 365)
if num in entered:
return 1
elif not num in entered:
entered.append(num)
return 0

TRIAL = 1000000
CORES = 4

def multi_pool():
jobs = []
p = Pool(CORES)
print np_average(p.map(loop, range(TRIAL)))

def single():
bingo = 0
for i in range(TRIAL):
bingo += loop(0)
print bingo / float(TRIAL)

if __name__ == '__main__':
t = time()
multi_pool()
print time() - t

t = time()
single()
print time() - t
            

コメントの投稿

非公開コメント

プロフィール

hMatoba

Author:hMatoba
Github

最新記事
リンク
作ったものなど
月別アーカイブ
カテゴリ
タグリスト

検索フォーム
Amazon
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。