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]
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]