La programación dinámica es una metodología de optimización que ahorra tiempo al intercambiar espacio. Utiliza la memorización para evitar cálculos repetidos al guardar los resultados de subproblemas que se pueden reutilizar. Esto es esencial en problemas donde hay muchas subestructuras comunes, como es el caso de la secuencia de Fibonacci.
¿Cómo se implementa la secuencia de Fibonacci de forma recursiva?
A pesar de ser sencilla de implementar, la solución recursiva a la secuencia de Fibonacci es ineficiente debido al cálculo repetido de los mismos subproblemas. El algoritmo recursivo es el siguiente:
deffibonacci_recursivo(n):if n ==0or n ==1:return1else:return fibonacci_recursivo(n-1)+ fibonacci_recursivo(n-2)
En este enfoque, calcular el Fibonacci de un número grande, como 50, puede ser extremadamente lento. Esto se debe al número exponencial de subproblemas solapados que requieren cálculo.
¿Cómo optimizar la secuencia de Fibonacci usando memorización?
Para optimizar el algoritmo, introducimos la técnica de memorización con un diccionario que almacena los resultados ya calculados:
deffibonacci_dinamico(n, memo ={}):if n ==0or n ==1:return1if n in memo:return memo[n] memo[n]= fibonacci_dinamico(n-1, memo)+ fibonacci_dinamico(n-2, memo)return memo[n]
Esta solución es significativamente más rápida, porque una vez que un valor de Fibonacci está calculado, no se recalcula.
¿Cómo empezar a usar la función optimizada?
Podemos probar este enfoque en nuestra terminal después de implementar el código:
if __name__ =='__main__': n =int(input("Escoge un número: "))print(f"Fibonacci de {n} es {fibonacci_dinamico(n)}")
Al correr este script, se podrá calcular rápidamente Fibonacci para números tan grandes como 10,000, siempre que se ajuste la recursión máxima de Python, como se muestra a continuación:
import sys
sys.setrecursionlimit(10002)
Esto asegura que nuestra función pueda manejar la profundidad de llamada necesaria para valores grandes.
Reflexiones sobre el uso de programación dinámica
La programación dinámica es increíblemente poderosa para problemas donde hay solapamiento de subproblemas. Sin embargo, su aplicación debe ser cuidadosa, ya que en problemas sin solapamiento este enfoque no resultaría en optimización alguna; solamente se crearían diccionarios infinitamente grandes sin beneficios perceptibles.
¡Exploren, experimenten y compartan sus hallazgos en cómo la programación dinámica puede aplicarse a otros problemas! Vuestros aportes pueden enriquecer la comunidad de aprendizaje.
Tengan cuidado con fibonaccis muy grandes, podrían encontrarse con este pokemon legendario
Gracias profe facundo
Facundo tu deberías por favor dar estas clases
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(R) Core(TM) i7-8850H CPU @ 2.60GHz)
Memoria Ram 32gb
Hola @Jvaldes, podrías ensayar el mismo proceso en un Xeon, de 8 nucleos y 16 hilos, el resultado sería muy similar, si no es que el mismo, debido a que este tipo de ejecuciones se corren sobre un único núcleo de procesamiento, por lo que el resultado será muy similar al margen de la velocidad, o la cantidad de núcleos; asumo que en próximos cursos de la ruta se enseñará sobre clusterización.
Saludos.
Hola , hice por curiosidad la prueba en un lenguaje diferente, uno compilado y la diferencia es enorme, solo tomo 2 minutos y 24 segundos (144 segundos) llegar al resultado por fibbonacci_recursivo
Para entender mejor escribí
memo[n]= resultado
print(memo)
Y como resultado
: def func_wrapper(*kwargs): _hash = hashlib.md5((func.__name__+str(kwargs)).encode()).hexdigest()if _hash indata_memo:return data_memo[_hash] _result =func(*kwargs) data_memo[_hash]= _result
return _result
return func_wrapper
@memoization
def fibonacci_recursive_memo(n):return1if n ==0 or n ==1elsefibonacci_recursive_memo(n-1)+fibonacci_recursive_memo(n-2)def fibonacci_recursive(n):return1if n ==0 or n ==1elsefibonacci_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}")
Me encantó tu comentario. De hecho, la forma en la que se hace en el mundo profesional es similar a tu implementación. Por cuestiones didácticas utilicé el diccionario, pero si estuvieramos escribiendo código de producción utilizaríamos el decorador lru_cache de la librería functools. Aquí está la documentación: https://docs.python.org/3/library/functools.html#functools.lru_cache
Si si muy facha tu codigo.
Dejo un link para complementar este comentario -> Link
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 =0if n ==0: step +=1print(f'.........Caso base - Fibo({n}) = {0}')return0 elif n ==1: step +=1print(f'.........Caso base - Fibo({n}) = {0}')return1try: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}')
Para que usas step y lo incrementas cuando n==0 y n==1, sin realmente esa variable no la usas?
Muchas gracias, aunque habian ciertas cosas que lo hacian difícil de leer o bien estaban de más, toma esta versión corregida:
def fibo_dinamico(n, memo={}):if n <=0 or n ==1:return1try:print(f'..Consultando en dic_memo Fibo({n})')print()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}')
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 exponencialO(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.deffibonacci_recursivo(n):if n ==0or n ==1:return1return 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.deffibonacci_dinamico(n, memo ={}):if n ==0or n ==1:return1# 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)
Muchas gracias, capo
++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 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.
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.
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.
Esto no lo sabía :o
Gracias por el aporte :D
Efectivamente, en mi preparación de algoritmia nos dijeron que la clave de la programacion dinamica era encontrar los modelos matematicos que seguian nuestros datos, y así era más fácil resolver problemas de programacion dinamica
Golden Ratio™ ? es un trade mark? -> chan! , en cualquier momento inventan la rueda y el ponen un "tm" tambien jaja
Muy bueno el articulo
Alguien entendio bien como funciona el algoritmo fibonacci_memorizacion que me ayude a entemderlo
A diferencia de fibonacci recursivo este algoritmo guarda los valores que ya calculo por ejemplo si quiero calcular el fibonacci de 6 llamara a fibonacci de 5 y fibonacci de 4, cuando deba calcular el fibonacci de 5 ya no volverá a calcular el fibonacci de 4 y el de 3 si no que directamente ya tomara estos valores que los guardo cuando calculo el fibonacci de 4 y de 3
def fibonacci_dinamico(n,memo ={}): #recibe el numero del cual quiero fibonacci y el diccionario vació en el cual voy a guardar mis resultados previos
if n ==0 or n ==1:return1try: # pido que intente encontrar el valor en el diccionario
return memo[n] except KeyError: #si no encuentre el valor me dará un error le digo que maneje el error
resultado =fibonacci_dinamico(n -1, memo)+fibonacci_dinamico(n -2, memo) # así manejo el error Mandando le a buscar como de manera recursiva a calcular el fibonacci de manera re cursiva pasando le también el diccionario q se va creando
memo[n]= resultado #aquí vuelvo guardo mi valor que calculo en el diccionario para volverlo a buscar en caso de que lo necesite después
return resultado # regreso el valor del fibonacci que no existia pero q ya lo calcule con los cómputos previos que había guardado
if __name__ =='__main__': sys.setrecursionlimit(10002) # El limite máximo de recursiones lo defino ahora como 10002 n =int(input('Escoge un numero: ')) resultado =fibonacci_dinamico(n)print(resultado)
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):return1returnfibonacciRecursivo(numero -1)+fibonacciRecursivo(numero -2)#FunciónFibonacci 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):return1 #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 tryexcept: #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)}')
Jose Zuñiga esta bien documentado, facil de entender, Muchas gracias.
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 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 2318:40 fr20.txt-rw-rw-r--1 julio julio 70034644 jun 2318:42 fr30.txt-rw-rw-r--1 julio julio 8613691911 jun 2318:49 fr40.txt-rw-rw-r--1 julio julio 3 jun 2318:40 numero20
-rw-rw-r--1 julio julio 3 jun 2318:42 numero30
-rw-rw-r--1 julio julio 3 jun 2318:43 numero40
-rw-rw-r--1 julio julio 0 jun 2319:15 prueba.txt
¿Es una buena practica el dar una solucion modificando el limite de recursividad de python?, lo pregunto dado a que en la documentacion no recomiendan subir estos cambios a entornos de produccion, en ese orden de ideas, ¿que otra enfoque se le pueden dar a soluciones recursivas que no nos haga enfrentar con esta "limitaciones" de python?
Cualquier algoritmo recursivo puede ser implementado de forma iterativa. Por otra parte puedes modificar esos limites, pero ten cuidado de no consumir todos los recursos de la maquina.
No hay una respuesta que sirva para todos los casos, no es cuestión de hacer todo de forma iterativa o recursiva. Conviene analizar cada caso he intentar aplicar la mejor solución.
El límite está puesto justo por eso. Para que no hayan problemas con funciones recursivas.
Pero como en el ejemplo de la clase. Si se conoce de antemano la función recursiva se puede editar ese límite. Solo hay que tener cuidado al hacerlo. Teniendo seguridad que no va a dar errores a futuro y esto último puede ser al realizar pruebas previas.
no puedo calcular fibonacci de 5000 ya logre calcular el de 2000 pero mi función simplemente no me devuelve nada.?
Escoge un numero: 2000
6835702259575806647045396549170580107055408029365524565407553367798082454408054014954534318953113802726603726769523447478238192192714526677939943338306101405105414819705664090901813637296453767095528104868264704914433529355579148731044685634135487735897954629842516947101494253575869699893400976539545740214819819151952085089538422954565146720383752121972115725761141759114990448978941370030912401573418221496592822626
PS C:\Users\HPUser\Documents\Python> 5000
5000
PS C:\Users\HPUser\Documents\Python>
sin el codigo, no se puede hacer nada, por favor agregalo
También en mi caso utilice import sys para 10000... pero aún así sólo dió respuesta el programa hasta el 2255. Creo que no se está importando bien la librería.
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.
