python - sucesion - Cálculo eficiente de la serie de Fibonacci
serie fibonacci programacion (20)
Estoy trabajando en un problema de Project Euler : el de la suma de los números pares de Fibonacci.
Mi código:
def Fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return Fibonacci(n-1) + Fibonacci(n-2)
list1 = [x for x in range(39)]
list2 = [i for i in list1 if Fibonacci(i) % 2 == 0]
La solución del problema se puede encontrar fácilmente imprimiendo sum (list2). Sin embargo, toma mucho tiempo llegar a la lista2, supongo. ¿Hay alguna manera de hacer esto más rápido? ¿O está bien incluso de esta manera ...
(el problema: Al considerar los términos en la secuencia de Fibonacci cuyos valores no exceden los cuatro millones, encuentre la suma de los términos pares).
Una solución O (1)
Resulta que hay una buena fórmula recursiva para la suma de números pares de Fibonacci. El enésimo término en la secuencia de sumas de números pares de Fibonacci es S_{n} = 4*S_{n-1} + S_{n-2} + 2 prueba se deja al lector, pero implica probar 1) incluso números Fibo son cada tercera, 2) prueba de la fórmula anterior con inducción usando la definición de números Fibo. Usando la lógica de here , podemos derivar una fórmula cerrada para esto con un pequeño esfuerzo:
S_{n} = -1/2 + (1/4 + 3*sqrt(5)/20)*(2+sqrt(5))**n + (1/4 - 3*sqrt(5)/20)*(2-sqrt(5))**n
A pesar del sqrt , esto es integral para n integral, por lo que esto se puede calcular de manera conveniente usando las funciones prácticas de mi respuesta anterior, o usando un paquete como sympy para manejar las raíces exactamente.
import sympy as sp
one = sp.sympify(1) #to force casting to sympy types
k1 = -one/2
k2 = one/4 + 3*sp.sqrt(5)/20
k3 = one/4 - 3*sp.sqrt(5)/20
r1 = one
r2 = 2 + sp.sqrt(5)
r3 = 2 - sp.sqrt(5)
def even_sum_fibo(n):
#get the nth number in the sequence of even sums of Fibonacci numbers. If you want the sum of Fibos up to some number m, use n = m/3 (integer division)
return sp.simplify(k1*r1**n + k2*r2**n + k3*r3**n)
Aunque es una respuesta tardía, pero podría ser útil
fib_dict = {}
def fib(n):
try:
return fib_dict[n]
except:
if n<=1:
fib_dict[n] = n
return n
else:
fib_dict[n] = fib(n-1) + fib (n-2)
return fib(n-1) + fib (n-2)
print fib(100)
Esto es mucho más rápido que la forma tradicional
Basé esto en un artículo sobre números de Fibonacci en Wikipedia. La idea es evitar el bucle y la recursión y simplemente calcular el valor según sea necesario.
Al no ser un experto en matemáticas, seleccionó una de las fórmulas y la procesó para codificarla y ajustarla hasta que los valores salieran bien.
import cmath
def getFib(n):
#Given which fibonacci number we want, calculate its value
lsa = (1 / cmath.sqrt(5)) * pow(((1 + cmath.sqrt(5)) / 2), n)
rsa = (1 / cmath.sqrt(5)) * pow(((1 - cmath.sqrt(5)) / 2), n)
fib = lsa-rsa
#coerce to real so we can round the complex result
fn = round(fib.real)
return fn
#Demo using the function
s = ''''
for m in range(0,30):
s = s + ''('' + str(m) + '')'' + str(getFib(m)) + '' ''
print(s)
Basado en el hecho de que fib(n) = fib(n-1)+fib(n-2) , la solución directa es
def fib(n):
if (n <=1):
return(1)
else:
return(fib(n-1)+fib(n-2))
sin embargo, el problema aquí es que algunos valores se calculan varias veces y, por lo tanto, es muy ineficiente. La razón se puede ver en este boceto:
Esencialmente, cada llamada recursiva a la función fib tiene que calcular todos los números de Fibonacci previos para su propio uso. Entonces, el valor más calculado será fib (1) ya que tiene que aparecer en todos los nodos de hoja del árbol mostrados por respuesta de @kqr. La complejidad de este algoritmo es la cantidad de nodos del árbol, que es $ O (2 ^ n) $.
Ahora una mejor manera es hacer un seguimiento de dos números, el valor actual y el valor anterior, por lo que cada llamada no tiene que calcular todos los valores anteriores. Este es el segundo algoritmo en el boceto, y se puede implementar de la siguiente manera
def fib(n):
if (n==0):
return(0,1)
elif (n==1):
return(1,1)
else:
a,b = fib(n-1)
return(b,a+b)
La complejidad de este algoritmo es lineal $ O (n) $, y algunos ejemplos serán
>>> fib(1)
(1, 1)
>>> fib(2)
(1, 2)
>>> fib(4)
(3, 5)
>>> fib(6)
(8, 13)
Cualquier problema como este tardará mucho tiempo en ejecutarse si hay muchos niveles de recursión. La definición recursiva es buena para codificar el problema de una forma que se pueda entender fácilmente, pero si necesita que se ejecute más rápido, una solución iterativa, como la respuesta en este hilo , será mucho más rápida.
Dado el número inicial y el número máximo; Creo que la siguiente solución para fibonacci sería interesante. Lo bueno es que no incluye recursividad, lo que reduce la carga de memoria.
# starting number is a
# largest number in the fibonacci sequence is b
def fibonacci(a,b):
fib_series = [a, a]
while sum(fib_series[-2:]) <=b:
next_fib = sum(fib_series[-2:])
fib_series.append(next_fib)
return fib_series
print(''the fibonacci series for the range %s is %s''
%([3, 27], fibonacci(3, 27)))
the fibonacci series for the range [1, 12] is [3, 3, 6, 9, 15, 24]
El cálculo recursivo de Fibonacci será más ineficiente que hacerlo iterativamente. Mi recomendación es:
Tómese el tiempo para crear una clase Fibonacci como un iterador, y realice los cálculos de forma independiente para cada elemento en el índice, tal vez con algún decorador @memoize (y también here ) para almacenar en caché todos los cálculos anteriores.
¡Espero que esto ayude!
Esta es una versión mejorada de Fibonacci donde calculamos el número de Fibonacci una sola vez:
dicFib = { 0:0 ,1 :1 }
iterations = 0
def fibonacci(a):
if (a in dicFib):
return dicFib[a]
else :
global iterations
fib = fibonacci(a-2)+fibonacci(a-1)
dicFib[a] = fib
iterations += 1
return fib
print ("Fibonacci of 10 is:" , fibonacci(10))
print ("Fibonacci of all numbers:" ,dicFib)
print ("iterations:" ,iterations)
# (''Fibonacci of 10 is:'', 55)
# (''Fibonacci of all numbers:'', {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13, 8: 21, 9: 34, 10: 55})
# (''iterations:'', 9)
Aquí estamos almacenando Fibonacci de cada número en el diccionario. Entonces puede ver que calcula solo una vez para cada iteración y para Fibonacci (10) es solo 9 veces.
Este es un algoritmo muy rápido y puede encontrar n-ésimo número de Fibonacci mucho más rápido que el simple enfoque iterativo presentado en otras respuestas, aunque es bastante avanzado:
def fib(n):
v1, v2, v3 = 1, 1, 0 # initialise a matrix [[1,1],[1,0]]
for rec in bin(n)[3:]: # perform fast exponentiation of the matrix (quickly raise it to the nth power)
calc = v2*v2
v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
if rec==''1'': v1, v2, v3 = v1+v2, v1, v2
return v2
Puedes leer más sobre las matemáticas involucradas here .
Haskell 1 liner: -
fibs = 0 : (f 1 1) where f a b = a : f b (a+b)
Este código es extremadamente eficiente y calcula los números de Fibonacci hasta ( 10^1000 ) en menos de un segundo. Este código también será útil para este problema en Project Euler.
Hay una solución O (1): en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding
import math
PHI = (1 + math.sqrt(5)) / 2
SQRT5 = math.sqrt(5)
def fast_fib(n):
if n < 0:
raise ValueError(''Fibs for negative values are not defined.'')
return round(math.pow(PHI, n) / SQRT5)
La solución 2 de es mi favorita definitiva.
Sin embargo, en este caso específico, estamos perdiendo todos nuestros cálculos entre llamadas consecuentes dentro de la lista de comprensión:
list2 = [i for i in list1 if fib(i) % 2 == 0]
, así que decidí dar un paso más y memorizarlo entre los pasos del ciclo de la siguiente manera:
def cache_fib(ff):
comp = {0: 0, 1: 1}
def fib_cached(n, computed=comp):
return ff(n, computed)
return fib_cached
@cache_fib
def fib(n, computed={0: 0, 1: 1}):
if n not in computed:
computed[n] = fib(n - 1, computed) + fib(n - 2, computed)
return computed[n]
Me gustaría hacer esto, para encontrar el número N de Fibonacci, en Python:
def fib(n):
a, b = 0, 1
while n:
a, b, n = b, a+b, n-1
return a
Para encontrar la suma de los primeros n valores de Fonacocci pares directamente, coloque 3n + 2 en su método favorito para calcular eficientemente un solo número de Fibonacci, disminuya por uno y divida por dos ( fib((3*n+2) - 1)/2) ). ¿Cómo sobrevivieron los maniquíes matemáticos antes de OEIS ?
Puedes usar la ecuación con raíces cuadradas para calcular esto si no usas la aritmética de coma flotante, pero haz un seguimiento de los coeficientes de otra manera sobre la marcha. Esto proporciona un algoritmo exacto de tiempo esencialmente constante para los números de Fibonacci:
def rootiply(a1,b1,a2,b2,c):
'''''' multipy a1+b1*sqrt(c) and a2+b2*sqrt(c)... return a,b''''''
return a1*a2 + b1*b2*c, a1*b2 + a2*b1
def rootipower(a,b,c,n):
'''''' raise a + b * sqrt(c) to the nth power... returns the new a,b and c of the result in the same format''''''
ar,br = 1,0
while n != 0:
if n%2:
ar,br = rootiply(ar,br,a,b,c)
a,b = rootiply(a,b,a,b,c)
n /= 2
return ar,br
def fib(k):
'''''' the kth fibonacci number''''''
a1,b1 = rootipower(1,1,5,k)
a2,b2 = rootipower(1,-1,5,k)
a = a1-a2
b = b1-b2
a,b = rootiply(0,1,a,b,5)
# b should be 0!
assert b == 0
return a/2**k/5
if __name__ == "__main__":
assert rootipower(1,2,3,3) == (37,30) # 1+2sqrt(3) **3 => 13 + 4sqrt(3) => 39 + 30sqrt(3)
assert fib(10)==55
Python no optimiza la recursividad de cola, por lo que la mayoría de las soluciones presentadas aquí fallarán con Error: maximum recursion depth exceeded in comparison si n es demasiado grande (y en grande, me refiero a 1000).
El límite de recursión se puede aumentar, pero hará que Python falle en el desbordamiento de la pila en el sistema operativo.
Tenga en cuenta la diferencia en el rendimiento entre fib_memo / fib_local y fib_lru / fib_local_exc : LRU caché es mucho más lento y ni siquiera se completó, ya que produce un error de tiempo de ejecución para n = ~ 500:
import functools
from time import clock
#import sys
#sys.setrecursionlimit()
@functools.lru_cache(None)
def fib_lru(n):
if n < 2:
return n
return fib_lru(n-1) + fib_lru(n-2)
def fib_memo(n, computed = {0: 0, 1: 1}):
if n not in computed:
computed[n] = fib_memo(n-1, computed) + fib_memo(n-2, computed)
return computed[n]
def fib_local(n):
computed = {0: 0, 1: 1}
def fib_inner(n):
if n not in computed:
computed[n] = fib_inner(n-1) + fib_inner(n-2)
return computed[n]
return fib_inner(n)
def fib_local_exc(n):
computed = {0: 0, 1: 1}
def fib_inner_x(n):
try:
computed[n]
except KeyError:
computed[n] = fib_inner_x(n-1) + fib_inner_x(n-2)
return computed[n]
return fib_inner_x(n)
def fib_iter(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
def benchmark(n, *args):
print("-" * 80)
for func in args:
print(func.__name__)
start = clock()
try:
ret = func(n)
#print("Result:", ret)
except RuntimeError as e:
print("Error:", e)
print("Time:", "{:.8f}".format(clock() - start))
print()
benchmark(500, fib_iter, fib_memo, fib_local, fib_local_exc, fib_lru)
Resultados:
fib_iter
Time: 0.00008168
fib_memo
Time: 0.00048622
fib_local
Time: 0.00044645
fib_local_exc
Time: 0.00146036
fib_lru
Error: maximum recursion depth exceeded in comparison
Time: 0.00112552
La solución iterativa es con mucho la más rápida y no corrompe la pila incluso para n=100k (0.162 segundos). No devuelve los números intermedios de Fibonacci de hecho.
Si quiere calcular el n ° e incluso el número de Fibonacci, podría adaptar el enfoque iterativo de esta manera:
def fib_even_iter(n):
a, b = 0, 1
c = 1
while c < n:
a, b = b, a + b
if a % 2 == 0:
c += 1
return a
O si está interesado en cada número par en el camino, use un generador :
def fib_even_gen(n):
a, b = 0, 1
c = 1
yield a
while c < n:
a, b = b, a + b
if a % 2 == 0:
yield a
c += 1
return a
for i, f in enumerate(fib_even_gen(100), 1):
print("{:3d}. {:d}".format(i, f))
Resultado:
1. 0
2. 2
3. 8
4. 34
5. 144
6. 610
7. 2584
8. 10946
9. 46368
10. 196418
11. 832040
12. 3524578
13. 14930352
14. 63245986
15. 267914296
16. 1134903170
17. 4807526976
18. 20365011074
19. 86267571272
20. 365435296162
21. 1548008755920
22. 6557470319842
23. 27777890035288
24. 117669030460994
25. 498454011879264
26. 2111485077978050
27. 8944394323791464
28. 37889062373143906
29. 160500643816367088
30. 679891637638612258
31. 2880067194370816120
32. 12200160415121876738
33. 51680708854858323072
34. 218922995834555169026
35. 927372692193078999176
36. 3928413764606871165730
37. 16641027750620563662096
38. 70492524767089125814114
39. 298611126818977066918552
40. 1264937032042997393488322
41. 5358359254990966640871840
42. 22698374052006863956975682
43. 96151855463018422468774568
44. 407305795904080553832073954
45. 1725375039079340637797070384
46. 7308805952221443105020355490
47. 30960598847965113057878492344
48. 131151201344081895336534324866
49. 555565404224292694404015791808
50. 2353412818241252672952597492098
51. 9969216677189303386214405760200
52. 42230279526998466217810220532898
53. 178890334785183168257455287891792
54. 757791618667731139247631372100066
55. 3210056809456107725247980776292056
56. 13598018856492162040239554477268290
57. 57602132235424755886206198685365216
58. 244006547798191185585064349218729154
59. 1033628323428189498226463595560281832
60. 4378519841510949178490918731459856482
61. 18547707689471986212190138521399707760
62. 78569350599398894027251472817058687522
63. 332825110087067562321196029789634457848
64. 1409869790947669143312035591975596518914
65. 5972304273877744135569338397692020533504
66. 25299086886458645685589389182743678652930
67. 107168651819712326877926895128666735145224
68. 453973694165307953197296969697410619233826
69. 1923063428480944139667114773918309212080528
70. 8146227408089084511865756065370647467555938
71. 34507973060837282187130139035400899082304280
72. 146178119651438213260386312206974243796773058
73. 619220451666590135228675387863297874269396512
74. 2623059926317798754175087863660165740874359106
75. 11111460156937785151929026842503960837766832936
76. 47068900554068939361891195233676009091941690850
77. 199387062373213542599493807777207997205533596336
78. 844617150046923109759866426342507997914076076194
79. 3577855662560905981638959513147239988861837901112
80. 15156039800290547036315704478931467953361427680642
81. 64202014863723094126901777428873111802307548623680
82. 271964099255182923543922814194423915162591622175362
83. 1152058411884454788302593034206568772452674037325128
84. 4880197746793002076754294951020699004973287771475874
85. 20672849399056463095319772838289364792345825123228624
86. 87571595343018854458033386304178158174356588264390370
87. 370959230771131880927453318055001997489772178180790104
88. 1571408518427546378167846658524186148133445300987550786
89. 6656593304481317393598839952151746590023553382130993248
90. 28197781736352815952563206467131172508227658829511523778
91. 119447720249892581203851665820676436622934188700177088360
92. 505988662735923140767969869749836918999964413630219877218
93. 2143402371193585144275731144820024112622791843221056597232
94. 9079598147510263717870894449029933369491131786514446266146
95. 38461794961234640015759308940939757590587318989278841661816
96. 162926777992448823780908130212788963731840407743629812913410
97. 690168906931029935139391829792095612517948949963798093315456
98. 2923602405716568564338475449381171413803636207598822186175234
99. 12384578529797304192493293627316781267732493780359086838016392
100. 52461916524905785334311649958648296484733611329035169538240802
Time: 0.00698620
Estos son los primeros 100 números pares de Fibonacci en ~ 7ms e incluye la sobrecarga de impresión en la terminal (fácil de subestimar en Windows).
Sí. La solución recursiva primitiva requiere mucho tiempo. La razón de esto es que para cada número calculado, necesita calcular todos los números anteriores más de una vez. Eche un vistazo a la siguiente imagen.
Representa el cálculo de Fibonacci(5) con su función. Como puede ver, calcula el valor de Fibonacci(2) tres veces y el valor de Fibonacci(1) cinco veces. Eso empeora cada vez más cuanto más alto sea el número que desee calcular.
Lo que lo hace aún peor es que con cada número de Fibonacci que calcules en tu lista, no usas los números previos que conoces para acelerar el cálculo: calculas cada número "desde cero".
Hay algunas opciones para hacer esto más rápido:
1. Crea una lista "de abajo hacia arriba"
La manera más fácil es simplemente crear una lista de números de Fibonacci hasta el número que desee. Si haces eso, construyes "de abajo hacia arriba" o por así decirlo, y puedes reutilizar los números anteriores para crear el siguiente. Si tiene una lista de los números de Fibonacci [0, 1, 1, 2, 3] , puede usar los dos últimos números en esa lista para crear el siguiente número.
Este enfoque se vería así:
>>> def fib_to(n):
... fibs = [0, 1]
... for i in range(2, n+1):
... fibs.append(fibs[-1] + fibs[-2])
... return fibs
...
Entonces puedes obtener los primeros 20 números de Fibonacci haciendo
>>> fib_to(20)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765]
O puede obtener el número 17 de Fibonacci de una lista de los primeros 40 haciendo
>>> fib_to(40)[17]
1597
2. Memoización (técnica relativamente avanzada)
Existe otra alternativa para hacerlo más rápido, pero también es un poco más complicado. Dado que su problema es que vuelve a calcular los valores que ya ha calculado, puede optar por guardar los valores que ya ha calculado en un dict y tratar de obtenerlos antes de volver a calcularlos. Esto se llama memorización . Puede parecerse a esto:
>>> def fib(n, computed = {0: 0, 1: 1}):
... if n not in computed:
... computed[n] = fib(n-1, computed) + fib(n-2, computed)
... return computed[n]
Esto le permite calcular grandes números de Fibonacci en un abrir y cerrar de ojos:
>>> fib(400)
176023680645013966468226945392411250770384383304492191886725992896575345044216019675
De hecho, esta es una técnica tan común que Python 3 incluye un decorador para hacer esto por usted. ¡Te presento, memoria automática!
import functools
@functools.lru_cache(None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
Esto hace más o menos lo mismo que la función anterior, pero con todas las cosas computed manejadas por el decorador lru_cache .
3. Solo cuenta hacia arriba (una solución iterativa ingenua)
Un tercer método, como sugiere Mitch, es simplemente contar hacia arriba sin guardar los valores intermedios en una lista. Podrías imaginarte haciendo
>>> def fib(n):
... a, b = 0, 1
... for _ in range(n):
... a, b = b, a+b
... return a
No recomiendo estos dos últimos métodos si su objetivo es crear una lista de números de Fibonacci. fib_to(100) va a ser mucho más rápido que [fib(n) for n in range(101)] porque con este último, todavía se obtiene el problema de calcular cada número en la lista desde cero.
Solución en R, el punto de referencia calcula de 1 a 1000 series de números de Fibonacci en 1.9 segundos. Sería mucho más rápido en C ++ o Fortran, de hecho, desde que escribí la publicación inicial, escribí una función equivalente en C ++ que se completó en unos impresionantes 0.0033 segundos, incluso Python completó en 0.3 segundos.
#Calculate Fibonnaci Sequence
fib <- function(n){
if(n <= 2)
return(as.integer(as.logical(n)))
k = as.integer(n/2)
a = fib(k + 1)
b = fib(k)
if(n %% 2 == 1)
return(a*a + b*b)
return(b*(2*a - b))
}
#Function to do every fibonacci number up to nmax
doFib <- function(nmax = 25,doPrint=FALSE){
res = sapply(0:abs(nmax),fib)
if(doPrint)
print(paste(res,collapse=","))
return(res)
}
#Benchmark
system.time(doFib(1000))
#user system elapsed
# 1.874 0.007 1.892
Una manera rápida es calcular el número fib (n / 2) recursivamente:
fibs = {0: 0, 1: 1}
def fib(n):
if n in fibs: return fibs[n]
if n % 2 == 0:
fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
return fibs[n]
else:
fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
return fibs[n]
from time import time
s=time()
print fib(1000000)
print time()-s
int count=0;
void fibbo(int,int);
void main()
{
fibbo(0,1);
getch();
}
void fibbo(int a,int b)
{
count++;
printf(" %d ",a);
if(count<=10)
fibbo(b,a+b);
else
return;
}