Functional Programming in JavaScript: A memorização

X

Privacidade e cookies

Este sítio utiliza cookies. Ao continuar, está a concordar com a sua utilização. Saiba mais, por exemplo, como controlar os cookies.

Understood

/div>

div>>div>dvertisements

/div>>/div>

8540563633_e4baebcb26_cp>Image by Lori-B.

A viagem chega ao fim. Com esta última entrada sobre optimização pusemos fim à série sobre programação funcional.

Se na penúltima prestação introduzimos os problemas da programação funcional em termos de desempenho, hoje vou falar de um mecanismo que nos pode ajudar a evitar cálculos e avaliações desnecessários: a memorização. Um termo profundamente enraizado neste estilo de programação.

Se estás comigo desde Outubro, penso que não queres perder esta última entrada. Vamos terminar isto bem:

Caching the results

Como dissemos, um dos problemas da programação funcional foi causado pelo uso intensivo de funções, vimos que quanto mais cálculo precisávamos num sistema, maior a possibilidade de causar a pilha de contexto poderia ultrapassar e deixar-nos pendurados.

Vimos que a avaliação preguiçosa poderia evitar chamadas desnecessárias, no entanto é um sistema bastante limitado e que não causa tempos de melhoria espectaculares. Se pensarmos bem, seria bom ter algum mecanismo que nos permitisse guardar os resultados que já foram calculados.

Em algumas linguagens de programação este cache de resultados é feito nativamente por compiladores, contudo, em linguagens como JavaScript ou Python este cache de resultados tem de ser gerido manualmente.

A ideia do cache é aproveitar a transparência referencial para evitar cálculos desnecessários. Se soubermos que uma função gera sempre os mesmos resultados para determinados parâmetros, podemos executar essa função, quantas vezes quisermos obter que o resultado não mude. Se assim for, poderíamos pensar que não seria necessário estar sempre a calcular os resultados se já soubéssemos que valor será obtido.

É por isso que poderíamos gerar uma cache que armazenasse estes valores. Uma aproximação poderia ser a seguinte:

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 executar essa função tantas vezes quantas quisermos que o resultado seja sempre o mesmo. O bom de usar uma cache intermédia é que só calculamos o valor uma vez, o resto do tempo é obtido a partir da cache, desta forma podemos reduzir os tempos de cálculo ou cálculos que sabemos que levarão tempo.

O problema com esta solução é que estamos a manter uma cache global. Estamos um pouco carregados da filosofia de manter os estados tão isolados quanto possível e pode acontecer que duas funções gerem duas ‘chaves’ iguais e sofram um conflito de resultados.

A solução, como vemos, não é óptima.

Aliminar a cache global: a memorização

Em vez de fazer uso de uma memória tão genérica, seria muito bom que cada função fosse capaz de gerir a sua própria cache interna. No final, precisamos de um mecanismo que seja transparente para nós, algo que não nos impeça de trabalhar como antes, algo que nos permita esquecer a gestão da memória.

Isto é memorização: A capacidade de fazer uma função pura tem um mecanismo onde se pode recordar valores já computados para poupar recursos e tempo. A ideia é envolver uma função num mecanismo de cache, sem alterar o comportamento dessa função.

Uma primeira proposta pode ser alargar o comportamento da ‘Função’ desta forma:

Function.prototype.memoized = function () { const key = JSON.stringify(arguments); this._cache = this._cache || {}; this._cache = this._cache || this.apply(this, arguments); return this._cache;}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’ verifica se a função a ser memorizada é unária e depois devolve uma função que activaria a verificação da cache. Memoriza’ o que faz é ir gerindo aquela cache interna que criámos no objecto Função.

Por enquanto ‘memorizamos’ funções unárias para tornar a explicação mais clara, mas existem mecanismos para ‘memorizar’ qualquer tipo de função.

Se estiver um pouco nervoso em manipular o protótipo de um tipo nativo, temos a mesma solução na forma de fecho:

function memoize(fn) { let _cache = {}; if (fn.length !== 1) { return fn; } return function memoized() { const key = JSON.stringify(arguments); _cache = _cache || this.apply(this, arguments); return _cache; }}const m_findStudent = memoize(findStudent);

Gosto muito mais porque se comporta da mesma forma que o anterior, mas temos o comportamento mais dissociado e não manipulamos o protótipo.

Esta última abordagem é muito semelhante à proposta por Rambda com o seu R.memoize, apenas que a sua solução permite funções ‘memoize’ com qualquer tipo de arity.

Demonstrando que a memoização funciona

Bem, dadas as diferentes abordagens, seria bom se pudéssemos demonstrar que a técnica funciona. Tomemos um exemplo de uma função pura que pode envolver um elevado tempo de computação.

Vamos tomar uma função bastante simples que converte uma ‘string’ com cifra de César:

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

Não estamos interessados no algoritmo em si, concentremo-nos na sua optimização. Vamos usar o método de Rambda para ‘memoize’:

const m_getCipherCaesar = R.memoize(getCipherCaesar);

Both ‘m_getCipherCaesar’ e ‘getCipherCaesar’ têm a mesma assinatura: Dada uma ‘string’, ambas devolvem uma ‘string’ encriptada. A única coisa que os diferencia é o seu tratamento de resultados.

Para testar isto, usaremos a API de desempenho da seguinte forma:

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

E veremos como se comporta:

let testCipherCaesar = IO.of(start) .map(R.tap(test(m_getCipherCaesar, 'prueba_memoizacion'))) .map(end);testCipherCaesar.run(); // 0.733 mstestCipherCaesar.run(); // 0.0021 ms

Como podemos ver, reduz bastante os tempos.

Temos de ser inteligentes ao ‘memorizar’ uma função. Haverá alturas em que a gestão de resultados com uma cache tem uma sobrecarga maior do que o próprio cálculo e não precisaremos dele. Contudo, teremos outros casos, onde podemos guardar muitos dados.

Memoização em recursividade

Memoização pode ser uma boa táctica em algoritmos recursivos. A recorrência baseia-se na quebra de problemas complexos em peças mais pequenas. As soluções intermédias são a soma de um todo que forma a solução final.

Recursão tende a ter um grande número de resultados intermédios iguais. Se dissemos que as caches de memorização resultam de modo a que nos próximos acessos o valor já esteja calculado, parece lógico pensar que estas técnicas se entenderão bem.

Imagine um caso como o factorial. Imagine que em algum problema, preciso de conhecer o factorial de 100 e o factorial de 101. Quando faço o factorial de 100, logicamente preciso de percorrer toda a recorrência.

Mas quando de repente preciso do factorial de 101, todos os factoriais até 100 são armazenados em cache. Os tempos de cálculo podem ser drasticamente reduzidos. Vamos ter isso em mente.

Conclusão

Como vemos um sistema de cache super útil que nos pode poupar muito tempo desnecessário. A transparência referencial é um conceito tão fundamental na programação funcional que, tendo tão claras as suas vantagens, pode ajudar-nos a encontrar as nossas próprias soluções.

Despedida final

E isto termina… Queria agradecer a todos aqueles que contribuíram com a sua parte para tornar esta série possível. Foram meses em que aprendi muito e em que penso ter melhorado como programador. Sem o seu apoio e feedback teria sido mais difícil encontrar tempo para dedicar a algo como isto.

p>Queria agradecer a Luis Atencio pelo seu grande livro. Talvez um dos livros que me ajudou a compreender tantos conceitos e a facilitar-me o que é difícil. Recomendo vivamente o seu livro sobre Programação Funcional em JavaScript. É um must have.

Levamos ler 🙂

P>P posts anteriores sobre Programação Funcional em JavaScript:

Introduction

  1. Programação Funcional em JavaScript
  2. Programação Funcional em JavaScript: Objectos
  3. Programação funcional em JavaScript: As Funções

O Controlo de Fluxo Funcional

  1. Programação Funcional em JavaScript: Métodos funcionais
  2. Programação funcional em JavaScript: Recursion

Functional modularity

    1. Functional Programming in JavaScript: Arity e tuples
    2. Functional Programming in JavaScript: Currificação

    3. Programação funcional em JavaScript: Composição
    4. Programação funcional em JavaScript: Combinadores

    Padrões funcionais

    1. Programação funcional em JavaScript: Os functores
    2. Programação funcional em JavaScript: A Mónada Talvez
    3. Functional Programming in JavaScript: A Mónada

      Functional Programming in JavaScript: A mónada IO

    A optimização funcional

    1. Programação funcional em JavaScript: Avaliação preguiçosa
    2. Programação funcional em JavaScript: Memoization

Deixe uma resposta

O seu endereço de email não será publicado. Campos obrigatórios marcados com *