Memoization en ruby

La memoization es una técnica de optimización que consiste en recordar los resultados para anteriores llamadas a una función.

Si para una llamada anterior a una función se han pasado los parámetros x=2 e y=3, la próxima vez se devolverá el mismo resultado al obtenido, sin repetir cálculos.

La implementación es muy sencilla y se pueden obtener mejoras muy significativas en funciones con cálculos pesados, basta con tener una tabla en la que utilicemos los parámetros de entrada como índices y el resultado de la función como valor.

Si ya de por sí es sencillo implementar la memoization en ruby se puede usar también la gema que hay específica para ello, esta gema implementa la memoization automática, por lo que ni siquiera es necesario mantener una tabla para los valores, la gema se encarga de ello.

Es necesario recordar que en la memoization solo se tienen en cuenta los parámetros de entrada, por lo que a las funciones que produzcan resultados a partir de otras entradas (ficheros, hora actual...) no se les debe aplicar esta técnica.

En el siguiente ejemplo se implementa la función de fibonacci recursiva (fib1), la misma función aplicándole la memoization (fib2) y por último la memoization automática a fib1. En mi máquina para este ejemplo se obtienen ganancias de 30 a 40 veces en las versiones memoizadas.

require 'rubygems'
require 'memoize'

include Memoize

def fib1(n)
 return n if n < 2
 return fib1(n-1) + fib1(n-2)
end


@mm = {}
def fib2(n)
 return @mm[n] if @mm[n]
 return n if n < 2
 
 @mm[n] = fib2(n-1) + fib2(n-2)
 return @mm[n]
end

puts fib1(30)
puts fib2(30)

memoize(:fib1)
puts fib1(30)