Pythonで巨大な階乗を求めた話

皆さん,元気にPythonistaしてますか〜?

Project Eulerとかいう数学力を試すコーディング能力を試すサイトで,

僕はPythonでチマチマ解いてます.

その中で,並列処理計算がちょっと気になったので,調べたついでに具体例で説明備忘録できたらいいな,と思います.(インタプリタで並列化とか意味不明すぎる,とかいうツッコミはなしでww)

具体例とは,ズバリ,タイトルにもあるように「階乗」です.

それも,巨大な階乗です.100000!にしましょう.

では,階乗を求めるコードを書いてください.

def Factorial_(integer) : 
 return 1 if integer == 0 else integer * Factorial(integer - 1)

確か,僕が学部の時,最初に習ったのはC言語だったのですが,

再帰関数の例でこんなのをやりました.でも,これで階乗を求めては

ダメです!

理由は,再帰の繰り返しであばばー,となるからです.

僕は,このコードを例に出すのは情報学演習の悪しき風習だと思うのですが,どうなんでしょう.教える側の詳しい事情,歴史,慣習は知りません.

実際,上のコードを100000!でやると

再帰回数を超えました

とエラーが出ます.Pythonのデフォルトの再帰限界は1000回だからです.

仕方ないので,積を格納する変数productを用意して

def Factorial(integer) : 
 product = 1
 if integer == 0 : return 1
 for num in range(1 , integer + 1):
 product *= num
 return product

みたいにします.

この2つのコードによる,(再帰限界を越えない程度の)998!はPython2.7,MacBookAir(Mid 2011 model)で

(前者) Factorial_(998) 0.762ms
(後者) Factorial(998)  0.586ms

となります.なお,時間の計測は

import time
 start = time.clock()
 Factorial(998)
 end = time.clock()
 print(str((end - start) * 1000) + 'ms')

のように雑に求めましたことを激白します(timeitは使っていない)

しかし,それでも100000!の階乗には関数Factorialで

Factorial(100000) 5037.811ms

5秒もかかります.

そこで並列化しました.簡単です.

MBAは4コアなので,以降4コアで説明すると,

100000!=(100000\times 99996 \times \cdots \times 4)\times (99999\times 99995\times \cdots \times 3)\times (99998 \times 99994 \times \cdots \times 2)\times (99997 \times 99993 \times \cdots \times 1)

とすればいいだけですよね!?

…実装しました.

import multiprocessing
import operator

c = multiprocessing.cpu_count()

def p_fac(n) : 
 product = 1
 if n == 0 : return 1
 for num in range(1 , n + 1 , c):
  product *= num
 return product

def p_Factorial(n) : 
 p = multiprocessing.Pool()
 return reduce(operator.mul , p.map(p_fac , range(n , n - c , -1)) , 1)

(間違いがあることが指摘されています)

cにはコア数が格納されます.僕のMBAですと4です.

p_facはcおきに数字を飛ばして階乗もどきを計算します.n!!!!ってことですね.

最後のp_Factorialでは,

p = multiprocessing.Pool()

で,プロセスのプールを作成します.

次の

reduce(operator.mul, ~)

は,~ に来るリストを全部積を取るだけです.

和だったらsumでやってくれるのに,積に相当するのがこんなのしかなくて,Pythonの仕様は???です.

そして,

p.map(p_fac , range(n , n - c , -1)) , 1)

は,4つのプロセスで各々計算したn!!!! , (n-1)!!!! , (n-2)!!!! , (n-3)!!!!をリストで与えます.

こうして並列化ができました.めっちゃ簡単ですね!

計算結果は

(シングルプロセス)Factorial 5012.873ms
(マルチプロセス)p_Factorial  276.728ms

やったね!∩(>◡<*)∩♡

参考:

http://gihyo.jp/dev/serial/01/pythonhacks/0005

http://docs.python.jp/3.3/library/multiprocessing.html

広告

Pythonで巨大な階乗を求めた話」への4件のフィードバック

    1. くぅ.色々実験してもやっぱりよく分からないので触れませんでしたww
      実は,c=1として計算してみました.1コアなので,早くならないはずです.
      しかし,p_Factorialの結果は27.291msとなって,シングルプロセスより180倍近く早いという結果になりました…
      (ちなみに,2コアで156.416ms, 3コアで245.565msとなり,いずれも4コアより早いです)
      pythonのmultiprocessモジュールは単純な並列化だけ行っているようには思えない,という感じですね…(全然分からない)

  1. コア数増やすと遅くなるってことですか.
    処理量が少なくてマルチプロセス展開するオーバーヘッドの方がでかくなってるのかな・・・?
    後,この計算方法だと,p_facの中で,rangeの第一引数が1だとまずいんじゃないでしょうか.

    1. その可能性は十分に考えられますが,1プロセスのプールで大きく高速化されているので主な原因は他にあると考えるのが自然だということを述べました.
      すみません,記事の執筆途中で内容飛んだので憶測で書きました.再度確認したら,
      range(n,0,-c)
      でした.赤字で修正しときます.ありがとうございました.

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中