細かく分かれてしまいましたが、Decorator4つ目。
（再帰の説明に言葉足らずな所があったので修正しました: 2021/11/14）
ベンチマーク計測を続けます。
フィボナッチ数の処理にかかる時間を測る
ベンチマーク計測と言えばやはりフィボナッチ数（Fibonacci number）。
詳細は上記リンク先wikipediaをご参照頂くのが一番ですが、簡単に言うと
F0（初項）は1、F1（第2項）は1、F2（第3項）以降は前の2項の数字を足した合計を解とする一連の数字。
初項から第10項迄のフィボナッチ数列は1, 1, 2, 3, 5, 8, 13, 21, 34, 55となります。
プログラムを組んで1から計算するとなると、最初は分かり易い、再帰（recursion）を使用したコードになりがち。
再帰を利用した計算では、Fx（第x項）の数は、前の2項の計算結果、Fx-1とFx-2を足した合計、と言う事になる。
しかしそのFx-1とFx-2は、Fx-2 と Fx-3の合計とFx-3 と Fx-4の合計であり、またそれぞれが前の2項の合計、と言う事になり、xが大きくなるほどに計算量が激増して時間が掛かってしまう。
この再帰で計算しているフィボナッチのコードを測ると測り甲斐がありそう。
ベンチマークをはかるdecoratorの下に、再帰を利用して第n項のフィボナッチ数を計算する関数fibo1(n)を記載した下記コードをbench2.pyとして保存する。
nが多いと計算が終わらなくなるので、第5項までとする。
import time
import functools
def Timer(func):
@functools.wraps(func)
def Wrapper(*args, **kwargs):
stime = time.process_time()
ret = func(*args, **kwargs)
etime = time.process_time()
print('{0}: {1:,f}ms'.format(func.__name__, (etime - stime)*1000))
return ret
return Wrapper
# Fibonacci recursion1
@Timer
def fibo1(n):
if (n == 1) or (n == 2):
return 1
return fibo1(n - 2) + fibo1(n - 1)
print(fibo1(5))
実行すると、あれ？今までと違う出力。
% python3 bench2.py fibo1: 0.000000ms fibo1: 0.001000ms fibo1: 0.065000ms fibo1: 0.001000ms fibo1: 0.000000ms fibo1: 0.001000ms fibo1: 0.007000ms fibo1: 0.014000ms fibo1: 0.088000ms 5
このエントリの3つ前の下記エントリでは
「decoratorは関数forloop()全体をデコレートする」と言う理解でした。
なぜbench2.pyでは何度もdecoratorが走っているのか？
これはrecursion（再帰）を利用したからだと考えられる。
因みにこのrecursion（再帰）（以下recursion）と は、「関数の中で自分自身を呼びだす事」である。
今回のfibo1(5)においては、下記計算が行われているが、これは実際の所、1から関数fibo1(n)を呼び出して実行し、実行の結果返ってきた戻り値を利用して更なるfibo1(n)を実行している。
1：f1を計算
2：f2を計算
3：f3を計算（f3＝f1 + f2）
4：f4を計算1（f3を算出＝ f1 ＋ f2）
5：f4を計算2（f4＝「4で計算したf3」 + f2）
6：f5を計算1（f3を算出＝ f1 + f2）
7：f5を計算2（f4を算出1： f3を算出＝f1＋ f2）
8：f5を計算3（f4を算出2：f4＝「7で計算したf3」 + f2）
9：f5を計算4（f5＝ 「7で計算したf3」 ＋ 「8で計算したf4」）
関数の中で何度もfibo1(n)関数を呼び出している訳だが、Decoratorが走って時間を計測しているのも9回なので、それぞれの関数呼び出しの際にDecorator時間が計測したと思って差し支えないだろう。
再帰を使用する関数の全体の時間を図る
上記の様に、再帰の関数では関数が呼び出される都度decoratorが走って時間を計測してしまう。
こんな場合は再帰の関数ごと関数で括ってしまおう。
fibo1(n)をTestfibo1(n)で括り、そのTestfibo1(n)をdecorateした下記コードをbench2b.pyとして保存、実行。
import time
import functools
def Timer(func):
@functools.wraps(func)
def Wrapper(*args, **kwargs):
stime = time.process_time()
ret = func(*args, **kwargs)
etime = time.process_time()
print('{0}: {1:,f}ms'.format(func.__name__, (etime - stime)*1000))
return ret
return Wrapper
# Fibonacci recurcion1r
@Timer
def Testfibo1r(n):
def fibo1(n):
if (n == 1) or (n == 2):
return 1
return fibo1(n - 2) + fibo1(n - 1)
return fibo1(n)
print(Testfibo1r(5))
%python3 bench2b.py Testfibo1r: 0.016000ms 5
測ることが出来た。
色々なFibonacci numberの計算方法を試す。
import time
import functools
def Timer(func):
@functools.wraps(func)
def Wrapper(*args, **kwargs):
stime = time.process_time()
ret = func(*args, **kwargs)
etime = time.process_time()
print('{0}: {1:,f}ms'.format(func.__name__, (etime - stime)*1000))
return ret
return Wrapper
# Fibonacci recurcion1r
@Timer
def Testfibo1r(n):
def fibo1(n):
if (n == 1) or (n == 2):
return 1
return fibo1(n - 2) + fibo1(n - 1)
return fibo1(n)
print(Testfibo1r(30))
# Fibonacci recursion & memo
memo = {1:1, 2:1}
@Timer
def Testfibo2rm(n):
def fibo2(n):
if n in memo:
return memo[n]
memo[n] = fibo2(n - 2) + fibo2(n - 1)
return memo[n]
return fibo2(n)
print(Testfibo2rm(30))
# Fibonacci loop & list(fib)
@Timer
def fibo3fl(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i - 2] + fib[i - 1])
return fib[n - 1]
print(fibo3fl(30))
今回は違いを明確にする為に、第30項の数を算出。
14行目# Fibonacci recurcion1rの関数Testfibo1r(30)はさっきと同じ、再帰による計算。
25行目# Fibonacci recursion & memoのの関数Testfibo2rm(30)は計算途中の第x項の数をdictionary型のmemoに残していく処理。今まで計算していた数がmemo内にあればそれを利用し、無ければ前2項の数を足した上でmemoに残す。計算を繰り返す必要がないので、時間は格段に早くなるはず。
39行目# Fibonacci loopの関数fibo3fl(30)は、フィボナッチ数をfor loopで算出、list”fib”に残していく方法。
再帰を使用していないので、関数で纏めなくても時間を計ることが出来る
計算の都度結果をlist”fib”に残していくので計算は早いはず。
実行結果
% python3 bench3.py Testfibo1r: 187.830000ms 832040 Testfibo2rm: 0.018000ms 832040 fibo3: 0.012000ms 832040
ただ再帰で計算した場合と比べ、再帰+メモ、for loopは格段に早いことが分かる。
コメント