Ich habe dynamische Planung gelernt, als ich in meinem zweiten Jahr der Grundschule war. Wenn ich dieses Wissen jedoch nicht benutze, werde ich immer mehr vergessen. Ich werde diesen Artikel schreiben, um die Fibonacci-Sequenz zu berühren und mich daran zu erinnern, die auf einem solchen grundlegenden Punkt basiert.
Was ist die Fibonacci-Sequenz?
\begin{align}
F_0 = 0 \quad \quad \quad \quad \quad \quad \quad \\
F_1 = 1 \quad \quad \quad \quad \quad \quad \quad \\
F_n = F_{n-1} + F_{n-2} \quad (n > 2)\\
\end{align}
Es ist eine Formel, die durch dargestellt wird.
Was soll ich hier besonders beim Programmieren tun?
fib.py
import time
def fib_stupid(n):
if(n == 0):
return 0
elif(n == 1):
return 1
else:
return fib_stupid(n-1) + fib_stupid(n-2)
#fib_stupid()Zweimal anrufen
start = time.time()
print(fib_stupid(40))
process_time = time.time() - start
print("Time :" + str(process_time))
102334155
Time :75.65844893455505[s]
Dies ist wie definiert. Die Bestellmenge für diese Berechnung ist jedoch sehr groß. Dies liegt daran, dass beim Auffinden von fib_stupid (n) fib_stupid (n-1) und fib_stupid (n-2) gefunden werden müssen, die mit einem fib_stupid () zweimal rekursiv aufgerufen werden, also immerhin $ Nur O (2 ^ {(n-1)} --2) $ ruft die Funktion auf. Wenn Sie $ F_9 $ finden möchten, müssen Sie $ F_8 $ und $ F_7 $ finden. Um $ F_8 $ zu finden, müssen Sie $ F_7 $ finden und $ F_7 $ zweimal berechnen. Es ist sehr ineffizient, weil es kommt.
Hier betrachten wir die dynamische Planungsmethode, um effizient zu denken.
Dynamische Planung ist ein Algorithmus mit einer rekursiven Struktur, der mehrere kleine Probleme aus dem Zielproblem findet und diese löst, um das ursprüngliche Problem zu lösen.
Im Folgenden stellen wir einen Algorithmus vor, der mit $ O (n), O (log (n)) $ berechnet werden kann.
fib.py
import sys
sys.setrecursionlimit(30000)
#Obere Grenzwerteinstellung für die rekursive Verarbeitung
def make_list_for_topdown(n):
l = [0]
l.append(1)
for i in range(n-1):
l.append(-1)
return l
lst = make_list_for_topdown(30000)
#Dieses Mal habe ich die Form der Liste so eingestellt, dass bis zu 3000 angefordert werden können
def fib_topdown(n):
if(lst[n] != -1):
return lst[n]
else:
lst[n] = fib_topdown(n-1) + fib_topdown(n-2)
return lst[n]
start = time.time()
print(fib_topdown(40))
fib_topdown(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.10364508628845215[s]
Dazu wird der Wert der Fibonacci-Zahlenspalte durch Erstellen eines Arrays mit dem Namen lst gespeichert. Dadurch werden doppelte Berechnungen wie oben vermieden. Es scheint, dass die Anzahl der Funktionsaufrufe dieselbe ist wie die vorherige fib_stupid (), aber da das Ergebnis im Array verbleibt, beträgt der Berechnungsbetrag $ O (2 (n-2)) $, was viel höher ist als zuvor. Es ist schneller.
fib.py
def fib_bottomup(n):
if(n < 2):
return n
else:
num_0 = 0
num_1 = 1
num_2 = -1
for i in range(n-1):
num_2 = num_0 + num_1
num_0 , num_1 = num_1, num_2
return num_2
start = time.time()
print(fib_bottomup(40))
fib_bottomup(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.023389101028442383[s]
Hier müssen Sie sich nur die letzten beiden Zustände mit num_0 und num_1 merken und addieren, und es gibt keine rekursive Struktur. Daher kann es mit $ O (n-2) $ berechnet werden.
Ich hatte erwartet, dass es ungefähr doppelt so schnell sein würde wie die Bottom-up-Reihenfolge, aber aus irgendeinem Grund war das Ergebnis ungefähr fünfmal schneller. Es wird angenommen, dass das Ergebnis des Erzeugens und Lesens der Liste ein solches Ergebnis ist (Wenn Sie genau überprüfen möchten, sollten Sie mehrere Verarbeitungszeiten durchführen und den Durchschnitt bilden und verteilen, aber sprechen Ich werde es diesmal weglassen, weil es abweicht.
Der allgemeine Term der Fibonacci-Sequenz kann durch Lösen der allmählichen Gleichung wie folgt ausgedrückt werden.
F_n = \frac{1}{\sqrt{5}}\Biggl\{\biggl( \frac{1+\sqrt{5}}{2}\biggl)^n- \biggl( \frac{1-\sqrt{5}}{2}\biggl)^n\Biggl\}
Wenden Sie sich daher wie folgt an.
fib.py
import math
def fib_general_term(n):
return math.floor((1/math.sqrt(5))*(((1+math.sqrt(5))/2)**n-((1-math.sqrt(5))/2)**n))
start = time.time()
print(fib_general_term(40))
try:
fib_general_term(30000)
except OverflowError:
print("OverflowError")
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
OverflowError
Time :0.00013494491577148438[s]
Dieses Mal wird der Dezimalpunkt ausgegeben, da die Routenoperation verwendet wird. Deshalb habe ich es mit der Bodenfunktion eingestellt. Außerdem liegt die Obergrenze von float bei 1,9796931348623157e + 308, und die Ausnahmebehandlung wird angewendet, da $ F_ {30000} $ größer als diese ist (es konnte berechnet werden, da int keine Obergrenze hat). Es ist jedoch immer noch möglich, dass es schneller ist als die beiden oben genannten dynamischen Planungsmethoden. Dies liegt daran, dass die Reihenfolge der Leistungsberechnung $ O (log (n)) $ ist. Der Prozess der n-fachen Multiplikation wird durch Berücksichtigung gerader und ungerader Zahlen verkürzt. Ein ähnliches Beispiel kann für einen Matrixausdruck in Betracht gezogen werden, daher werde ich es in diesem Beispiel erläutern (natürlich ist es keine vielseitige Programmierung, da die Ausnahmebehandlung angewendet wird).
Die allmähliche Gleichung der Fibonacci-Sequenz kann auch durch das Produkt der folgenden Matrizen ausgedrückt werden.
\begin{pmatrix}
F_{n} \\
F_{n-1}
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
F_{n-1} \\
F_{n-2}
\end{pmatrix}
Mit anderen Worten
A
:=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}\\
\begin{align}
\begin{pmatrix}
F_{n} \\
F_{n-1}
\end{pmatrix}
=A
\begin{pmatrix}
F_{n-1} \\
F_{n-2}
\end{pmatrix}
=A^2
\begin{pmatrix}
F_{n-2} \\
F_{n-3}
\end{pmatrix}
=A^{n-1}
\begin{pmatrix}
F_{n-(n-1)} \\
F_{n-1-(n-1)}
\end{pmatrix} \\
=A^{n-1}
\begin{pmatrix}
1 \\
0
\end{pmatrix}
\end{align}
Kann geschrieben werden. (n> 0) Wenn $ A ^ n $ $ n = 2 ^ k $ ist, kann es durch Wiederholen des Quadrats k-mal wie unten gezeigt erhalten werden. Wenn zum Beispiel $ n = 35 $ ist, Weil $ n = 2 ^ 5 + 2 ^ 1 + 2 ^ 0 $ $ A ^ {35} = A ^ {2 ^ 5} A ^ {2 ^ 1} A ^ {2 ^ 0} = ((((A ^ 2) ^ 2) ^ 2) ^ 2) ^ 2A ^ 2A Wird $ sein (Eine andere Denkweise Die Idee ist $ 35 = 2 * 17 + 1 = 2 * (2 * 8 + 1) + 1 = ... $. Ich persönlich dachte, es wäre einfacher zu verstehen. Wie Sie oben sehen können, endet es diesmal mit 6 Mal, dh $ log (35) $ Mal. Mit anderen Worten ist die Reihenfolge der Berechnung der Fibonacci-Sequenz durch die Potenz der Matrix in diesem Algorithmus $ log (n) $. Der spezifische Code lautet wie folgt (in Python erfolgt die Operation des Matrixausdrucks natürlich in numpy, aber da er mit der Berechnungsmethode des obigen allgemeinen Begriffs identisch ist, wird numpy nicht verwendet).
fib.py
def make_matrix(row_len,column_len):
matrix_c = [[0]*column_len for _ in range(row_len)]
return matrix_c
def matrix_mul(a,b):
c = make_matrix(len(a),len(b[0]))
for i in range(len(a)):
for k in range(len(b)):
for j in range(len(b[0])):
c[i][j] += a[i][k] * b[k][j]
return c
def matrix_pow(a,n):
b = make_matrix(len(a), len(a))
for i in range(len(a)):
b[i][i] = 1
while(n>0):
if(n & 1):
b = matrix_mul(a,b)
else:
pass
a = matrix_mul(a,a)
n >>= 1
return b
def fib_matrix(n):
if n == 0:
return 0
a = make_matrix(2,2)
a[0][0] = 1
a[0][1] = 1
a[1][0] = 1
a[1][1] = 0
a = matrix_pow(a, n)
return a[1][0]
start = time.time()
print(fib_matrix(40))
fib_matrix(30000)
process_time = time.time() - start
print("Time :" + str(process_time) + '[s]')
102334155
Time :0.002933025360107422[s]
Hier sehen Sie, dass es etwa zehnmal schneller ist als die Bottom-up-Methode.
Durch die Verwendung der oben genannten dynamischen Planungsmethode kann der Rechenaufwand erheblich reduziert werden. Dies ist eine grundlegende Angelegenheit, daher möchte ich zu einem späteren Zeitpunkt verschiedene DPs zusammenfassen.
Recommended Posts