Python-Memorandum (Algorithmus)

Eine Erinnerung daran, Python von Grund auf neu zu lernen. Ich möchte Ergebnisse erzielen, die grundlegende Probleme angehen.

Fibonacci-Folge

Erstellen Sie ein Ergebnisanzeigeprogramm für die Fibonacci-Sequenz. Der Beamte ist übrigens

a_{1} = a_{2} = 1 \\ 
a_{n+2} = a_{n+1} + a_{n}\;\;\;\;\;(n >= 1) 

Ist.

Schreiben Sie als offiziell

fibonacci_simple.py

#Die Formel für die Fibonacci-Sequenz lautet wie folgt.
#Zu diesem Zeitpunkt wird die Fibonacci-Funktion viele Male aufgerufen, um den numerischen Wert von n zu erhalten.
#Daher ist der Algorithmus einfach, aber die Verarbeitung ist langsam.
import time 


def fibonacci_simple(n):
    if (n == 1) or (n == 2):
        return 1
    return fibonacci_simple(n - 2) + fibonacci_simple(n - 1)


start = time.time()
print(fibonacci_simple(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

als Ergebnis

6765
elapsed_time:0.002089977264404297[sec]

Versuchen Sie, es mit Memo zu einem Hochgeschwindigkeitsprozess zu machen

fibonacci_memo.py

#Beschleunigen Sie die Verarbeitung, indem Sie Notizen machen.
#Der Wert des bedingten Arrays wird in das assoziative Array namens memo eingefügt.
#memo Wenn es immer gibt, endet es. Wenn nicht, berechnen und in das Memo einfügen
#Die gleiche Berechnung kann eliminiert werden.
import time


memo = {1: 1, 2: 1}
def fibonacci_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibonacci_memo(n - 2) + fibonacci_memo(n - 1)
    return memo[n]


start = time.time()
print(fibonacci_memo(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

als Ergebnis

6765
elapsed_time:0.0002808570861816406[sec]

Versuchen Sie es mit einer Schleife

fibonacci_loop.py

#Verwenden Sie eine Schleife, um es zu finden.
import time


def fibonacci_loop(n):
    fib = [1, 1]
    for i in range(2, n):
        fib.append(fib[i -2] + fib[i - 1])
        
    return fib[n - 1]


start = time.time()
print(fibonacci_loop(20))
elapsed_time = time.time() - start
print ("elapsed_time:{0}".format(elapsed_time) + "[sec]")

als Ergebnis

6765
elapsed_time:0.00026702880859375[sec]

Wenn Sie vergleichen

Es ist erstaunlich, dass die Verarbeitungszeit auf 1/10 reduziert werden kann, indem nur der Umfang der doppelten Berechnung im Vergleich zur einfachen reduziert wird.