こんにちは、のっくんです。
今日は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]
かなり速くなりましたね!
おわり。