Functional Programming (Memoization) em JavaScript

Olá pessoal. Tudo certo?!

Há algum tempo, escrevi um post falando sobre técnicas de Functional Programming em C#. Dentre essas técnicas, está Memoization. Basicamente, essa técnica melhora a performance de aplicativos evitando a repetição de cálculos para entradas já processadas.

No post de hoje, apresento essa técnica em JavaScript.

Explicitando o problema

Considere o código abaixo:

fibonacci = function (depth) {
    if (depth < 2) {
        return depth;
    }
    else {
        return fibonacci(depth - 1) + fibonacci(depth - 2);
    }
}


$(function () {
    var start = new Date().getTime();
    for (var i = 0; i < 45; i++) {
        document.writeln(fibonacci(i));
        document.writeln("
");
    }
    var end = new Date().getTime();
    var time = end - start;
    document.writeln(time);
});

O que esse programa faz é muito simples. Basicamente, definimos a função para Fibonacci e imprimimos os primeiros 45 números da série.

Esse simples algoritmo demora muito tempo para completar sua execução (desisti de esperar).

Perceba como que, a mesma função é executada um sem fim de vezes.

Criando uma versão com Memoization

Considere agora essa versão modificada:

fibonacci = function (depth) {
    if (!(depth in fibonacci)) {
        if (depth < 2) {
            fibonacci[depth] = depth;
        }
        else {
            fibonacci[depth] = fibonacci(depth - 1) + fibonacci(depth - 2);
        }
    }
    return fibonacci[depth];
}

Com essa versão, o programa conclui quase que imediatamente. O que mudou!? Armazemamos os resultados dos processamentos anteriores no objeto da função. Veja como há uma redução grotesca de complexidade do algoritmo.

Perceba que poderíamos ter armazenado os resultados intermediários em uma variável global. Mas, isso não é necessário, pois esses dados são utilizados apenas pela função. Assim, é melhor armazenar a informação em uma propriedade do “objeto” função.

Compreendido?!

Uma High-Order Function que “entrega” Memoization

No exemplo anterior, reduzi a complexidade de execução do algoritmo. Entretanto, aumentei a complexidade acidental do problema. Há como evitar esse problema? Penso que sim. Considere:

fibonacci = function (depth) {
    if (depth < 2) {
        return depth;
    }
    else {
        return fibonacci(depth - 1) + fibonacci(depth - 2);
    }
}

memoize = function (fn) {
    var cache = {};
    return function () {
        var key = Array.prototype.join.call(arguments, ",");
        if (!(key in cache))
            cache[key] = fn.apply(this, arguments);
        return cache[key];
    };
}

var fiboWithMemoization = memoize(fibonacci);

Nesse exemplo, memoize é uma “higher-order function” que gera funções com suporte a memoization. Essa versão perde um bocado, quando comparada ao exemplo anterior, principalmente pelo join executado nas consultas.

Bom, era isso.