読んでたPython本でフィボナッチ数列に関して出てきたので調べつつメモ程度のライトな内容でまとめておきます。
なお、私の方はデザインの専門卒なので数学関係やコンピューターサイエンス関係の大学を出ている方からずると色々雑な点があるかと思われますがご了承ください。
使う環境
- Python 3.8.5
- VS Code
そもそもフィボナッチ数列とは
イタリアの数学者のレオナルド・フィボナッチさんにちなんで名づけられた数列です（英語ではFibonacci sequence）。
0, 1, 1, 2, 3, 5, 8, 13, 21...といった値の数列になります。
最初（0のインデックス）が0、次（1のインデックス）が1、それ以降は1つ前と2
式で書くと以下のような感じになります（数列の$n$番目の値を$F_n$とします）。
F_0 = 0\\
F_1 = 1\\
F_n = F_{n - 1} + F_{n - 2}
また、この数列はいわゆるデザイン方面、特に黄金比（1:1.618...）とも密接に絡んでおり、デザイン関係の本などでも出て来たりします。
自然界でもひまわりの種やオウムガイなど様々なもので、この数列の値に近くなっており、人が自然と美しく感じる比率と言われています。
その他にも黄金比の長方形を正方形と長方形の2つに分割すると、長方形の方は再び黄金比を維持した長方形になるなど、面白い性質を色々持っています（この記事では詳細は割愛します。数学やらデザイン関係の記事や本などでも調べると色々出てくるので必要に応じてお調べください）。
Pythonでフィボナッチ数列の値の算出処理を書いてみる
まずは何も考えずに、関数を再帰的に呼び出す形でPythonでフィボナッチ数列のインデックスnの位置の値を取得する処理を書いてみます。
def fib(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
前述の式そのまま、nが0のとき、nが1の時はそれぞれ0と1を返すようにし、それ以降ではn - 1とn - 2の位置のフィボナッチ数列の値の合計値になるようにしてあります。
実行して結果を確認してみます。
if __name__ == '__main__':
for n in range(7):
print(f'n = {n}の場合:', fib(n=n))
n = 0の場合: 0
n = 1の場合: 1
n = 2の場合: 1
n = 3の場合: 2
n = 4の場合: 3
n = 5の場合: 5
n = 6の場合: 8
想定した値が取れているとこが分かります。
nが大きくなると計算に時間がかかる問題
このままだとnが大きくなるととても計算に時間がかかるようになります。
例えばn = 5の値を計算する場合には、n = 4とn = 3の値を計算しないといけませんし、n = 4を計算するにはn = 3とn = 2の値を求めたり・・・といったように、nが1つ増える度にまるで家系図のようにその下に計算が必要な条件が指数関数的に増えていきます。
試しに用意した関数が何回実行されたかを調べてみます。クローバル変数でcountという変数を用意しました。
from datetime import datetime
count: int = 0
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
n=34とn=35などで実行しでみると、nが1増えただけで非常に関数実行回数が増えていることが分かります。
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=34)
print('関数が実行された回数:', count)
print(datetime.now(), 'ended')
2020-08-30 15:45:15.097393 started
関数が実行された回数: 18454929
2020-08-30 15:45:17.980419 ended
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('関数が実行された回数:', count)
print(datetime.now(), 'ended')
2020-08-30 15:49:25.628928 started
関数が実行された回数: 29860703
2020-08-30 15:49:30.307930 ended
計算を速くするために・・・
前述のようにnが大きくなった際の計算を速くするための方法は様々なものがありますが、その一つの方法に関数の実行結果をキャッシュするという対応があります。
たとえばnの値が同じ値の場合には返却値も同じ値が返るのと、大きなnの値を計算するときにはそれよりも小さな値は何度も何度も計算されうるため、既に特定のnの値のケースが集計済みであればキャッシュしておいて計算をスキップすることで、nが多くなっても短時間で処理を終わらせることができます。
辞書などを使ってキャッシュしてもいいのですが、Pythonではビルトインモジュールのfunctoolsを使って、lru_cacheのデコレーターを指定することで対応することができます。
使い方は簡単で、lru_cacheの関数をキャッシュしたい関数へデコレーターとして設定するだけです。lruはLeast Recently Usedの略で、新しい実行結果を残す（今回のケースでいえば最後の方にキャッシュされたnの計算結果を残す）形でキャッシュする方式です。
今回は古いキャッシュは削除しないで全てキャッシュするため、引数のmaxsizeにNoneを指定しています。
from datetime import datetime
from functools import lru_cache
count: int = 0
@lru_cache(maxsize=None)
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
実行してみると、処理は一瞬で終わり、且つ関数の内部を通った回数が一気に減っていることが確認できます。
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('関数が実行された回数:', count)
print(datetime.now(), 'ended')
2020-08-30 16:39:49.109241 started
関数が実行された回数: 36
2020-08-30 16:39:49.110240 ended