Python y la programación dinámica

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í:

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.

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.

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.

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é.

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!

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.

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í?