[PYTHON] Memo gelernt

Vorwort

Vor kurzem hatte ich mehrere Möglichkeiten, eine Auswahl von Praktikanten und eine endgültige Auswahl von Web-Unternehmen zu erhalten. Bei der Auswahl vieler Unternehmen gab es einen Codierungstest, und da ich diesmal ein wenig studiert habe, werde ich ihn als Memorandum als Ausgabepraxis belassen.

Diesmal über ** Auswendiglernen **.

Was ist ein Memo?

Einfach gesagt, es ist eine Technik, um Ihr Programm zu beschleunigen.

Dies ist eine Technik wie "Wenn dieselbe Funktion bei der rekursiven Verarbeitung usw. mehrmals aufgerufen wird, wird das Berechnungsergebnis im Cache (Memo) aufgezeichnet und der zwischengespeicherte Wert wird für den zuvor berechneten zurückgegeben."

Implementierungsbeispiel

Dieses Mal werde ich als Implementierungsbeispiel ein Programm vorstellen, das nach ** fragt, was die n-te Zahl in der Fibonacci-Sequenz ist.

Fibonacci-Folge

a_1=a_2=1 \\
a_n=a_{n−1}+a_{n−2}\\
(1\leqq n)

Die Fibonacci-Zahlenfolge kann wie oben gezeigt als allmähliche Formel ausgedrückt werden. Ich werde nicht auf Details eingehen, aber die ersten beiden Begriffe geben 1 zurück, und der Rest der Begriffe gibt die Summe der beiden vorherigen Begriffe zurück.

Implementiert mit nur rekursiv

def fibonacci(n):
    if n == 1 or n == 2:
        return 1

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

print(fibonacci(6))  # 8

Als Memo implementiert

memo = {1: 1, 2: 1}

def fibonacci(n):
 Wenn n in # memo aufgezeichnet ist, wird sein Wert zurückgegeben.
    if n in memo:
        return memo[n]

 # Wenn nicht, notieren Sie es in einem Memo und geben Sie den Wert zurück
    memo[n] = fibonacci(n - 2) + fibonacci(n - 1)
    return memo[n]

print(fibonacci(6))  # 8

Bild

Bei einfacher rekursiver Implementierung wird n = 6 zweimal als Fibonacci (4) und dreimal als Fibonacci (3) bezeichnet. Sie können sich vorstellen, dass mit zunehmender Anzahl von n die Anzahl der Berechnungen zunimmt. Wenn Sie ein Memo erstellen, müssen Sie das einmal berechnete Memo ab dem zweiten Mal nicht mehr berechnen, sodass Sie die Anzahl der Berechnungen erheblich reduzieren können.

Zusammenfassung

--Memo ist eine der Techniken zur Beschleunigung des Programms.

• Je größer n, desto effektiver