Wiederholung der Memorisierung und dynamische Planungsmethode, bekannt aus der Python Fibonacci-Sequenz

Einführung

Dieser Artikel wurde als Memo veröffentlicht, da ich durch die Berechnung der Fibonacci-Sequenz die Bedeutung des Einfallsreichtums bei der Berechnung gelernt habe.

Was ist die Fibonacci-Sequenz?

Eine Folge von Zahlen, dargestellt durch die Formel An = An-1 + An-2 (A0 = A1 = 1).

Die Zahlenfolge ist die Summe von 1 1 2 3 5 8 .... und den beiden vorhergehenden Begriffen.

Implementierung (rekursive, rekursive Gedenkplanung, dynamische Planung)

Implementieren Sie zunächst mit rekursiv

Implementierte eine Funktion, um einen beliebigen Term der Fibonacci-Sequenz in Python zu finden.

fib.py

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

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

Diese Funktion findet die Terme jeder Fibonacci-Sequenz. Diese Funktion ist jedoch rechenintensiv. Um fib (5) zu finden, suchen Sie fib (4) und fib (3). Wenn Sie fib (4) finden, suchen Sie fib (3) und fib (2). In diesem Fall wird fib (3) zweimal berechnet. Auf diese Weise führt die rekursive Implementierung zu nutzlosen Berechnungen.

Umsetzung mit Gedenkwiederholung

Zusätzlich zur normalen Wiederholung enthält die Wiederholung eines Denkmals Informationen zu berechneten Begriffen. Dieses Mal verwenden wir die Python-Wörterbuch-Typstruktur.

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

        #Verwenden Sie die gespeicherten Informationen, wenn der Begriff bereits berechnet wurde
        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]

Durch Speichern und Verwenden der bereits berechneten Begriffe wird die Verschwendung von Berechnungen vermieden.

Implementierung mit dynamischer Planung

Bei der dynamischen Planungsmethode werden die Terme der Fibonacci-Sequenz aus der kleinsten berechnet. Es eliminiert die Verschwendung von Berechnungen.

fib.py

def fib_dynamic(n):
    #Wörterbuch, das Ergebnisse enthält
    cal_result = {}

    #Anfangswerteinstellung
    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]

Überprüfung

Die Ausführungskosten (Sekunden) für die drei Implementierungen wurden mit n = 1 bis 15 berechnet. Das resultierende Diagramm ist unten dargestellt.

Normal ist normale Wiederholung, Memo ist Memorandum-Wiederholung und Dynamisch ist dynamische Planung. Aus dem Diagramm können Sie ersehen, dass es einen großen Unterschied in der Ausführungsgeschwindigkeit von etwa n = 10 gibt.

Fazit

Aus dem Obigen wurde festgestellt, dass sich die Ausführungsgeschwindigkeit bei einem einfachen Gerät stark unterscheidet. Normalerweise achte ich nicht besonders auf die Ausführungsgeschwindigkeit und es ist schwierig, die Wichtigkeit zu verstehen. Aufgrund dieses Ergebnisses hielt ich es für wesentlich, eine Datenstruktur und einen Algorithmus für umfangreiche Berechnungen zu entwickeln.