[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)

Introduction

A Fibonacci sequence is a sequence in which the first two terms are 0, 1 and every subsequent term is the sum of the two terms immediately preceding it. ([Wikipedia](https://en.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3% From 83% 81% E6% 95% B0))

Fibonacci sequence


0
1
1 (0 + 1)
2 (1 + 1)
3 (1 + 2)
5 (2 + 3)
8 (3 + 5)
13 (5 + 8)

When finding the nth term of this sequence, if it is implemented as it is, it will be like this.

def fib(n):
    """
Find the nth Fibonacci number starting from 0.
    """
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(7)) # -> 13

When you actually run it, you can see that it is ** very slow **. For example, even n = 100 takes a considerable amount of time.

The reason is that, although details are omitted, ** the same calculation is performed many times **. For example, fib (8) can be obtained by finding fib (7) and fib (6), and then adding them together. However, in order to find fib (7), it is necessary to find fib (6) anew. There is.

Let's speed up with the keyword ** "Do not do the same calculation twice" **. We will introduce two algorithms, ** memoization ** and ** dynamic programming **.

Memoization

Save the result of the calculation once. If it works, use it, if not, calculate it anew and save the result for future use.

MAX_N = 100
MEMO = [None] * (MAX_N + 1)  #Array to save the calculation result

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    #Calculated?
    if MEMO[n]:
        return MEMO[n]

    r = fib(n-1) + fib(n-2)
    MEMO[n] = r  #Save calculation result
    return r

print(fib(100))

Even when n = 100, the result came back immediately.

Dynamic programming (DP)

The Fibonacci number can be calculated from the smaller n without using a recursive function.

MAX_N = 100
DP = [None] * (MAX_N + 1)  #Array to save the calculation result
DP[0] = 0  #From the definition
DP[1] = 1  #From the definition

def fib(n):
    #Find the Fibonacci number in order from 2 to n
    for i in range(2, n + 1):
        DP[i] = DP[i-1] + DP[i-2]
    return DP[n]

print(fib(100))

See reference material for dynamic programming.

Reference material

Recommended Posts

[Python] Find Fibonacci numbers at high speed (memoization, dynamic programming)
Memoization recursion and dynamic programming known by Python Fibonacci sequence
[Python] How to get divisors of natural numbers at high speed
[Python] Dynamic programming ABC015D
Perform half-width / full-width conversion at high speed with Python
[Python] Dynamic programming knapsack problem
[Python] Dynamic programming TDPC D
[Python] Articles that enable sparse matrix calculations at high speed
[Python] Dynamic programming TDPC A
Project Euler # 2 "Even Fibonacci Numbers" in Python
Learn dynamic programming in Python (A ~ E)