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

Veuillez consulter Github pour plus de détails

Recommended Posts

J'ai essayé d'étudier DP avec séquence de Fibonacci
J'ai essayé la récurrence avec Python ② (séquence de nombres Fibonatch)
J'ai essayé de trouver la moyenne de plusieurs colonnes avec TensorFlow
J'ai essayé d'implémenter Autoencoder avec TensorFlow
J'ai essayé de visualiser AutoEncoder avec TensorFlow
J'ai essayé de commencer avec Hy
J'ai essayé d'implémenter CVAE avec PyTorch
J'ai essayé de résoudre TSP avec QAOA
J'ai essayé de prédire l'année prochaine avec l'IA
J'ai essayé d'implémenter la lecture de Dataset avec PyTorch
J'ai essayé d'utiliser lightGBM, xg boost avec Boruta
J'ai essayé d'apprendre le fonctionnement logique avec TF Learn
J'ai essayé de déplacer GAN (mnist) avec keras
J'ai essayé de sauvegarder les données avec discorde
J'ai essayé de détecter rapidement un mouvement avec OpenCV
J'ai essayé d'intégrer Keras dans TFv1.1
J'ai essayé d'obtenir des données CloudWatch avec Python
J'ai essayé de sortir LLVM IR avec Python
J'ai essayé de déboguer.
J'ai essayé de détecter un objet avec M2Det!
J'ai essayé d'automatiser la fabrication des sushis avec python
J'ai essayé de prédire la survie du Titanic avec PyCaret
J'ai essayé d'utiliser Linux avec Discord Bot
J'ai essayé de démarrer Jupyter avec toutes les lumières d'Amazon
J'ai essayé de juger Tundele avec Naive Bays
J'ai essayé de déplacer l'apprentissage automatique (détection d'objet) avec TouchDesigner
J'ai essayé d'extraire des fonctionnalités avec SIFT d'OpenCV
J'ai essayé de déplacer Faster R-CNN rapidement avec pytorch
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2 2
J'ai essayé d'implémenter et d'apprendre DCGAN avec PyTorch
J'ai essayé d'implémenter Mine Sweeper sur un terminal avec python
J'ai essayé de démarrer avec le script python de blender_Part 01
J'ai essayé de toucher un fichier CSV avec Python
J'ai essayé de résoudre Soma Cube avec python
J'ai essayé de lire et d'enregistrer automatiquement avec VOICEROID2
J'ai essayé de démarrer avec le script python de blender_Partie 02
J'ai essayé de générer ObjectId (clé primaire) avec pymongo
J'ai essayé d'implémenter le perceptron artificiel avec python
J'ai essayé de créer un pipeline ML avec Cloud Composer
J'ai essayé de découvrir notre obscurité avec l'API Chatwork
[Introduction à Pytorch] J'ai essayé de catégoriser Cifar10 avec VGG16 ♬
J'ai essayé de résoudre le problème avec Python Vol.1
J'ai essayé d'implémenter Grad-CAM avec keras et tensorflow
J'ai essayé de créer une application OCR avec PySimpleGUI
J'ai essayé d'implémenter SSD avec PyTorch maintenant (Dataset)
J'ai essayé d'interpoler le masque R-CNN avec un flux optique
J'ai essayé de passer par l'optimisation bayésienne. (Avec des exemples)
J'ai essayé de trouver la classe alternative avec tensorflow
J'ai essayé d'implémenter le calcul automatique de la preuve de séquence
[Introduction à AWS] J'ai essayé de jouer avec la conversion voix-texte ♪
J'ai essayé de résoudre la théorie des nombres entiers d'AOJ avec Python
J'ai essayé fp-growth avec python
J'ai essayé de gratter avec Python
J'ai essayé Learning-to-Rank avec Elasticsearch!
J'ai essayé d'organiser SVM.
J'ai essayé le clustering avec PyCaret