こんにちは、のっくんです。
今日はPythonでフィボナッチ数列を求めてみます。
[toc]フィボナッチ数列とは？
フィボナッチ数列とは、
「フィボナッチ数列」とは，「前の２つの数を加えると次の数になる」という数列です。
です。
{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]
かなり速くなりましたね！
おわり。
