Python y la programación dinámica
Tags: spanish, python, dynamic, algorithms
Published: 2024-03-11 11:11:29

---
title: Python y la programación dinámica
published: true
description: Recordando los valores calculados previamente
tags: #spanish #python #dynamic #algorithms
---

Todos conocemos la función *fibonacci(n: int) -> list[int]*, es probablemente la pesadilla de muchos estudiantes del grado en informática. Se trata de devolver una lista con los elementos de la sucesión de *Fibonacci* hasta *n*, el parámetro. Recordemos que la sucesión de *Fibonacci* se define por calcular cada elemento como la suma de los dos anteriores, siendo el comienzo siempre [0, 1], es decir, *fibo(0) == [0]* y *fibo(1) == [0, 1]*.

Podemos hacerlo tal que así:

```python
def calc_fibo(self, n: int) -> list[int]:
	toret = []

        if n == 0:
	    toret = [0]
        elif n == 1:
            toret = [0, 1]
        elif n >= 2:
            toret = calc_fibo(n - 1) + [calc_fibo(n - 1)[-1] + calc_fibo(n - 1)[-2]]
        ...

	return toret
...
```

Se trata de la versión más obvia de la función de *Fibonacci*, y también la menos eficiente. Al hacer tres llamadas recursivas, nos encontramos con que con valores no demasiado altos de *n*, como 15, el tiempo de ejecución comienza a resentirse, siendo insufrible con *n == 20*.

```python
from time import time


fibo = Fibo()
t1 = time()
print(calc_fibo(17))
t2 = time()
print(f"Tiempo: {t2 - t1: 5.2f} segundos.")    # Tiempo:  14.00 segundos.
```

Ya sabemos que es posible crear versiones más eficientes de la función *calc_fibo(n)*, pero... Supongamos por un momento que no podemos hacerlo. Supongamos que necesitamos mantener esa función como está, pero que necesitamos acelerar las cosas.

Una posibilidad es utilizar *programación dinámica*. Aunque parezca un término como muy técnico, en realidad se trata simplemente de recordar aquellos términos que ya hemos calculado, y utilizarlos en los siguientes cálculos. Incluso un término aún más técnico es *memoization*, pero el recurso que debemos utilizar es el que es, es decir: una caché. Y la caché más típica es un diccionario: en este caso la clave sería *n*, el parámetro pasado, y el valor la lista con la sucesión de *Fibonacci* previamente calculada.

Por ejemplo, si nos piden `calc_fibo(4)`, calcularemos que el resultado es `[0, 1, 1, 2]`, y podemos guardarlo en la caché con `cache[4] = [0, 1, 1, 2]`. Cuando a continuación nos pidan `fibo(5)`, la llamada recursiva pedirá `fibo(4)`. Como ya está en la caché, simplemente podemos devolver el valor asociado en lugar de calcularlo.

El primer paso, por tanto, es crear una caché. La caché tendrá al menos los valores de la sucesión de partida.

```python
cache = {0: [0], 1: [0, 1]}
```

Vamos a mantener la función *calc_fibo(n)* como estaba. Crearemos una nueva función que consulte y actualice la caché, y que devuelva el valor buscado o lo calcule.

```python
def fibonacci(n: int) -> list[int]:
	toret = cache.get(n)

	if not toret:
		toret = calc_fibo(n)
		cache[n] = toret

	return toret
...
```

Solo hay un problema: debemos actualizar la función *calc_fibo(n)* de forma que también llame a *fibonacci(n)* para las llamadas recursivas, de otra forma solo estaremos aprovechando parcialmente la caché.

```python
def calc_fibo(n: int) -> list[int]:
    toret = []

    if n == 0:
	toret = [0]
    elif n == 1:
	toret = [0, 1]
    elif n >= 2:
        toret = fibonacci(n - 1) + [fibonacci(n - 1)[-1] + fibonacci(n - 1)[-2]]
    ...

    return toret
...
```

Probemos el nuevo código. Soy muy optimista con su potencial, así que para qué probar con *n* igual a 25. ¡Probemos directamente con 200!

```python
t1 = time()
print(fibonacci(200))
t2 = time()
print(f"Tiempo: {t2 - t1: 5.2f} segundos.")    # Tiempo:  0.00 segundos.
```

Ahora la respuesta es... casi instantánea. Y no estamos calculando `n == 20`, ni siquiera `n == 50`, lo estamos haciendo con `n == 200`. Recordemos que previamente con `n == 17`, ¡empleaba aproximadamente 14 segundos!

Pues **Python**... sí, ya puede hacer esto automáticamente. No es necesaria la función *fibonacci(n)* que hemos desarrollado. En el módulo `functools` tenemos el decorador *cache*, si se lo aplicamos a la función *calc_fibo(n)* obtenemos el mismo resultado, sin necesidad de la función *fibonacci(n)*. Tampoco necesitamos el diccionario *cache*, claro.


```python
import functools
from time import time


@functools.cache
def calc_fibo(n: int) -> list[int]:
	toret = []

	if n == 0:
		toret = [0]
	elif n == 1:
		toret = [0, 1]
	elif n >= 2:
		toret = calc_fibo(n - 1) + [calc_fibo(n - 1)[-1] + calc_fibo(n - 1)[-2]]
	...

	return toret
...


t1 = time()
print(calc_fibo(200))
t2 = time()
print(f"Tiempo: {t2 - t1: 5.2f} segundos.")    # Tiempo:  0.00 segundos.
```

Python mola. ¿A que sí?