Memoization en Groovy

Este artículo es una traducción del documento Memoization in Groovy, escrito por Brendon Anderson en el blog de Object Partners. Deseo mostrar mi más sincero agradecimiento tanto al autor por escribir un artículo tan práctico y sencillo como a Ehren J. Seim por responder afirmativamente a mi petición para realizar la traducción del documento a español, y así difundir el conocimiento a la comunidad hispana de Groovy.

This article is a translation of the document Memoization in Groovy, written by Brendon Anderson in Object Partners's corporate blog. I wish to express my sincere thanks to the original author for write such a practical and easy-to-read article, as well as Ehren J. Seim for accept the spanish translation request and thus spread the word to the Groovy hispanic community.

Thanks a lot guys :)

¿Qué es Memoization?

Memoization (que aunque no es directamente traducible a español representa un concepto similar a memorización) es una forma de cacheo disponible en Groovy. Según su artículo original en Wikipedia (entre otros sitios) memoization es una técnica muy útil al realizar cálculos recursivos, aunque puede ser usando en cualquier situación en la que sea necesario almacenar cálculos previos basados en una entrada específica. Es importante hacer constar que memoization debe ser usado de forma distinta a como usamos un cacheo regular (en el contexto de Spring Cache, por ejemplo). Este último generalmente implica que, o los datos expirarán eventualmente, o simplemente cambiarán en el algún momento futuro, mientras que memoization está dirigido hacia cosas que siempre van a ser verdad (en otras palabras, datos que no van a cambiar). 5! (factorial de 5) va a ser siempre 120, mientras que el resultado de una llamada a un sistema remoto para obtener información de un usuario basado en un identificador (como idUsuario) podría cambiar. Groovy proporciona memoization en closures desde la versión 1.8. La capacidad de realizar memoization directamente sobre métodos ha sido añadida recientemente, más concretamente en la versión 2.2. Mirando el código fuente vemos que memoization en métodos usa la ya citada capacidad existente en closures; básicamente, la anotación @Memoized envuelve en un closure la llamada al método donde es aplicado.

Memoization en closures

En el siguiente código se muestra un ejemplo básico de memoization en closures:

def miClosure = { Integer x ->
    println "Argumento de miClosure: $x"
}.memoize()

miClosure 3
miClosure 4
miClosure 3
miClosure 4

El resultado obtenido al ejecutar el código anterior es el siguiente:

Argumento de miClosure: 3
Argumento de miClosure: 4

Como puedes ver, el código incluido en el closure se ha ejecutado una única vez por cada parámetro de entrada distinto.

Memoization en métodos

Veamos ahora como ejecutar memoization en métodos. Para ello vamos a realizar un cálculo recursivo común: el cálculo del factorial de un número (N!). Si has calculado previamente 4! a traves de un método memoization, calcular 5! solo debería implicar una única operación de multiplicación, ya que 5! == 4! * 5.

Veámoslo mediante un ejemplo:

@Memoized
static Long factorial(Long f) {
  println "Factorial de $f"
  if (f == 0 || f == 1) {
       return 1
   }
   factorial(f - 1) * f
}

Ahora ejecuta el siguiente código:

println factorial(4)
println factorial(3)
println factorial(5)

Y observa el resultado:

Factorial de 4
Factorial de 3
Factorial de 2
Factorial de 1
24
6
Factorial de 5
120

La mayor parte del trabajo ha sido realizado al calcular 4!, por lo que al calcular 3! no se ha realizado ningún cálculo extra. Adicionalmente, al calcular 5! sólo se ha realizado una operación extra (aquella de la que hablamos antes y que no habíamos calculado aún).

Calcular la sucesión de Fibonnaci es un ejemplo aún más claro de las ventajas que puede reportarnos el uso de memoization. Veamos un ejemplo de dicho cálculo sin usar memoization:

static Long fib(Long f) {
   println "Fibonacci de $f"
   if (f <= 1) {
       return f
   }
   fib(f - 1) + fib(f - 2)
}

La salida al ejecutar fib(5) es la siguiente:

Fibonacci de 5
Fibonacci de 4
Fibonacci de 3
Fibonacci de 2
Fibonacci de 1
Fibonacci de 0
Fibonacci de 1
Fibonacci de 2
Fibonacci de 1
Fibonacci de 0
Fibonacci de 3
Fibonacci de 2
Fibonacci de 1
Fibonacci de 0
Fibonacci de 1

Como puedes ver, hay multitud de llamadas repetidas. Si ahora añadimos la anotación @Memoized al método fib() y ejecutamos de nuevo la sentencia anterior se va a producir la siguiente salida:

Fibonacci de 5
Fibonacci de 4
Fibonacci de 3
Fibonacci de 2
Fibonacci de 1
Fibonacci de 0

El resultado no puede ser más claro: gracias a memoization hemos evitado una cantidad muy importante de carga computacional.

Configurando la caché

La anotación @Memoized proporciona un mecanismo para limitar el tamaño de la caché a través del atributo maxCacheSize (tamaño máximo de caché). La estrategia para eliminar valores de la caché cuando hemos alcanzado su valor máximo de elementos se hace a través del algoritmo último valor usado recientemente. Veamos un ejemplo:

@Memoized(maxCacheSize = 3)
static Integer miCalculo(Integer entrada) {
   println "miCalculo de $entrada"
   return entrada
}

Ahora ejecutemos el siguiente código (los comentarios indican el comportamiento que está teniendo lugar en cada momento):

println miCalculo(1) // 1 es añadido en caché
println miCalculo(2) // 2 es añadido en caché
println miCalculo(3) // 3 es añadido en caché
println miCalculo(1) // 1 es leído desde caché
println miCalculo(4) // 4 es añadido en caché, 2 es eliminado (éste último es el último valor usado recientemente)
println miCalculo(1) // 1 es leído desde caché
println miCalculo(1) // 1 es leído desde caché
println miCalculo(2) // 2 es añadido en caché, 3 es eliminado (mismo comportamiento que antes)
println miCalculo(5) // 5 es añadido en caché, 4 es eliminado (de nuevo, mismo coportamiento que antes)
println miCalculo(1) // 1 es leído desde caché. En este momento 1, 2, y 5 permanecen en caché

El resultado de la ejecución anterior es el siguiente:

miCalculo de 1
1
miCalculo de 2
2
miCalculo de 3
3
1
miCalculo de 4
4
1
1
miCalculo de 2
2
miCalculo de 5
5
1

Ajustar el tamaño máximo de la caché es muy útil cuando es necesario limitar la cantidad de memoria a usar, pero también puede serlo (como ya hemos visto) cuando sabemos que al llegar a cierto punto no vamos a necesitar recalcular valores previamente evaluados ya que estos fueron calculados (de forma directa o indirecta) anteriormente.

También tenemos disponible el atributo protectedCacheSize (tamaño de caché protegido), el cual nos permite ajustar un valor mínimo de valores a retener y va a evitar que sean procesados (y por tanto eliminados) por el recolector de basura de Groovy. La memoization en closures también dispone de un mecanismo similar para ajustar el tamaño de la caché.

Resumen

Como hemos podido ver, memoization proporciona un mecanismo que nos puede resultar extremadamente útil para ahorrar carga computaciónal. Deberías plantearte usarlo en las siguientes situaciones:

  • Cálculos que son lentos (más lentos que búscar un valor en un map)
  • Métodos que sólo dependen del valor de entrada para calcular un valor
  • Métodos que no provocan efectos colaterales (como actualizar una base de datos, escribir en un fichero, etc)
  • Calculos que SIEMPRE devuelven el mismo valor de retorno a partir de cierto valor de entrada

Y por supuesto, no uses memoization cuando:

  • Los datos pueden cambiar en el futuro (la edad de una persona, la probabilidad de que los Minnesota Vikings ganen la Super Bowl, etc)
  • Se necesita más control sobre la caché (almacenarla en disco, ejecutar otras estrategias para eliminar valores cuando hemos alcanzado el valor máximo de elementos, etc)