Programación Funcional en JavaScript: La memoización

8540563633_e4baebcb26_c

Imagen de Lori-B.

El viaje se termina. Con esta última entrada sobre optimización ponemos punto y final a la serie sobre programación funcional.

Si en la penúltima entrega introdujimos los problemas de la programación funcional en cuanto a rendimiento, hoy voy a hablaros de un mecanismo que puede ayudarnos a evitar cómputos y evaluaciones innecesarias: la memoización. Un término muy arraigado a este estilo de programación.

Si llevas conmigo desde Octubre, no creo que quieras perderte esta última entrada. Terminemos esto bien:

Cacheando los resultados

Como dijimos, uno de los problemas de la programación funcional venía provocado por el uso intensivo de funciones, vimos que cuanto mayor número de cómputo necesitábamos en un sistema, mayor era la posibilidad de provocar que la pila de contexto pudiera llegar a sobrepasarse y dejarnos colgados.

Vimos que la evaluación perezosa podía evitar llamadas innecesarias,  sin embargo es un sistema bastante limitado y que no provoca unos tiempos de mejora espectaculares. Si lo pensamos en frío que bueno sería contar con algún mecanismo que nos permitiera cachear resultados que ya hubieran sido calculados .

En algunos lenguajes de programación este cacheo de resultado se realiza de forma nativa por los compiladores, sin embargo, en lenguajes como JavaScript o Python este cacheo de resultado tiene que gestionarse de manera manual.

La idea del cacheo es aprovecharse de la transparencia referencial para poder evitar cálculos innecesarios. Si nosotros sabemos que una función genera siempre los mismos resultados para unos parámetros dados, podremos ejecutar esa función, tantas veces como queramos consiguiendo que el resultado no cambiara. Si esto es así, podríamos pensar que no sería necesario estar computando los resultados todo el rato si ya sabemos que valor se va a obtener.

Es por eso, que podríamos generar una caché que fuese almacenando estos valores. Una aproximación podría ser la siguiente:

function fnCache(cache, fn, args) {
    const key = fn.name + JSON.stringify(args);

    if (contains(cache, key)) {
        return get(cache, key);
    }
    
    const result = fn.apply(this, args);
    set(cache, key, result);
    return result;
}

let cache = {};
fnCache(cache, findStudent, '03123456J');
fnCache(cache, findStudent, '03123456J');

Podemos ejecutar esa función las veces que queramos que el resultado siempre es el mismo. Lo bueno de usar una caché intermedia es que solo calculamos el valor una vez, el resto de veces es obtenido de la caché, de esta forma podemos reducir los tiempos de cálculo o cómputos que sepamos que se demorarán en el tiempo.

El problema de esta solución es que estamos manteniendo una caché global. Nos cargamos un poco la filosofía de mantener estados lo más aislados posibles y puede darse el caso de que dos funciones generen dos ‘keys’ iguales y se sufra un conflicto de resultados.

La solución, como vemos, no es óptima.

Eliminando la caché global: la memoización

En vez de hacer uso de una memoria tan genérica, sería muy bueno que cada función fuese capaz de gestionar su propia caché interna. Al final, necesitamos un mecanismo que sea transparente para nosotros, algo que no nos impida trabajar como antes, algo que permita olvidarnos de gestiones de memoria.

Esto es la memoización: La capacidad de hacer que una función pura cuente con un mecanismo en el que pueda recordar valores ya computados para ahorrar recursos y tiempos. La idea es envolver una función en un mecanismo de caché, sin que el comportamiento de dicha función se vea alterado.

Una primera propuesta puede ser la de extender el comportamiento de ‘Function’ de esta manera:

Function.prototype.memoized = function () {
    const key =  JSON.stringify(arguments);
    
    this._cache = this._cache || {};
    this._cache[key] = this._cache[key] || this.apply(this, arguments);

    return this._cache[key];
}

Function.prototype.memoize = function () {
     const fn = this;

     if (fn.length !== 1) {
         return fn;
     }

     return function () {
          return fn.memoized.apply(this, arguments);
     }
}

const m_findStudent = findStudent.memoize();

‘memoize’ comprueba que la función que se quiere memoizar es unaria y después devuelve una función que provocaría el control de la caché. ‘memoized’ lo que hace es ir gestionando esa caché interna que hemos creado en el objeto Function.

Por ahora ‘memoizamos’ funciones unarias para que la explicación sea más clara, pero existen mecanismos para ‘memoizar’ cualquier tipo de función.

Si os pone un poco nerviosos manipular el prototipo de un tipo nativo, tenemos la misma solución en forma de closure:

function memoize(fn) {
     let _cache = {};
    
     if (fn.length !== 1) {
         return fn;
     }

     return function memoized() {
         const key = JSON.stringify(arguments);
         _cache[key] = _cache[key] || this.apply(this, arguments);
         return _cache[key];
     }
}

const m_findStudent = memoize(findStudent);

A mi me gusta bastante más porque se comporta igual que la anterior, pero tenemos el comportamiento más desacoplado y no manipulamos el prototipo.

Esta última aproximación es muy parecida a la que propone Rambda con su R.memoize, solo que su solución permite ‘memoizar’ funciones con cualquier tipo de aridad.

Demostrando que la memoización funciona

Bueno, pues vista las diferentes aproximaciones, sería bueno que pudiésemos demostrar que la técnica funciona. Pongamos un ejemplo de una función pura que pueda conllevar un tiempo elevado de cómputo.

Cojamos una función bastante sencilla que convierta un ‘string’ con cifrado César:

const getCipherCaesar = s => 
    s.replace(/[a-zA-Z]/g, c => 
        String.fromCharCode((c <= 'Z' ? 90 : 122            >= (c = c.charCodeAt(0) + 13) ? c : c - 26))

No nos interesa el algoritmo en sí, centrémonos en su optimización. Usemos el método de Rambda para ‘memoizar’:

const m_getCipherCaesar = R.memoize(getCipherCaesar);

Tanto ‘m_getCipherCaesar’ como ‘getCipherCaesar’ tienen la misma firma: Dado un ‘string’, ambas devuelven un ‘string’ cifrado. Lo único que las diferencia es su gestión de resultados.

Para probar esto vamos a usar la API de performance de la siguiente manera:

const start = () => performance.now();
const end = (start) => (performance.now() - start).toFixed(3);
const test = (fn, arg) => () => fn(arg);

Y veremos cómo se comporta:

let testCipherCaesar = 
     IO.of(start)
       .map(R.tap(test(m_getCipherCaesar, 'prueba_memoizacion')))
       .map(end);

testCipherCaesar.run(); // 0.733 ms
testCipherCaesar.run(); // 0.0021 ms

Como vemos, se reduce bastante los tiempos.

Tenemos que ser inteligentes a la hora de ‘memoizar’ una función. Habrá ocasiones que gestionar resultados con una caché tenga un gasto superior al del propio cómputo y que no nos hará falta. Sin embargo, tendremos otros casos, donde podremos ahorrar muchos datos.

La memoización en la recursividad

La memoización puede ser una buena táctica en algoritmos recursivos. La recursividad se basa en dividir problemas complejos en partes más pequeñas. Las soluciones intermedias son la suma de un todo que forma la solución final.

La recursividad tiende a tener un número elevado de resultados intermedios iguales. Si hemos dicho que la memoización cachea resultados para que en próximos accesos el valor ya esté calculado, parece que tiene cierta lógica pensar que estas técnicas se van a llevar bien.

Imaginemos un caso como el factorial. Imaginaros que en algún problema, necesito saber el factorial de 100 y el factorial de 101. Cuando yo realizo el factorial de 100, logicamente necesito recorrer toda la recursividad.

Pero cuando de pronto yo necesito el factorial de 101. Todos los factoriales hasta 100 se encuentran cacheados. Los tiempos de cálculo se pueden reducir drásticamente. Tengámoslo en cuenta.

Conclusión

Cómo vemos un sistema de caché super útil que puede ahorrarnos muchos tiempos innecesarios. La transparencia referencial es un concepto tan clave en la programación funcional que tener tan claras sus ventajas, podrá ayudarnos a encontrar nuestras propias soluciones.

Despedida final

Y esto se acaba… Quería daros las gracias a todos los que han aportado su granito de arena para que esta serie haya sido posible. Han sido meses en los que he aprendido mucho y donde creo que he mejorado como programador. Sin vuestro apoyo y feedback hubiera sido más difícil encontrar el tiempo necesario para dedicárselo a algo así.

Quería darle las gracias a Luis Atencio por su grandísimo libro. Quizá uno de los libros que más me han ayudado a entender tantos conceptos y hacerme fácil lo difícil. Os recomiendo su libro de Programación Funcional en JavaScript encarecidamente. Es un must have.

Nos leemos 🙂

Anteriores posts de Programación Funcional en JavaScript:

Introducción

  1. La Programación Funcional en JavaScript
  2. Programación Funcional en JavaScript: Los Objetos
  3. Programación Funcional en JavaScript: Las funciones

El control de flujo funcional

  1. Programación Funcional en JavaScript: Los métodos funcionales
  2. Programación Funcional en JavaScript: La recursividad

La modularidad funcional

  1. Programación Funcional en JavaScript: La aridad y las tuplas
  2. Programación Funcional en JavaScript: La currificación
  3. Programación Funcional en JavaScript: La composición
  4. Programación Funcional en JavaScript: Los combinadores

Los patrones funcionales

  1. Programación Funcional en JavaScript: Los funtores
  2. Programación Funcional en JavaScript: La mónada Maybe
  3. Programación Funcional en JavaScript: La mónada Either
  4. Programación Funcional en JavaScript: La mónada IO

La optimización funcional

  1. Programación Funcional en JavaScript: La evaluación perezosa
  2. Programación Funcional en JavaScript: La memoización
Anuncios

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 )

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 )

Google+ photo

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

Conectando a %s