【Python】フィボナッチ数列を求める【multiprocessingで並列化】

こんにちは、のっくんです。

今日はPythonでフィボナッチ数列を求めてみます。

フィボナッチ数列とは?

フィボナッチ数列とは、

フィボナッチ数列」とは,「前の2つの数を加えると次の数になる」という数列です。

です。

{0,1,1,2,3,5,8,13 …}

というように、前の二つを足せば良いのです。

「1番目は0」、「5番目は3」というように、ある数Xを指定するとフィボナッチ数列X番目の数値を返すような関数を作りましょう。

以下のように考えるとシンプルです。

  • 1番目は0
  • 2番目は1
  • X番目は、(X-1)番目と(X-2)番目を足す

 

def Fibo(num):
    if num == 1:
        return 0
    elif num == 2:
        return 1
    else:
        return Fibo(num-1)+Fibo(num-2)

普通に計算してみる

 

例として39番目のフィボナッチ数列を求めてみます。(rangeの範囲は1〜39です。)

import time
start = time.time()
for i in range(1,40):
    print(Fibo(i))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

 

実行すると以下の値が得られます。(最初の方は省略)

 :
39088169
elapsed_time:31.42648720741272[sec]

31秒かかりました。

multiprocessingで並列化してみる

次に、`multiprocessing`のモジュールを使って並列化してみます。

その前に私の自宅のPCのコア数を調べます。

import multiprocessing
num_of_cpu = multiprocessing.cpu_count()
print(num_of_cpu)

#12

12個のCPUが搭載されていることが分かりました。

ちなみに、Google Colaboratoryというクラウドサービスで同じコードを実行してみたら2コアでした。

コア数が多ければ多いほど、並列化した時にスピードアップします。

from multiprocessing import Pool
start = time.time()
pool = Pool()
args = range(1,40)
result = pool.map(Fibo, args)
print(result)
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

実行してみると、、

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269,
 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169]

elapsed_time:12.244011402130127[sec]

かなり速くなりましたね!

 

おわり。