[PYTHON] J'ai essayé d'étudier DP avec séquence de Fibonacci

Depuis que j'ai le temps, j'ai commencé à travailler sur la méthode de planification dynamique (DP) afin de démarrer avec AtCoder 100 tours plus tard.

TL;DR Je viens d'implémenter la partie de la séquence de Fibonacci dans Dynamic Planning in Programming Contest en Python.

DP Ne faites pas la même recherche deux fois Une fois calculé, enregistrez le résultat et réutilisez-le

Séquence de Fibonacci

La "séquence de Fibonacci" est une séquence qui "ajoute les deux nombres précédents pour obtenir le nombre suivant". Cependant, les premier et deuxième nombres sont tous deux 1.

--Les valeurs des éléments 0 à 21 sont les suivantes:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …

 > --La séquence de Fibonacci (Fn) est définie par l'expression graduelle suivante:

> ```math
F0 = 0\\
F1 = 1\\
F_{n+2} = F_n + F_{n+1}\,(n ≥ 0)\\

Studyplus Wikipedia

Mesure du temps de traitement

Je vais introduire une fonction de devinette que j'utilise souvent pour mesurer le temps de traitement! Simplification de la fonction de minuterie introduite par le maître kaggle Arai (Je suis content d'avoir kaggle juste pour savoir ça ...)

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)

Patrimoine du code Kaggle

Sujet principal

Calculez le nombre de Fibonacci normalement

def fib(n: int):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Recherche de mémo (mémo de fonction rétroactive)

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]

Méthode de planification dynamique (expression graduelle + boucle)

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]

Courir

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

commander

python fibonacci.py fib_memo 1000

vitesse de traitement

Parmi les trois ci-dessus, la méthode de planification dynamique était la plus rapide, puis la recherche par mémo, et la plus lente était le cas du calcul normal du nombre de Fibonacci.

Comme décrit dans Méthode de planification dynamique dans le concours de programmation, il semble que la quantité de calcul prend un temps exponentiel ou un temps pseudopolypolique.

Méthode de planification dynamique<Recherche de mémo<<<<<<<<<<<<<<<<<<Numéro de Fibonacci normalement

--Lorsque n = 30000 --Méthode de planification dynamique: 0,04 s

• Recherche de mémoire: 0,06 s --Normalement Fibonacci: Cela ne se termine pas (cela prend beaucoup de temps même avec n = 100)

Veuillez consulter Github pour plus de détails