en Curso Python, Programación, Python

Técnicas de programación: Patrón memoize

Patrón Memoize

Hola a todos, bienvenidos a una nueva entrada de este blog, y en esta ocasión vengo a escribir sobre un tema que a muchos les será de utilidad. Conoceremos qué es el patrón memoize o de memorización con ayuda de nuestro buen amigo, el lenguaje Python en su versión 3.6.0.

¿Qué es el patrón memoize o de memorización?

El patrón memoize consiste en almacenar las soluciones calculadas previamente, para evitar que sean recalculadas, logrando con esto, reducir el tiempo computacional de nuestros algoritmos.

Este patrón es empleado en diversas técnicas de programación, entre ellas, la programación dinámica, ¿sencillo, no lo creen?

Creo que un ejemplo permitirá que esto quede más claro. Para ilustrar esto, escribiremos un decorador que siga este patrón, por lo tanto, almacenará las soluciones en un diccionario para ser reutilizadas al ser requeridas nuevamente.


#!/usr/bin/env python
# -*- coding: utf-8 -*-


def memoize(f):
memory = {}

def wrapper(n):
if n not in memory:
memory[n] = f(n)
return memory[n]
return wrapper

 

Como podemos observar, el código no debería resultar demasiado complejo. Es la definición de una función decorator. Si miramos detenidamente el código, observamos que la función memoize recibe un argumento f, que se trata de la función que será “decorada”.

Paso siguiente, se define un diccionario, el cual almacenará los valores que se vayan calculando en la función. Tenemos nuestra función de envoltura (wrapper), la cual recibe un argumento n, que se trata del valor que está siendo calculado.

Dentro de nuestra función de envoltura, se verifica que el elemento no se encuentra en nuestro diccionario, si la condición se cumple entonces lo añade al mismo, de lo contrario, simplemente retorna el elemento desde el diccionario. Y por último, devuelve la función de envoltura.

Poniendo en práctica nuestra función memoize

Un problema que aprovecha enormemente este patrón, es el conocido problema de encontrar el n-ésimo número de la sucesión de Fibonacci. Así que, primero vamos a crear nuestra función para lograr tal objetivo.


def fibonacci(n):
if n < 2:
return n
return fibonacci(n - 1) + fibonacci(n - 2)

 

Como podemos apreciar, estamos utilizando la versión recursiva de la función para realizar la operación. Con esto, podemos apreciar de mejor forma las ventajas del patrón memoize. En principio este algoritmo genera un árbol recursivo, el cual se halla plagado de subárboles que corresponden a casos resueltos en diferentes ramas, y por lo tanto, están siendo recalculados.  En la siguiente imagen podemos ver la explosión arbórea cuando n = 6.

qué es el patrón memoizePara evitar esta situación, podemos valernos de una solución de ramificación y poda, utilizando el decorador memoize que creamos previamente, evitando así cálculos innecesarios.


# Utilizando Memoize
@memoize
def fib_memoize(n):
if n < 2:
return n
return fib_memoize(n - 1) + fib_memoize(n - 2)

 

Lo sé, lo sé, seguro están pensando que no hay forma de comprobar que realmente esto funciona. Hagamos algo, modifiquemos un poco el código del decorador para que indique cuando una solución ha sido calculada previamente, con esto podremos apreciar que la memorización se está llevando a cabo.


# Decorador mejorado, para visualización
def memoize_debug(f):
memory = {}

def wrapper(n):
if n not in memory:
memory[n] = f(n)
else:
print("Result was previously calculated: {0}".format(n))
return memory[n]
return wrapper

 

De igual forma, vamos a modificar nuestra función fib_memoize para que utilice nuestro nuevo decorador.


@memoize_debug
def fib_memoize(n):
if n < 2:
return n
return fib_memoize(n - 1) + fib_memoize(n - 2)

 

Si realizamos la prueba de nuestra función, el resultado para n=6 será.

In[1]: fib_memoize(6)

Result was previously calculated: 1
Result was previously calculated: 2
Result was previously calculated: 3
Result was previously calculated: 4

Out[1]: 8

Les dejo el código en el repositorio en Github.

Por esta ocasión es todo, espero los conceptos hayan quedado claros, de lo contrario, no duden en escribir sus dudas en los comentarios. No olviden seguirme en mis redes, ya sea twitter, o en la fanpage en Facebook. Y bien, hasta la próxima entrada.

Deja un comentario