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

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

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

フィボナッチ数列とは？

フィボナッチ数列とは、

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

です。

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

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

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

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

• １番目は0
• ２番目は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の範囲は１〜３９です。）

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というクラウドサービスで同じコードを実行してみたら２コアでした。

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

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]

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

おわり。