J'ai appris la planification dynamique lorsque j'étais en deuxième année à l'école de premier cycle. Cependant, si je n'utilise pas ces connaissances, j'oublierai de plus en plus. J'écrirai cet article pour aborder et me souvenir de la séquence de Fibonacci basée sur un point aussi basique.
Quelle est la séquence de Fibonacci?
\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}
C'est une formule représentée par.
Que dois-je faire en particulier dans la programmation ici?
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()Appeler deux fois
start = time.time()
print(fib_stupid(40))
process_time = time.time() - start
print("Time :" + str(process_time))
102334155
Time :75.65844893455505[s]
Ceci est tel que défini. Cependant, la quantité commandée pour ce calcul est très importante. Après tout, il est nécessaire de trouver fib_stupid (n-1) et fib_stupid (n-2) lors de la recherche de fib_stupid (n), et il est appelé récursivement deux fois avec un fib_stupid (), donc après tout, $ O (2 ^ {(n-1)} --2) $ finira par appeler la fonction. En fait, si vous voulez trouver $ F_9 $, vous devez trouver $ F_8 $ et $ F_7 $. Pour trouver $ F_8 $, vous devez trouver $ F_7 $, et vous devez calculer $ F_7 $ deux fois. C'est très inefficace parce que ça vient.
Ici, afin de penser efficacement, nous allons considérer la méthode de planification dynamique.
Le procédé de planification dynamique est un algorithme ayant une structure récursive qui résout le problème d'origine en trouvant une pluralité de petits problèmes à partir du problème cible et en les résolvant.
Ci-dessous, nous allons introduire un algorithme qui peut être calculé avec $ O (n), O (log (n)) $.
fib.py
import sys
sys.setrecursionlimit(30000)
#Réglage de la limite supérieure pour le traitement récursif
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)
#Cette fois, j'ai défini la forme de la liste afin que jusqu'à 3000 puissent être demandés
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]
Pour cela, la valeur de la colonne de nombre de Fibonacci est enregistrée en créant un tableau appelé lst. Cela évite les calculs en double comme celui ci-dessus. Il semble que le nombre d'appels de fonction soit le même que le précédent fib_stupid (), mais comme le résultat reste dans le tableau, le montant du calcul est $ O (2 (n-2)) $, ce qui est beaucoup plus élevé qu'avant. C'est plus rapide.
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]
Ici, il vous suffit de mémoriser les deux derniers états avec num_0 et num_1 et de les additionner, et il n'a pas de structure récursive. Par conséquent, il peut être calculé avec $ O (n-2) $.
Je m'attendais à ce que ce soit environ deux fois plus rapide que l'ordre ascendant, mais pour une raison quelconque, le résultat était environ cinq fois plus rapide. On pense que le résultat du processus de génération et de lecture de la liste est un tel résultat (si vous voulez vérifier avec précision, vous devez faire plusieurs temps de traitement et faire la moyenne et distribuer, mais parlez Je vais l'omettre cette fois car il s'écarte.)
Le terme général de la séquence de Fibonacci peut être exprimé comme suit en résolvant l'équation graduelle.
F_n = \frac{1}{\sqrt{5}}\Biggl\{\biggl( \frac{1+\sqrt{5}}{2}\biggl)^n- \biggl( \frac{1-\sqrt{5}}{2}\biggl)^n\Biggl\}
Par conséquent, appliquez comme suit.
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]
Cette fois, la virgule décimale sort car l'opération d'itinéraire est utilisée. Par conséquent, je l'ai ajusté avec la fonction de sol. De plus, la limite supérieure de float est 1.9796931348623157e + 308, et la gestion des exceptions est appliquée car $ F_ {30000} $ est plus grand que cela (il était possible de calculer car int n'a pas de limite supérieure). Cependant, il est toujours possible que ce soit plus rapide que les deux méthodes de planification dynamique ci-dessus. Cela est dû au fait que l'ordre du calcul de la puissance est $ O (log (n)) $. Le processus de multiplication de n fois est raccourci en considérant les nombres pairs et impairs. Un exemple similaire peut être considéré dans une expression matricielle, je vais donc l'expliquer dans cet exemple (bien sûr, ce n'est pas une programmation polyvalente car la gestion des exceptions est appliquée).
L'expression progressive de la séquence de Fibonacci peut également être exprimée par le produit des matrices suivantes.
\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}
En d'autres termes
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}
Peut être écrit. (n> 0) Si $ A ^ n $ vaut $ n = 2 ^ k $, il peut être obtenu en répétant le carré k fois comme indiqué ci-dessous. Par exemple, si $ n = 35 $, Parce que $ 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 Sera $ (Une autre façon de penser L'idée est 35 $ = 2 * 17 + 1 = 2 * (2 * 8 + 1) + 1 = ... $. J'ai personnellement pensé que ce serait plus facile à comprendre). Comme vous pouvez le voir ci-dessus, cette fois, il se termine par 6 fois, soit $ log (35) $ fois. En d'autres termes, l'ordre du calcul de la séquence de Fibonacci par la puissance de la matrice dans cet algorithme est $ log (n) $. Le code spécifique est le suivant (en python, bien sûr, le fonctionnement de l'expression matricielle est en numpy, mais comme c'est le même que la méthode de calcul par le terme général ci-dessus, numpy n'est pas utilisé).
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]
Ici, vous pouvez voir qu'il est environ 10 fois plus rapide que la méthode ascendante.
En utilisant la méthode de planification dynamique ci-dessus, la quantité de calcul peut être considérablement réduite. Il s’agit d’une question fondamentale, je voudrais donc résumer les différents PDD à une date ultérieure.
-Accélérer le calcul de la séquence de Fibonacci par la méthode de planification dynamique. https://yosuke-furukawa.hatenablog.com/entry/20120120/1327056359
Recommended Posts