Crea una cuenta o inicia sesi贸n

隆Contin煤a aprendiendo sin ning煤n costo! 脷nete y comienza a potenciar tu carrera

Optimizaci贸n de Fibonacci

3/24
Recursos

Aportes 271

Preguntas 44

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

Tengan cuidado con fibonaccis muy grandes, podr铆an encontrarse con este pokemon legendario

Por que usar diccionario y no listas?

El algoritmo que usa Python internamente para buscar un elemento en un diccionario es muy distinto que el que utiliza para buscar en listas.

Para buscar en las listas, se utiliza un algoritmos de comparaci贸n que tarda cada vez m谩s a medida que la lista se hace m谩s larga. En cambio, para buscar en diccionarios se utiliza un algoritmo llamado hash, que se basa en realizar un c谩lculo num茅rico sobre la clave del elemento, y tiene una propiedad muy interesante: sin importar cu谩ntos elementos tenga el diccionario, el tiempo de b煤squeda es siempre aproximadamente igual (O(1)).

Este algoritmo de hash es tambi茅n la raz贸n por la cual las claves de los diccionarios deben ser inmutables, ya que la operaci贸n hecha sobre las claves debe dar siempre el mismo resultado, y si se utilizara una variable mutable esto no ser铆a posible.

link

Para el n煤mero 50 en recursivo mi computadora tardo: 5,394.27 segundos cerca de 1.5 horas
Resultado Recursivo: 20365011074
Tiempo Recursivo 5394.270832061768

Procesador (Intel庐 Core鈩 i7-8850H CPU @ 2.60GHz)
Memoria Ram 32gb

En este video explican muy bien la utilizaci贸n de 鈥渕emoization鈥 para optimizar la funci贸n de fibonacci https://www.youtube.com/watch?v=Qk0zUZW-U_M

Para entender mejor escrib铆

memo[n] = resultado
        print(memo)

Y como resultado

![](

En esta pagina se muestra la soluci贸n de Fibonacci recursivo y Fibonacci Memoized con una animaci贸n.
https://www.cs.usfca.edu/~galles/visualization/DPFib.html

Con un decorador podr铆amos hacer un m茅todo general para memorizar

import hashlib
from time import time

data_memo = {}


def memoization(func):
    def func_wrapper(*kwargs):
        _hash = hashlib.md5((func.__name__+str(kwargs)).encode()).hexdigest()
        if _hash in data_memo:
            return data_memo[_hash]
        _result = func(*kwargs)
        data_memo[_hash] = _result
        return _result
    return func_wrapper


@memoization
def fibonacci_recursive_memo(n):
    return 1 if n == 0 or n == 1 else fibonacci_recursive_memo(n-1) + fibonacci_recursive_memo(n-2)


def fibonacci_recursive(n):
    return 1 if n == 0 or n == 1 else fibonacci_recursive(n-1) + fibonacci_recursive(n-2)


if __name__ == '__main__':
    n = int(input('chose a number: '))
    start = time()
    result = fibonacci_recursive_memo(n)
    end = time()
    print(f"result with memo {result} in {end-start}")
    start = time()
    result = fibonacci_recursive(n)
    end = time()
    print(f"result without memo {result} in {end-start}")

Dato curioso:

Si cambian por:

resultado = "{:.5e}".format(fibonacci_dinamico(n))

Tienen el resultado en notaci贸n cientifica.
El fibonacci de 1000 es 7.03 E 208
En relaci贸n,** los atomos de todo el planeta son 10 E 50**

Pdta: Antes de 2000 deja de funcionar porque el numero es muy largo, para el que se anime a averiguar como solucionarlo

Comparto una modificaci贸n que le hice al c贸digo, donde podemos ver como trabaja internamente, guardando cada n煤mero de fibonacci calculado para posteriormente consultarlo y usarlo para el calculo del numero siguiente.

def fibo_dinamico(n, memo={}):
    step = 0
    if n == 0:
        step += 1
        print(f'.........Caso base - Fibo({n}) = {0}')
        return 0
    elif n == 1:
        step += 1
        print(f'.........Caso base - Fibo({n}) = {0}')
        return 1
    try:
        print(f'..Consultando en dic_memo Fibo({n})')
        return memo[n]
    except KeyError:
        print(f'....No existe Fibo({n}) en el diccionario')
        print(f'......Calculando Fibo({n})')
        resultado = fibo_dinamico(n-1, memo) + fibo_dinamico(n-2, memo)
        memo[n] = resultado
        print(f'.........Se guardo Fibo({n})={resultado} en el diccionario')
    return resultado

if __name__ == '__main__':
    n = 5
    num_fibo_n = fibo_dinamico(n)
    print('*'*40)
    print(f'El numero Fibo({n}) = {num_fibo_n}')

https://github.com/karlbehrensg/programacion-dinamica-y-estocastica
Optimizaci贸n de Fibonacci

La serie de Fibonacci se representa como Fn = Fn-1 + Fn-2 y es muy simple implementarla de forma recursiva en c贸digo. Sin embargo es muy ineficiente hacerlo simplemente recursivo, ya que repetimos varias veces el mismo computo.

Si te fijas en la imagen te dar谩s cuenta de que repetimos varias veces el calculo para f(4), f(3), f(2), f(1) y f(0), esto significa que nuestro algoritmo crece de forma exponencial O(2^n).

Para optimizar nuestro algoritmo implementaremos en primer lugar la funci贸n recursiva para luego dar paso a la memorizaci贸n, con esto las mejoras ser谩n realmente sorprendentes.

# Importamos la librer铆a sys para subir el limite de recursividad de Python.
import sys

# La funci贸n recursiva realiza varias veces los mismos c谩lculos.
def fibonacci_recursivo(n):
    if n == 0 or n == 1:
        return 1

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


# En cambio en la funci贸n din谩mica vamos a utilizar la t茅cnica de la
# memorizaci贸n, guardando los resultados ya hechos en un diccionario.
def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1


    # Primero intentamos buscar el resultado en memoria.
    try:
        return memo[n]

    # En caso de no existir realizamos el c谩lculo.
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado

        return resultado

if __name__ == '__main__':
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un numero: '))
    resultado = fibonacci_dinamico(n)
    print(resultado)

Resumen para estudiar

-Con fibonacci_rescursivo hace varios calculos, independiente de si los ah calculado o no.
Ej: Si queremos el fibonacci de 6 en algun momento calcularemos 5 veces el fibonacci de 2, ahora imaginense de los demas numeros, o incluso si es un numero enorme como 500.

-Fibonacci_dinamico la gran ventaja que nos ofrece es que guarda el computo ya hecho, ejemplo, si ya ah calculado fibonacci de 2, no es necesario recalcularlo otra vez, ya que la primera vez que lo hace, lo guarda dentro de un diccionario, osea que el programa tiene memoria

-La ventaja de guardarlo dentro de diccionarios es que su complejidad es 0(1), quiere decir que no importa cuan grande sea el diccionario, se tardar谩 lo mismo buscando un elemento, ya que en un diccionario se busca la clave correspondiente al resultado.

Para entender mejor el porque de los diccionarios, nuestro compa帽ero @Daniel Torres lo explica mas a fondo en comentarios mas abajo

En la forma de calcular la intensidad de campo el茅ctrico o magn茅tico de ciertos sistemas, deben utilizarse funciones u operaciones que dependen del resultado de una o varias iteraciones previas. Se les conoce como elementos finitos.

Ac谩 un link para que se fijen: (https://www.researchgate.net/publication/260591308_METODO_DE_ELEMENTOS_FINITOS_EN_DOS_DIMENSIONES_PARA_ESTUDIO_DE_PROPAGACION_EN_POTENCIALES_ELECTROSTATICOS)

Generalmente se utilizan f贸rmulas matem谩ticas que ya han modelado un sistema, es decir que esas f贸rmulas describen el comportamiento de ese sistema de manera muy acertada.

Tambi茅n en matem谩ticas financieras, los c谩lculos de algunos tipos de intereses tienen f贸rmulas recursivas.

En esta imagen, los valores de las cajas en azul son valores que ya se han calculado, por esto s贸lo se consulta el valor en el diccionario y pasa de ser una funci贸n recursiva con complejidad O(2**n) a una funci贸n recursiva O(n) [sin embargo el espacio donde se almacenan los resultados tambien se convierte en O(n)]

Conclusion
Memoization es una t茅cnica de funciones con almacenamiento (caching functions) es decir las funciones tienen memoria, y los ususarios de las funciones no necesitan saber si la funci贸n tiene memoria o no. En ocasiones este tipo de funciones no requieren hacer ningun calculo sino devolver el resultado almacenado.

En este articulo pueden encontrar la informaci贸n que les compart铆 y m谩s detalles.

https://medium.com/@chialunwu/wtf-is-memoization-a2979594fb2a

He encontrado este interesante articulo que fortalece lo aprendido durante esta clase http://www.cs.wm.edu/~rml/teaching/python/functions/recursion.html
Recomiendo leerlo despues de acabar la clase

Dejo el c贸digo con comentarios

'''
En este caso se usaran la memoization para optimizar el algoritmo recursivo
Esta tecnica sacrifica espacio en memoria por tiempo
'''
import sys
#Funci贸n fibonacci recursivo
def fibonacciRecursivo(numero):
    if (numero == 1 or numero == 0):
        return 1

    return fibonacciRecursivo(numero - 1) + fibonacciRecursivo(numero - 2)
#Funci贸n Fibonacci memoization
#Como parametro tiene el numero y un diccionario inicializado sin tama帽o fijo y vacio
def fibonacciDinamico(numero, diccionario = {}):
    #Este es el caso base que finaliza la recursion
    if(numero ==1 or numero == 0):
        return 1
    #La funci贸n try verifica si una operaci贸n puede ser ejecutada. En este caso verifica
    #si el diccionario contiene datos para la palabra clave o key: numero
    #si exite retornara el resultado sin ejecutar la recursi贸n, es en este punto donde 
    #mejora los tiempos de procesamiento, es m谩s rapido buscar en un diccionario que ejecutar la recursi贸n 
    #En pocas palabras si el fibonacci de un numero ya se calculo antes estara guardado en memoria
    try:
        return diccionario[numero]
    #La funci贸n excep se ejecuta cuando no se logra ejecutar o no se obtienen datos en el try
    except:
        #Si es un numero que no se ha calculado nunca se ejecutara la recursi贸n normal
        resultado = fibonacciDinamico(numero -1, diccionario) + fibonacciDinamico(numero - 2, diccionario)
        #Salvo que el resultado se guardara en el diccionario usando como palabra clave el numero para el que se calcula
        #De esta manera se ira creando la base de datos de los resultados para cada numero nuevo
        diccionario[numero] = resultado
        return resultado

if __name__ ==('__main__'):
    sys.setrecursionlimit(100)
    dato = int(input('Digita un numero para calcular su Fibonacci: '))
    print(f'El fibonaci de {dato} es: {fibonacciDinamico(dato)}')
    print(f'El fibonaci de {dato} es: {fibonacciRecursivo(dato)}')

Hice la siguiente locura para el fibonacci recursivo:

Modifique la funcion para que mostrara calculando fibonacci de n

llame el programa dandole una entrada desde archivo y sacando los resultados a otro archivo, se cuentan las lineas y se sabe cuantas recursiones hizo.

fibonacci de 20:

~/cursoEstocastica $ echo 20 > numero20
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero20 >fr20.txt 

~/prueba fibonacci $ tail -n3 fr20.txt
calculando fibonacci de 1
calculando fibonacci de 0
10946

~/prueba_fibonacci $ wc -l fr20.txt
21892 

fibonacci de 20 es 10,946 iteraciones: 21,891

Ahora para n = 30

~/cursoEstocastica $ echo 30 > numero30
 ~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero30 >fr30.txt
  
tail -n3 fr30.txt
calculando fibonacci de 1
calculando fibonacci de 0
1346269

~/prueba_fibonacci $ wc -l fr30.txt
2692538 

fibonacci de 30 es 1,346,269 iteraciones: 2,692,537

ahora para n=40

~/cursoEstocastica $ echo 40 > numero40
~/cursoEstocastica $ /bin/python3 optimizacion1_fibonacci.py <numero40 >fr40.txt 

tail -n3 fr40.txt
calculando fibonacci de 1
calculando fibonacci de 0
165580141

~/prueba_fibonacci $ wc -l fr40.txt
331160282

fibonacci de 40 es 165,580,141 iteraciones: 331,160,282

La locura es que casi acabo con mi disco duro:

~/prueba fibonacci $ ls -l
total 8480784
-rw-rw-r-- 1 julio julio     569422 jun 23 18:40 fr20.txt
-rw-rw-r-- 1 julio julio   70034644 jun 23 18:42 fr30.txt
-rw-rw-r-- 1 julio julio 8613691911 jun 23 18:49 fr40.txt
-rw-rw-r-- 1 julio julio          3 jun 23 18:40 numero20
-rw-rw-r-- 1 julio julio          3 jun 23 18:42 numero30
-rw-rw-r-- 1 julio julio          3 jun 23 18:43 numero40
-rw-rw-r-- 1 julio julio          0 jun 23 19:15 prueba.txt

la prueba con n=40 se comio 8 gigas!!!

Pueden conseguir una explicaci贸n muy buena (parte visual incluida) y otra forma de implementar esto, en el siguiente video:
https://www.youtube.com/watch?v=Qk0zUZW-U_M

Optimizaci贸n de Fibonacci:

  • La soluci贸n recursiva cl谩sica es muy ineficiente, puesto que crece de manera exponencial (O(n**2), ya que llamamos a la funci贸n 2 veces m谩s por cada incremento de n)
  • Logramos optimizar esta funci贸n a una complejidad lineal (O(n)) guardando en un diccionario los resultados obtenidos previamente.

Notas:

  • En python es usual el uso de la expresi贸n try/except (pedir perd贸n antes que pedir permiso)
  • La recursividad m谩xima en python por defecto es 1000, se puede modificar en el comando sys.setrecursionlimit(<nuevo_limite>)
  • Puesto que intercambiamos tiempo por memoria, si excedemos las capacidades de nuestro computador puede aparecernos un error de memoria: MemoryError: Stack overflow

Creo que hacer programas que resuelvan una sumatoria matem谩tica con Memoization puede optimizar mucho el tiempo de respuesta con n煤meros grandes.

En este algoritmo los fibonacci se van almacenando en el diccionario memo, digamos queremos obtener F(4) , lo que hace es :
f(4) = f(3) + f(2), no hay ningun valor en memo, entonces sigue la recursividad:
f(4) = f(2) + f(1) + f(1) + f(0), aca ya sabemos que f(1 o 0) = 1, estos fibonacci no los guarda, solo retorna 1
f(4) = f(2) + 1 + 1 + 1, entonces ya obtuvo f(2) = 2 y lo almacena en memo:
f(4) = 2 + 1 + 1 +1, obtuvo f(3) y lo almacena en memo
f(4) = 5, y hace lo mismo de forma progresiva
Asi lo logre entender mejor.

Wow Excelente, la verdad que me qued茅 sorprendido y por poco me salto este curso.

En mi maquina paso algo curioso, con el c贸digo de programaci贸n din谩mica a partir del 2998 no me muestra el resultado en pantalla, tengo algunas cosas abiertas como Docker, mi teoria es que se quedo sin memoria RAM en ese punto para poder procesar m谩s, 驴o que podr铆a estar sucediendo?

Modifique el c贸digo para poder ver la cantidad de veces que se ejecuta el ingreso a la funci贸n tanto recursiva como din谩mica, esto verifica que la funci贸n recursiva pasa de ser exponencial (O(n**n)) a la funci贸n din谩mica ser lineal (O(n)).
algunos de los resultados:

La secuencia de fibonacci en la posici贸n 5 es 8
Se ejecuto la funci贸n recursiva 15 veces
Se ejecuto la funci贸n din谩mica 9 veces

Tambien para el n煤mero 15

La secuencia de fibonacci en la posici贸n 15 es 987
Se ejecuto la funci贸n recursiva 1973 veces
Se ejecuto la funci贸n din谩mica 29 veces

Y para el n煤mero 25:

La secuencia de fibonacci en la posici贸n 25 es 121393
Se ejecuto la funci贸n recursiva 242785 veces
Se ejecuto la funci贸n din谩mica 49 veces

Es increible el cambio, para n煤meros mas grandes puse comentarios al llamado a la funci贸n recursiva o no terminaria, los cambios de la din谩mica son:

La secuencia de fibonacci en la posici贸n 50 es 20365011074
Se ejecuto la funci贸n din谩mica 99 veces
La secuencia de fibonacci en la posici贸n 100 es 573147844013817084101
Se ejecuto la funci贸n din谩mica 199 veces
La secuencia de fibonacci en la posici贸n 500 es 22559151616193633087251269503607207204601132491375819058863886641847
4627738686883405015987052796968498626
Se ejecuto la funci贸n din谩mica 999 veces
Escoge un n煤mero: 5000
La secuencia de fibonacci en la posici贸n 5000 es 7088069496231111407908953313902398529655056082228.....(son demasiados n煤meros)
Se ejecuto la funci贸n din谩mica 9999 veces

Como se ve la cantidad de veces que se ingreso a la funci贸n se vuelve lineal, dejare el c贸digo respondiendo una pregunta para no hacer este post mas largo.

Detuve el cronometro de fibonacci_recursivo en 13 min. y aun no llegaba al resultado. Con fibonacci_dinamico fue super r谩pido

Excelente tema y explicaci贸n. A tener en cuenta en el algoritmo del profesor: Fibonacci de 0 es 0 y de 1 es 1

import time
import sys

def fibonacci_recursivo(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_recursivo(n - 1) + fibonacci_recursivo(n -2)

def fibonacci_dinamico(n, memo = {}):
    if n == 0:
        return 0
    elif n == 1:
        return 1

    try:
        return memo[n]        
    except KeyError:
        resultado = fibonacci_dinamico(n - 1, memo) + fibonacci_dinamico(n - 2, memo)
        memo[n] = resultado
        return resultado

def main():
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un n煤mero: '))

    tiempo_ini = time.time()
    # resultado = fibonacci_recursivo(n)
    resultado = fibonacci_dinamico(n)
    tiempo_fin =  time.time()
    print(f'El resultado es {resultado} y el tiempo para calcularso fue de {tiempo_fin - tiempo_ini}')

if __name__ == "__main__":
    main()
sys.setrecursionlimit(100002)
sys.set_int_max_str_digits(1000000)

aumentando l铆mites xd el n煤mero m谩s grande que prob茅 fue 50000

al reto de fibonacci recursivo de 50.
a mi se me demoro 31min appx en calcular el resultado. Con ese tiempo, no quiero probar los 500.

Cuando introdujeron Fibonacci dentro de este learning path busque videos para ayudarme a comprender m谩s el tema de recursividad, de todos ellos este fue el m谩s util que encontr茅:
Me sorprendi贸 ver como de diferentes maneras podemos resolver un problema, incluso si implementamos las mismas ideas (no se si me explico xD)

Tal vez estoy mal pero en todos los sitios donde investigo, el Fibonacci de 5 da 5. Con el codigo que creamos en esta clase da 8. 驴Cu谩l es el real?

Dej茅 10min computando el fibonacci de 50 con la funci贸n recursiva, y ni as铆 lo termin贸 de calcular.

Dur贸 un instante con memorizaci贸n. Aqu铆 les dejo el n煤mero:
20,365,011,074

A manera de recomendaci贸n en estos ejercicios que son tan abstractos, deber铆an apoyarse en recursos visuales para que el que tome el curso comprenda de manera la implementaci贸n de estos algoritmos, saludos

Una t茅cnica de optimizaci贸n combinatorica permite encontrar una formula no recursiva para Fibonacci y otras funciones recursivas como los n煤meros de Catalan. Esta t茅cnica se llama funciones generatrices, en este pdf se explica en detalle como usar esta t茅cnica. Las secciones 1, 2 y 3 son introductorias, en la secci贸n 4 se explica la t茅cnica, en la secci贸n 5 hay otro ejemplo de esta t茅cnica, en el ap茅ndice de la secci贸n 9 se explica como se hacen los calculos mas complicados. (https://www.miguelmath.com/Combinatorics-spring-2018.pdf)

Una forma de escribir rapido el:
if __name__=='__main__':
Es escribiendo main en VS y presionando enter, a mi me ahorra 2 o 3 segundos de vida 馃榿

Consejo antes de ver este v铆deo: averiguen qu茅 es la sucesi贸n de Fibonacci 驴Para qu茅? Para saber qu茅 es lo qu茅 van a hacer y para qu茅 sirve.
Para dejarlo m谩s claro pongo un v铆deo aqu铆 de la sucesi贸n de Fibonacci: https://www.youtube.com/watch?v=yDyMSliKsxI

La serie Fibonacci
Si tienen dudas sobre la serie de n煤meros de Fibonacci, se construye de la siguiente manera:

  • Si ustedes hacen la serie les da:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34鈥

  • El sub铆ndice en realidad es muy importante, pues representa la posici贸n del n煤mero que quieres hallar.

  • Por ejemplo para el sub铆ndice n = 50, el n煤mero de Fibonacci F50 es un n煤mero muy grande porque es una serie que crece muy r谩pido. Entonces, si la serie comienza con:
    n = 0, F0 = 0, F50 = 12586269025. Que es como est谩 implementado en la funci贸n de la imagen.

  • Si la serie comienza con n = 0, F0 = 1, salt谩ndose el 0, entonces:
    F50 = 20365011074, como le da a al profe David.

La memorizaci贸n convierte el algoritmo de fibonacci de exponencial O(2**n) a lineal O(n). Es bell铆simo, les dejo una gr谩fica que hice con bokeh y el c贸digo. https://github.com/Angrub/dinamic_fibonacci/blob/main/README.md
x = n煤mero de fibonacci
y = n煤mero de pasos

woooooow hace un tiempo implemente esta misma optimizacion para trabjar con un datasets, de 20s en hacer un cambio pase a 0.6s

Muy interesante el ejemplo

Yo al principio no entendia como funcionaba memo, literal parecia magia pura, pero dibuje los frames en un papel y FUA, entendi todo a la perfeccion jajajaj

#Si hay un numero en la posicion n, devolvemos ese valor y corta la recursividad, esto nos ahorra muchisimo tiempo, porque cuando entra al segundo fibonacci, literalmente solo toma memo[n] y listo
#El que penso en esto es un crack

Hola otro forma de usar la programaci贸n din谩mica es para optimizar la forma de encontrar n煤meros primos.
Los invito a ver el tutorial que cre茅 si quieren saber mas al respecto -> https://platzi.com/tutoriales/1835-programacion-estocastica/5328-usar-programacion-dinamica-para-buscar-numeros-primos/
saludos!

Cuando empezaba a estudiar python, uno de los ejercicios era generar la secuencia de Fibonacci. No me di cuenta que hicimos un algoritmo eficiente usando s贸lo bucles.

print('Secuencia de Fibonacci \n\n')
limite = int(input('Escribe el elemento de la serie: '))
Fib = [1,1]
if limite > 1:
	for i in range(2, limite+1, 1):
		Fib.append(Fib[i-2] + Fib[i-1])
print(Fib[limite])

funciona igual de r谩pido 馃槃

La diferencia entre ttiempos es brutal!!!

Esto me funciono rebien, no pude desifrar un error que me dio en el codigo de profe Aroesti.

Super, lo de la memoization es muy heavy 馃く

entonces creo que entendi bien鈥 lo que hacemos en este caso es guardar los numeros en un diccionario(鈥榤emo鈥) para que cuando los ocupemos el calculo sea mas rapido? :0

Desarroll茅 este c贸digo de fibonacci hace tiempo y es m谩s eficiente ahora que lo comparo con el c贸digo del profe, pero, por qu茅?

def run():
    contador = int(input("cuantos n煤meros fibonacci quieres?: "))
    i = 0
    a , b = 0, 1
    while i < contador:
        a = a + b
        b = a - b
        i += 1
        print(f'({i})', a)

if __name__=='__main__':
    run()

prueben con cualquier n煤mero, 5k, 10k, 100k, no tarda nada(claro, tarda solo el print)

rats鈥

Este enlace muestra un simulacion de como funciona la pila stack en los algoritmos de Fibonacci Recursivo, Memoizado y de tabla que al parecer es mas optimo que los demas

https://www.cs.usfca.edu/~galles/visualization/DPFib.html

si hay muchos numeros casi imposible de leer pueden usar notacion cientifica

from decimal import Decimal 
'%.2E' % Decimal(resultado) ```
ejemplo 
Fib de 900 
8.88e+187
#crear diccionario    
memo={}
#definir funcion fibo
def fibo_dina_1(n):
    #si n ingresado esta en el diccionario, devuelve el valor grabado, 
    #caso contrario calculalo
    if n in memo:
        #aqui encuentra el valor grabado
        return memo[n]
    if n==0 or n==1:
        value=1
    else:
        #aqui lo calcula
        value=fibo_dina_1(n-1)+fibo_dina_1(n-2)
    #grabar el valor calculado en el diccionario con indice n
    memo[n]=value 
    #la funcion retorna el valor grababo en el diccionario con indice n
    return memo[n]
Super clase 馃挭

Yo utilizar铆a programaci贸n din谩mica para filtrar b煤squedas en el front end. As铆 solo tendr铆a que hacer una llamada al back-end para filtrar y en caso de que el usuario repita una b煤squeda, se muestra de inmediato.

Les comparto el mismo m茅todo pero con factorial. Es un c贸digo muy sencillo y evita que explote tu computadora al intentar calcular n煤meros grandes.

import sys

def factorial(n, memo = {}):
    """Calcula el factorial de n.
    n int > 0

    returns n!
    """

    if n == 1:
        return 1
    try:
        return memo[n]
    except KeyError: 
        resultado = n * factorial(n - 1, memo)    
    return resultado

if __name__ == '__main__':

    sys.setrecursionlimit(10002)

    n = int(input("escribe un entero:  "))

    resultado = factorial(n)

    print(f'Su resultado es: {resultado}')

Hay un error fibonacci de 0 es 0 no 1 creo que hubo una confusi贸n con factorial 0! = 1
El programa da los n煤meros de fibonacci pero recorridos un lugar

Corrijanme se me equivoco 鈥
La sucesi贸n de Fibonacci inicia con 0, es decir 鈥
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 鈥

A mi me crasheo Python con F(5000) y f(10000) D:

me sucede algo extra帽o鈥
al ampliar el l铆mite de recursividad, solo me deja calcular hasta 2286, de ah铆 en adelante no muestra el resultado, termina la funci贸n sin imprimir ning煤n valor.
Alguna idea por qu茅?

Hola amigos, encontr茅 una tercera forma de hacerlo. En realidad es igual que con el m茅todo din谩mico que nos ense帽贸 el profesor, pero en lugar de crear un diccionario, usamos el decorador de python @lru_cache de la librer铆a functools. Les dejo mi c贸digo con las 3 implementaciones:

"""
Fibonacci sequence:
1,1,2,3,5,8,13,21,34,...

n : 1 --> 1
n : 2 --> 1
n : 3 --> 2
n : 4 --> 3
n : 5 --> 5
n : 6 --> 8
...

- El siquiente numero de la secuencia de fibonacci es la suma de los dos terminos anteriores.
- A veces se suele incluir el 0. Eso depende de una decision personal la mayoria de los casos.
"""
from functools import lru_cache

# Funcion recursiva que obtiene el n-esimo termino de la secuencia Fibonacci
# Muy ineficiente
def fibonacci_recursivo(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacci_dinamico(n-1) + fibonacci_dinamico(n-2)

# Funcion de Fibonacci din谩mica que obtiene el n-茅simo termino de la secuencia
def fibonacci_dinamico(n, memo = {}):
    if n==1 or n==2:
        return 1
    else:
        try:
            return memo[n]
        except KeyError:
            resultado = fibonacci_dinamico(n-1, memo) + fibonacci_dinamico(n-2, memo)
            memo[n] = resultado

            return resultado

# Una alternativa a la funci贸n fibonacci_dinamico. Obtiene el n-茅simo termino de la secuencia
# En esta funci贸n nos auxiliamos de la libreria de python. El resultado se obtiene de manera tan eficiente que con fibonacci_dinamico.
# Mas informaci贸n: https://docs.python.org/3/library/functools.html
@lru_cache(maxsize = 1000)
def fibonacci_dinamico2(n, memo={}):
    if n == 1 or n == 2:
        return 1
    return fibonacci_dinamico(n-1) + fibonacci_dinamico(n-2)

# Funcion principal
def main():
    n = int(input("Escoge un numero: "))
    resultado = fibonacci_dinamico2(n)
    print(resultado)

if __name__ == "__main__":
    main()

Como ven, la funci贸n fibonacci_dinamico2 es igual a la funci贸n fibonacci_recursivo solo que antes le agregamos el decorador lru_cache.

Esta forma es con un loop pero sin guardar en memoria

def fibonacci_iterativo(n):
    resultado_anterior, resultado_actual= 0, 1

    for i in range(n):
        resultado_anterior, resultado_actual = resultado_actual, resultado_actual + resultado_anterior

    return resultado_actual

Un poco m谩s comprendido al tema del trade of: tiempo vs espacio

antes de iniciar la clase hice este peque帽o codigo para calcular la secuencia que desee ver el usuario:

def Fibonacci(i_objetivo):
lista=[1,1]
for i in range(i_objetivo+1):
if i <=2:
Resultado=1
else:
Resultado=lista[0]+lista[1]
lista[0]=lista[1]
lista[1]=Resultado
#print(lista)
print(Resultado)
if name == 鈥main鈥:
i_objetivo = int(input('cual item desearia saber: '))

Fibonacci(i_objetivo)

Corregidme si me equivoco, pero creo que hay un error en el algoritmo de David:

if  n==0  or  n==1:
    return 1

es err贸nea. Fibonacci de 0 es 0, pero seg煤n el c贸digo de arriba devuelve 1. Deber铆a ser:

if  n==0:
	return 0
if  n==1:
	return 1

Me pareci贸 m谩s f谩cil como lo explica aqu铆, incluso hasta como ordena el c贸digo:

https://www.youtube.com/watch?v=Qk0zUZW-U_M

Programaci贸n din谩mica
Poco tiene que ver con su nombre, es solo una t茅cnica para optimizar ciertos tipos de problemas. Especificamente los problemas que tienen:

1. Subestructura 贸ptima: cuando una soluci贸n 贸ptima global se puede encontrar al combinar soluciones 贸ptimas de subproblemas locales. Es decir, encontrar las soluciones 贸ptimas de problemas m谩s peque帽os.
Ejemplos: Fibonacci, Problema del morral, Merge sort.

2. Problemas empalmados: Soluciones 贸ptimas que involucra resolver el mismo problema varias veces (recursividad).
Ejemplo: Fibonacci, Problema del morral.

Aclaraci贸n: en Merge sort, cada vez que se divide la lista, se tiene un nuevo problema. Por lo tanto, no aplica la PG en este caso.

**La forma de optimizar: Memoization **
Evita c贸mputos adicionales guardando el resultado de c谩lculos previos dentro de un diccionario (o estructura de datos), que tienen complejidad O(1). Al guardar los resultados en memoria, se ahorra tiempo de c贸mputo. As铆, se intercambia tiempo por espacio.

馃槂

**Por que usar listas y no diccionarios? (error com煤n al hacer programaci贸n din谩mica)** En programaci贸n din谩mica, el diccionario (*hashmap*) se usa solamente cuando el valor del estado (par谩metro a memoizar) tiene una distribuci贸n dispersa (es decir hay valores inexistentes entre valores). Para distribuciones no dispersas como es este caso, es mas eficiente usar listas, ya que estas tienen un acceso a cada valor memoizado de O(1) (usando el indice en la lista), mientras que el *hashmap* tiene un tiempo O(1) pero solamente *en el caso promedio* (la lista es siempre O(1) en el peor caso). Ademas el hashmap es una estructura de datos mas ineficiente en otros aspectos (requiere mas memoria, maneja memoria en heap, y requiere re-hashing en ciertas ocasiones). (Nota) Complemento: Data dispersa es por ejemplo: 4, 9, 10000, 1000000 (los valores 100, 101, 2000, etc no est谩n presentes). Para memoizar estos valores usando el indice en la lista requerir铆amos tener una lista enorme, pero solo ciertos valores estar铆an ocupados, por lo que un hashmap es mejor. Data no dispersa es cuando todos los valores consecutivos est谩n presentes: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, etc. Aqu铆 no tiene sentido usar hashmap para separar los valores, una lista es mas eficiente.

Una ilustraci贸n grafica de la optimizaci贸n din谩mica de fibonacci.

Un peque帽o error, aunque no afecta el tema a tratar, es que en la serie de Fibonacci si el numero es igual a 0 se retorna 0 no 1, y si es 1 si se retorna 1.

Primer clase del curso donde hay c贸digo, y la verdad qued茅 impresionado de como al cambiar un concepto, se pasa de inutilizar la m谩quina a darle un uso apropiado.
Excelente clase de introducci贸n a la programaci贸n din谩mica!

miren amigos, yo lo hice con javascript y aqui lo dejo por si les sirve

function fibonacci_dinamic(n, memo = {}) {
  if (n == 0 || n == 1) {
    return 1;
  }
  if (memo[n]) {
    return memo[n];
  }
  var resultado =
    fibonacci_dinamic(n - 1, memo) + fibonacci_dinamic(n - 2, memo);
  memo[n] = resultado;
  console.log(memo);
  return resultado;
}

const resultado = fibonacci_dinamic(50);
console.log(resultado);

que locura鈥 馃槂

Hola a todos 馃憢馃従!
Utilizando python tutor, hice la prueba de hallar el n煤mero de Fibonacci tres veces en una misma ejecuci贸n para ver c贸mo funcionaba el diccionario en cada llamada de la funci贸n y el resultado fue el siguiente (馃く):

.
La primera entrada fue 10:
.

.
La segunda entrada fue 15:
.

.
La tercera entrada fue 5:
.

.
Si quieres probarlo por ti mismo 馃憠馃従aqu铆 lo puedes hacer 馃憟馃従

en principio lo hice sin el if name
y por alguna r谩zon que no me explico es mas lento asi.
aunque funciona
una vez lo pongo con ese iniciador, funciona de inmediato


馃槂 Intent茅 encontrar el fibonacci de 40 con el metodo recursivo y demoro 69 segundo

a m铆 me sigui贸 respondiendo hasta el 999

Como consejo, en general nunca deber铆an utilizar recursi贸n en la programaci贸n.
Una forma de implementar lo mismo sin el problema del l铆mite de recursi贸n (y algo as铆 como 100 veces m谩s r谩pido) ser铆a un simple for loop

def fib(n):

    a, b = 1, 1

    for i in range(n):
        a, b = b, a+b
    
    return a

El Fibonacci de 50 es 20365011074

En mi pc el l铆mite es 2131 de la serie de Fibonacci. No se puede ir m谩s all谩 alargando el SYS porque literalmente parece que el micro no llega.
No s茅 si es problema de python o de mi compu pero siguiendo estos pasos de la clase me top茅 con este l铆mite.
Tengo que a帽adir que a partir de n煤meros muy grandes Python ya no me devuelve ning煤n error, s贸lo pasa y ya.

Si est谩s leyendo esto seguro que puedes explicar el comportamiento de mi compu.
Responde este comentario y me cuentas porque estoy perdid铆sima

驴Qu茅 es el entry point en python?

鈥淓n conclusi贸n, nuestro entry point le ayuda al interprete de python internamente a identificar de que manera se debe ejecutar el o los m贸dulos y/o scripts de python que le estamos pasando.鈥

https://n9.cl/knz4w9

Yo hice una busqueda en Stack Overflow de alg煤n c贸digo de fibonacci y encontr茅 uno que me sirvi贸 de base para crear esta soluci贸n que me parece mas intuitiva y no consume tanta memoria.
Igual no se si es una soluci贸n valida, as铆 que acepto sugerencias.

import time


def fibonacci(n):
    fibonacci_numbers = [0, 1]
    for i in range(n-1):
        fibonacci_numbers.append(fibonacci_numbers[0]+fibonacci_numbers[1])
 
        del fibonacci_numbers[0]

    return fibonacci_numbers[1]


if __name__ == '__main__':
    n = int(input('Elige un numero: '))
    #n = 4000000

    start = time.time()
    print(fibonacci(n))
    end = time.time()


    number = end-start

    print(f'Fibonacci de {n}')
    print(f'Tiempo de ejecucion: {number}')
    print(f'Tiempo en minutos: {number/60}')
    print('---'*50)

Fibonacci de 4 000 000
Tiempo de ejecucion: 598.9549551010132
Tiempo en minutos: 9.982582585016887

No pongo el resultado por que es muy muy grande

Este algoritmo funciona bien y no da problemas de recursividad.

def fibonacci_dinamico_2(number):
    memo_dict = {0: 0, 1: 1}
    for i in range(number + 1):
        if i >= 2:
            resp = memo_dict[i - 1] + memo_dict[i - 2]
            memo_dict[i] = resp

    return memo_dict[number]

es un poco mas facil de entender si se imprimer el diccionario.

Para parar la ejecuci贸n de un programa desde la consola basta con poner 鈥楥trl+c鈥

馃槃

Para entender mejor el tema, fibonacci y memorizaci贸n, tuve que leer este medium: https://medium.com/@porzingod/fibonacci-and-memoization-e99f765b97f6

Me costo un poco entenderlo, pero me ayudo verlo asi:

  1. Crear un diccionario
  2. return 1 para los primeros dos elementos de la secuencia
  3. Revisar si ya tenemos guardado el numero n de la secuencia en el diccionario
  4. Si esta, return el valor. Si no esta evaluar el n煤mero de la secuencia

.
Siempre revisamos si ya tenemos el valor n de la secuencia guardado en el diccionario.
Si no est谩, lo evaluamos.


y este comentario me salvo la vida

Hola creo que hay una forma mas eficiente. Llego a 400mil de fibonacci en menos de 2 segundos.
Con el fibonacci_dinamico(n) del curso se rompe todo mucho antes.

def fibonacci_faster(n):
    if n == 1 or n == 0:
        return 1
    primero = 0
    segundo = 1
    
    for i in range(n):
        resultado = primero + segundo
        primero = segundo
        segundo = resultado

    return resultado

Me puse rebelde y no quise usar la recursividad, 馃槄 y que creen,
logre llegar a la complejidad **O(n) ** A mi parecer lo hice bien鈥 pero me gustar铆a leer tu recomendaci贸n.

def fibonacii_by_loop(n):
    #[{fibonacii:_2},{fibonacii:_1}, {fibonacii : _1 + _2 }]
    _1 = 1
    _2 = 0
    fibonacii = _1 + _2
    for i in range(1, n):
        _2 = _1
        _1 = fibonacii
        fibonacii = _1 + _2
    return fibonacii


def run():
    n = int(input('Escribe un n煤mero: '))
    print(fibonacii_by_loop(n))


if __name__ == '__main__':
    run()

pdsta: Si llegaste hasta aqu铆 es por que eres grandioso o un curioso grandioso, jaja pero de todos modos eres grandioso!

Se puede profundizar este contenido a nivel de programacion con esta genial clase:
https://platzi.com/clases/2397-python-profesional/39532-la-sucesion-de-fibonacci/

En ingenier铆a de software analizar la complejidad algor铆tmica es primordial, por tanto, es importante entender un poco m谩s que tipo de complejidad tiene nuestro algoritmo, les dejo este video, que explica a grandes rasgos como medirla: https://www.youtube.com/watch?v=IZgOEC0NIbw

Fuente Imagen: https://rootear.com/desarrollo/complejidades-algoritmos

<import sys

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

def fibonacci_dinamico(n, memo = {}):
    if n == 0 or n == 1:
        return 1
    try:
        return memo[n]
    except KeyError:
        resultado = fibonacci_dinamico( n - 1, memo) + fibonacci_dinamico(n - 2 , memo)
        memo[n] = resultado
        return resultado


if __name__ == '__main__':
    #cambiar limite de recursividad mediante la libreria sys
    sys.setrecursionlimit(10002)
    n = int(input('Escoge un n煤mero: '))
    resultado = fibonacci_dinamico(n)
    print(resultado)> 

import sys, sys.setrecursionlimit(10000) para aumentar el nivel de recursividad.

Para hacer memoization, solo necesitamos especificar cu谩ndo se guarda el resultado, para luego acceder a 茅l.

Fibonacci de 35 para arriba, empieza a ser lento.

memoization, es la forma en c贸mo aplicamos la programaci贸n din谩mica.

Los n煤meros Fibonacci, pueden tomar muchos caminos.

Fibonancci, de por si solo, es bastante ineficiente.

Este v铆deo es muy bueno para complementar!
https://www.youtube.com/watch?v=M3LkQiWVBoc

Es divertido utilizar recursividad para aprender, solo hay que tener cuidado de no usarlo en el trabajo, no es bien visto por la complejidad algoritmica que implica