Python decoratorの簡単な練習4-フィボナッチ数の算出にかかる時間を計算

細かく分かれてしまいましたが、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
@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で算出する方法。
再帰を使用していないので、関数で纏めなくても時間を計ることが出来る
また、こちらも計算の都度結果をリストfibに残していくので計算は早いはず。

実行結果

% python3 bench3.py
Testfibo1r: 187.830000ms
832040
Testfibo2rm: 0.018000ms
832040
fibo3: 0.012000ms
832040

ただ再帰で計算した場合と比べ、再帰+メモ、for loopは格段に早いことが分かる。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

four × 4 =

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください