Pythonをしっかりと根本面での学習をしなおそうという備忘録。
基本的な問題などに取り組んでいるものを成果として上げていこうと思う。
フィボナッチ数列
フィボナッチ数列の結果表示プログラムを作成せよ。
ちなみに、公式は、
a_{1} = a_{2} = 1 \\
a_{n+2} = a_{n+1} + a_{n}\;\;\;\;\;(n >= 1)
である。
公式通りに書いてみる
fibonacci_simple.py
# フィボナッチ数列の公式から立てると以下のようになる。
# この時、nの数値を出すのに、fibonacci関数を呼び出す回数が多い。
# よって、アルゴリズムは簡単だけど、処理が遅い。
import time
def fibonacci_simple(n):
if (n == 1) or (n == 2):
return 1
return fibonacci_simple(n - 2) + fibonacci_simple(n - 1)
start = time.time()
print(fibonacci_simple(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
その結果
6765
elapsed_time:0.002089977264404297[sec]
メモ化で高速処理にしてみる
fibonacci_memo.py
# メモ化によって処理を高速化する。
# memoという連想配列に条件配列の値を入れている。
# memo常にあれば、終了。なければ、計算とmemoへの挿入
# 同じ計算をなくすことができる。
import time
memo = {1: 1, 2: 1}
def fibonacci_memo(n):
if n in memo:
return memo[n]
memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1)
return memo[n]
start = time.time()
print(fibonacci_memo(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
その結果
6765
elapsed_time:0.0002808570861816406[sec]
ループを使ってみる
fibonacci_loop.py
# ループを使って、求める。
import time
def fibonacci_loop(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i -2] + fib[i - 1])
return fib[n - 1]
start = time.time()
print(fibonacci_loop(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")
その結果
6765
elapsed_time:0.00026702880859375[sec]
比較してみると
単純なものより、重複する計算量を減らすだけで、1/10の処理時間になるのはすごいなぁ。