Memoization: Acelerando funciones recursivas. Ejemplo con Javascript.

En su día hablamos aquí sobre la recursividad y sus “peligros“. Las funciones recursivas son muy costosas a nivel de recursos pues al llamarse a si mismas repiten varias veces el mismo paso ¿hay una solución?

Memoization (memorización) es una técnica consistente en almacenar los resultados de funciones muy costosas para devolverlos directamente en lugar de volver a calcularlos.

Por ejemplo, la siguiente función que ya vimos en un artículo anterior nos permitiría calcular un factorial con javascript:

function factorial(num)
{
    if (num < 0) {
        return 0;
    }
    else if (num == 0) {
        return 1;
    }
    else {
        return (num * factorial(num - 1));
    }
}

¿Podemos optimizar mucho esta función cacheando los datos? Podemos:

function factorial(num) {
    // inicializamos si es necesario
    if (!factorial.cache) {
        factorial.cache = {};
    }
    if (num == 0) {
        return 1;
    } else if (num in factorial.cache) {
    // si ya tenemos en cache el factorial de num, lo devolvemos
        return factorial.cache[num];
    } else {
    factorial.cache[num] = num * factorial(num - 1);
    return factorial.cache[num];
}
 

De esta forma nos ahorramos varias llamadas a la función pues simplemente devolvemos un valor almacenado en memoria. Esta no es una técnica exclusiva de Javascript, podemos utilizarla con otros lenguajes de programación. Javascript sí tiene la particularidad de tratar las funciones como un objeto más, eso nos permite por ejemplo definirle la propiedad cache en el ejemplo de arriba (en otros lenguajes deberíamos pasarle como parámetro a la función el array de valores o declararlo como variable global), esto también nos permite hacer que una función reciba como parámetro una función o devuelva como resultado otra función, lo que se conoce como higher-order function o función de orden superior. Sirviéndonos de esto podríamos declarar una función genérica para nuestro memoization:

const memoization = function(func){
    const cache = {};
    return (...args) => {
        const key = [...args].toString();
        return key in cache ? cache[key] : (cache[key] = func(...args));
    }
}

De esta forma podríamos definir nuestra función factorial() tal que así:

var factorial = memoization(function(num) {		
    return (num <= 1) ? 1 : num * factorial(num-1);
})

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios .