Patrón de diseño Memoization

El patrón de diseño Memoization es una técnica de optimización en programación en la cual se almacenan los resultados de funciones que requieren cálculos muy costosos para evitar volver a calcularlos.

Su funcionamiento es simple. La primera vez que se llama a una función con un conjunto de argumentos dado, se calcula el resultado y se guarda en una caché o diccionario. La próxima vez que se llama a la función con el mismo conjunto de argumentos, se devuelve el resultado guardado en la caché en lugar de volver a calcularlo.

A continuación puedes ver un ejemplo en Python donde se suma los números de la secuencia Fibonacci recursivamente. Se basa en un decorador que almacena en un diccionario los resultados de la función, para en caso de volver a invocarse devolver los valores previamente guardados.

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(40))
# 102334155

El mismo ejemplo podemos implementarlo en JavaScript.

function memoize(fn) {
    let cache = {};
    return function(...args) {
        const key = JSON.stringify(args);
        if (cache[key]) {
            return cache[key];
        }
        else {
            const result = fn(...args);
            cache[key] = result;
            return result;
        }
    }
}

let fibonacci = memoize(function fibonacci(n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
});

console.log(fibonacci(40));
// 102334155

Disclaimer: Python posee optimizaciones internas que invalidan el ejemplo ya que aplica técnicas similares de serie; sin embargo, en JavaScript no. Te recomiendo que utilices el segundo ejemplo para hacer sus pruebas.

Deberíamos utilizarlo porque mejora significativamente el rendimiento cuando se llama varias veces a la misma función con los mismos argumentos. Se utiliza principalmente en problemas recursivos, especialmente en funciones que se llaman a sí mismas con los mismos argumentos. Aunque también mejora exponencialmente el rendimiento de una aplicación que depende de una API para su contenido.