Acelerar las funciones de Python con lru_cache

En esta entrada se va a ver cómo cachear los métodos para acelerar las funciones de Python con lru_cache.

Al trabajar con funciones recursivas, como puede ser la sucesión de Fibonacci, es habitual llamar al mismo método con los mismos parámetros en repetidas ocasiones. Si el resultado del método se obtiene rápidamente esto no es un problema, pero si en el caso contrario. Una solución para este problema es cachear las funciones. Así, cuando sea necesario llamar volver a llamar a un método su resultado se puede recuperar más rápidamente. En una entrada anterior se ha visto cómo hacer esto en R con el paquete memoize, en esta se va a explicar cómo hacerlo en Python con lru_cache.

Implementación de la sucesión de Fibonacci

Para ver el tiempo que se puede ganar al cachear un método en Python se va a implementar la sucesión de Fibonacci. Esta se define con la siguiente expresión:

f(n) = f(n-1) + f(n-2)

En donde n es un número natural. Una implementación básica en Python se puede realizar mediante la siguiente función:

def fibonacci(num):
if num in [0, 1]:
return num
else:
return fibonacci(num - 1) + fibonacci(num - 2)

Ahora se puede medir el tiempo necesario para obtener el valor 50 de la serie.

from time import time

start = time()
fibonacci(35)
end = time()

fib_time = end - start

El tiempo necesario para obtener el resultado ha sido de 3,43 segundos en un Intel Core i5 a 3,1 GHz.

Implementación de la función cacheada

Para cachear la función simplemente se ha de importar el embellecedor lru_cache desde functools y utilizarlo antes de la función. Esto, junto a la medida del tiempo, es lo que se muestra en las siguientes líneas de código:

from functools import lru_cache

@lru_cache()
def fib_cache(N):
if N in [0, 1]:
return N
else:
return fib_cache(N - 1) + fib_cache(N - 2)

start = time()
fib_cache(35)
end = time()

fib_time = end - start

Ahora el tiempo necesario para ejecutar el código es solamente de 0,3 milisegundos en la misma maquina. Esto supone mejorar el rendimiento en cerca de 4 ordenes de magnitud.

Conclusiones

En esta entrada se ha visto cómo mejorar el rendimiento de las funciones Python utilizando el embellecedor lru_cache. La mejora que se puede obtener empleando esta técnica es considerable. Como se ha visto en la entrada, en el caso de las funciones recursivas se pude llegar a ganar varios ordenes de magnitud.