【Python】フィボナッチ数列
はじめに
学びたいことが多すぎます。キョです。
みなさん、競技プログラミングをやったことがありますか？
私は、2年前の転職活動で、コーディングテストの対策として、
毎週の土曜日、AtCodeのコンテストに参加したことがあります。
※今は全然やっていないですけどねｗｗ
最近、自分が何かのコードを書く時、
考えがまとまらない場合が時々ありますので、
定期的に競技プログラミングの問題を解くことでプログラミングの練習を再開しようと思います！
今回はまず、よく序盤で遭遇する
・フィボナッチ数列
の実装から、行きたいと思います。
フィボナッチ数列とは
フィボナッチ数列は、先頭の2項目以外、一般項は前の2項目の和で表れることができる数列です。
定義は以下になります。
- fib(0) = 0
- fib(1) = 1
- fib(n+2) = fib(n) + fib(n+1) (n ≥ 0)
プログラミングでの実装
今回は、Pythonで実装したいと思います。
１．再帰による実装
再帰はある手続きや関数が自分自身を参照または呼び出すことを指します。
上のフィボナッチ数列の定義も再帰として見てもいいでしょう。
それなら、さっそく実装してみます。
def fib(n: int) -> int:
if n <= 1: return n
return fib(n-2) + fib(n-1)
再帰による実装はシンプルで分かりやすいですね。
でも、今の実装だと以下の問題があります。
- nが大きくなるほど、fib関数の呼び出し回数が非常に多くなる
試しに、fib関数を呼び出すたびに、ログを出力するように修正します。
def fib(n: int) -> int:
print(f'fib関数実行！ n：{n}')
if n <= 1: return n
return fib(n-2) + fib(n-1)
そして、fib(4)を求める時の出力は以下になります。
$ python fib.py 4
fib関数実行！ n：4
fib関数実行！ n：2
fib関数実行！ n：0
fib関数実行！ n：1
fib関数実行！ n：3
fib関数実行！ n：1
fib関数実行！ n：2
fib関数実行！ n：0
fib関数実行！ n：1
fib(4) = 3
fib(4)の結果を求めるだけで、fib関数を9回実行されました。
fib(10)の場合は、177回実行されます。
これはなんででしょうか？
ログを見るだけで、関数がどんな感じで呼び出されているかがわかりずらいと思いますので、
下の図を用意しました。
図を見れば、原因がわかると思います。
それは、重複計算した部分があるからです。
例えば、fib(2)を一度計算したにもかかわらず、
二回目fib(2)を呼び出す時、もう一度fib(0) + fib(1)で再計算しています。
つまり、一度計算したことがあるものを一度保存して利用すれば、
改善できると思いますね。
では、このコードを改善していきたいと思います。
from typing import Dict
fib_memo: Dict[int, int] = {0: 0, 1: 1}
def fib(n: int) -> int:
print(f'fib関数実行！ n：{n}')
if n not in fib_memo.keys():
fib_memo[n] = fib(n-2) + fib(n-1)
return fib_memo[n]
$ python fib.py 4
fib関数実行！ n：4
fib関数実行！ n：2
fib関数実行！ n：0
fib関数実行！ n：1
fib関数実行！ n：3
fib関数実行！ n：1
fib関数実行！ n：2
fib(4) = 3
改善後、fib(4)の場合はfib関数を7回実行するようになりました。
nが小さい場合は、あまり改善できなかったかと思うかもしれないですが、
fib(10)の場合は、177回から19回になりました！
２．for文による実装
再帰以外、for文を利用しても実装できます。
def fib(n: int) -> int:
if n <=1: return n
n1: int = 0 #fib(0)
n2: int = 1 #fib(1)
for _ in range(1, n):
n1, n2 = n2, n1 + n2
return n2
$ python fib3.py 4
fib(4) = 3
for文による実装だと、ちょっとわかりずらいですが、
n-1回実行しますので、上の再帰バージョンより実行回数が少ないですね。
３．その他の方法
実はpythonでは、lru_cacheというデコレータがありますので、
lru_cacheを利用することによって、
Dictを利用した再帰の改善案と同じ効果を得ることができます。
その実装も記載します。
※同じ効果というか実は実行回数がもっと少ないですね。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n: int) -> int:
print(f'fib関数実行！ n：{n}')
if n <= 1: return n
return fib(n-2) + fib(n-1)
$ python fib.py 4
fib関数実行！ n：4
fib関数実行！ n：2
fib関数実行！ n：0
fib関数実行！ n：1
fib関数実行！ n：3
fib(4) = 3
$ python fib.py 10
fib関数実行！ n：10
fib関数実行！ n：8
fib関数実行！ n：6
fib関数実行！ n：4
fib関数実行！ n：2
fib関数実行！ n：0
fib関数実行！ n：1
fib関数実行！ n：3
fib関数実行！ n：5
fib関数実行！ n：7
fib関数実行！ n：9
fib(10) = 55
最後に
再帰バージョンとforバージョンのフィボナッチ数列を実装してみました。
再帰は直感的で、わかりやすいですが、
対策しないと、呼び出し回数が多くなり、性能上問題が発生するかもしれないですね。
for文による実装は少々わかりずらいですが、性能上の問題はないでしょう。
いつどんな方法を使うかは常に考えないといけないですね。
みなさんもぜひ自分で実際に実装してみてください。
それでは、良い開発ライフをお送りください。
Discussion