Récurrence de mémorisation et méthode de planification dynamique connue de la séquence Python Fibonacci

introduction

Cet article est posté sous forme de mémo car j'ai appris l'importance de l'ingéniosité du calcul à travers le calcul de la séquence de Fibonacci.

Quelle est la séquence de Fibonacci?

C'est une suite de nombres exprimée par la formule An = An-1 + An-2 (A0 = A1 = 1).

La séquence de nombres est la somme de 1 1 2 3 5 8 .... et des deux termes précédents.

Mise en œuvre (récursive, mémorielle récursive, planification dynamique)

Tout d'abord, implémentez avec récursif

Implémentation d'une fonction pour trouver un terme arbitraire de la séquence de Fibonacci en python.

fib.py

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

    return fib(n-1) + fib(n-2) 

Cette fonction trouve les termes de n'importe quelle séquence de Fibonacci. Cependant, cette fonction est coûteuse en calcul. Pour trouver fib (5), trouvez fib (4) et fib (3). Lorsque vous trouvez fib (4), trouvez fib (3) et fib (2). Dans ce cas, fib (3) est calculé deux fois. De cette manière, l'implémentation récursive aboutit à des calculs inutiles.

Mise en œuvre avec récurrence commémorative

En plus de la récurrence normale, la récurrence commémorative contient des informations sur les termes calculés. Cette fois, nous utiliserons la structure de type dictionnaire python.

fib.py

class Fib_memo:
    def __init__(self):
        self.fib_memo = {}

    def cal_fib(self, n):
        if n == 0 or n == 1:
            self.fib_memo[n] = 1
            return 1

        #Utilisez les informations enregistrées si le terme a déjà été calculé
        if n in self.fib_memo.keys():
            return self.fib_memo[n]
        
        self.fib_memo[n] = self.cal_fib(n-1) + self.cal_fib(n-2)
        return self.fib_memo[n]

En sauvegardant les termes déjà calculés et en les utilisant, le gaspillage de calcul est éliminé.

Mise en œuvre avec planification dynamique

Dans la méthode de planification dynamique, les termes de la séquence de Fibonacci sont calculés à partir du plus petit. Il élimine le gaspillage de calcul.

fib.py

def fib_dynamic(n):
    #Dictionnaire contenant les résultats
    cal_result = {}

    #Réglage de la valeur initiale
    cal_result[0] = 1
    cal_result[1] = 1

    if n == 0 or n == 1:
        return 1

    for i in range(2, n+1):
        cal_result[i] = cal_result[i-1] + cal_result[i-2]

    return cal_result[n]

Vérification

Le coût d'exécution (secondes) pour les trois implémentations a été calculé avec n = 1 à 15. Le graphique résultant est présenté ci-dessous.

Normal est une récurrence normale, Memo est une récurrence de mémorandum et Dynamic est une planification dynamique. À partir du graphique, vous pouvez voir qu'il existe une grande différence de vitesse d'exécution d'environ n = 10.

Conclusion

D'après ce qui précède, il a été constaté que la vitesse d'exécution diffère considérablement avec un appareil simple. Habituellement, je ne fais pas très attention à la vitesse d'exécution et il est difficile d'en comprendre l'importance. À partir de ce résultat, j'ai senti qu'il était essentiel de concevoir une structure de données et un algorithme pour les calculs lourds.