Since I had time, I started working on dynamic programming (DP) in order to get started with AtCoder 100 laps later.
TL;DR I just implemented the Fibonacci sequence part of Dynamic Programming in Programming Contest in Python.
DP Don't do the same search twice Once calculated, save the result and reuse it
The "Fibonacci sequence" is a sequence that "adds the previous two numbers to get the next number". However, the first and second numbers are both 1.
--The values in items 0 to 21 are as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …
> --The Fibonacci sequence (Fn) is defined by the following recurrence formula:
> ```math
F0 = 0\\
F1 = 1\\
F_{n+2} = F_n + F_{n+1}\,(n ≥ 0)\\
I will introduce a guess function that I often use when measuring processing time! Simplified the timer function introduced by kaggle master Arai (I'm glad I did kaggle just to know this ...)
import time
from contextlib import contextmanager
@contextmanager
def timer():
t0 = time.time()
msg = "start"
print(msg)
yield
msg = f"done in {time.time() - t0:.2f} s"
print(msg)
def fib(n: int):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
def fib_memo(n: int):
global done
global memo
if n == 0: return 0
if n == 1: return 1
if done[n]:
return memo[n]
done[n] = True
memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
return memo[n]
def fib_loop(n: int):
global memo
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]
if __name__ == "__main__":
parser = argparse.ArgumentParser()
parser.add_argument("method", help="Select to solve with which fibonacci method")
parser.add_argument("max_num", help="Set max number")
args = parser.parse_args()
n = int(args.max_num)
done = [False] * (n + 1)
memo = [0] * (n + 1)
with timer():
print(eval(args.method)(n))
python fibonacci.py fib_memo 1000
Of the above three, dynamic programming was the fastest, then memo search, and the slowest was when calculating the Fibonacci number normally.
It seems that the amount of calculation takes exponential time or pseudo-polynomial time as described in Dynamic programming in programming contest.
Dynamic programming<Memo search<<<<<<<<<<<<<<<<<<Fibonacci number normally
--When n = 30000 --Dynamic programming: 0.04 s --Memo search: 0.06 s --Normally Fibonacci: It doesn't end (it takes a lot of time even with n = 100)
Please refer to Github for details
Recommended Posts