日: 2021年10月25日

[Python] EX 03 ジェネレータを用いたフィボナッチ数生成関数

ジェネレータを用いたフィボナッチ数生成関数を走らせてみました。

処理速度は反復法に及びませんでしたが、なかなか面白い手法です。

import time,datetime

def generator(): # ジェネレータ
    a, b = 0, 1
    while True:
        yield b
        a, b = b, a + b

def fib_generator(n): # ジェネレータを用いた関数
    fib = generator()
    fib_list = [next(fib) for i in range(n-1)]
    return fib_list[-1]

def fib_iterate(n): # 反復法
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def fib_recursion(n, memo={}): # メモ化再帰法
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = fib_recursion(n-1, memo) + fib_recursion(n-2, memo)
        return memo[n]

if __name__ == '__main__':
    list_time = list()

    for function in [fib_generator,fib_iterate,fib_recursion]:
        start = time.time()

        print(function)
        print(function(41))

        # 処理時間算出
        process_time = time.time() - start
        td = datetime.timedelta(seconds = process_time)
        list_time.append(td.microseconds)

    print(list_time)
--------------------------------------------------

出力
--------------------------------------------------
<function fib_generator at 0x1074070d0>
102334155
<function fib_iterate at 0x107407160>
102334155
<function fib_recursion at 0x107407040>
102334155
[52, 10, 33]

[Python] EX 02 フィボナッチ数の生成関数

フィボナッチ数を生成する関数の計算速度を測定しました。メモ化再帰法が最速でした。

今の私の知識では反復法一択ですが、再帰的手法についてはこれから学んでいきます。

import time,datetime

def fib_A(n): # 反復法
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

def fib_B(n): # 再帰法
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fib_B(n-1) + fib_B(n-2)

def fib_C(n, memo={}): # メモ化再帰法
    if n == 1:
        return 0
    elif n == 2:
        return 1
    elif n in memo:
        return memo[n]
    else:
        memo[n] = fib_C(n-1, memo) + fib_C(n-2, memo)
        return memo[n]

if __name__ == '__main__':

    list_time = list()
    for function in [fib_A,fib_B,fib_C]:
        start = time.time()
        print(function)
        print(function(40))

        # 処理時間算出
        process_time = time.time() - start
        td = datetime.timedelta(seconds = process_time)

        list_time.append(td.microseconds)

    print(list_time)
--------------------------------------------------

出力
--------------------------------------------------
<function fib_A at 0x10743cf70>
63245986
<function fib_B at 0x107637040>
63245986
<function fib_C at 0x1076370d0>
63245986
[42, 549224, 35]