Artigo original: How to use Memoize to cache JavaScript function results and speed up your code

As funções são uma parte integral da programação. Elas ajudam a adicionar modularidade e reusabilidade ao código.

É muito comum dividir nossos programas em partes usando funções que podemos chamar mais tarde para realizar alguma função útil.

Por vezes, pode ficar pesado chamar uma função diversas vezes (por exemplo, uma função que calcule o fatorial de um número). Existe, porém, um modo através do qual podemos otimizar essas funções e fazê-las executarem mais rapidamente: o cache.

Por exemplo, digamos que temos uma function que retorna o fatorial de um número:

function fatorial(n) {
    // Cálculos: n * (n-1) * (n-2) * ... (2) * (1)
    return fatorial
}

Vamos encontrar o fatorial(50). O computador realizará cálculos e retornará o resultado. Ótimo!

Ao terminarmos, vamos calcular fatorial(51). O computador mais uma vez realizar diversos cálculos e nos dá um resultado. Você, contudo, deve ter percebido que já estamos repetindo uma quantidade de passos que podiam ter sido evitados. Um modo otimizado de fazer esse cálculo seria:

fatorial(51) = fatorial(50) * 51

Nossa function, no entanto, realiza os cálculos desde o início sempre que é chamada:

fatorial(51) = 51 * 50 * 49 * ... * 2 * 1

Não seria incrível se, de algum modo, nossa função fatorial pudesse lembrar dos valores de seus cálculos anteriores e pudesse usá-los para acelerar sua execução?

É aí que entra a memoização, um modo de nossa function lembrar (colocar em cache) dos resultados. Agora que você tem um entendimento básico daquilo que estamos buscando obter, aqui temos uma definição mais formal:

A memoização é o armazenamento de resultados de chamadas de função custosas. (Traduzido da Wikipédia em inglês)

Memoizar, simplificando, significa memorizar ou armazenar na memória. Uma função memoizada geralmente é mais rápida, pois se a função é chamada mais tarde com os valores anteriores guardados, em vez de executar a função, obteríamos o resultado a partir do cache.

Vamos mostrar aqui como seria uma função memoizada simples (veja a função no CodePen caso queira interagir com ela):

// Uma função simples de adição
const adicionar = (n) => (n + 10);
add(9);
// Uma função simples memoizada para adição
const adicionarMemoizado = () => {
  let cache = {};
  return (n) => {
    if (n in cache) {
      console.log('Obtendo no cache');
      return cache[n];
    }
    else {
      console.log('Calculando o resultado');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
}
// Função retornada de adicionarMemoizado
const novoAdicionar = adicionarMemoizado();
console.log(novoAdicionar(9)); // calculado
console.log(novoAdicionar(9)); // em cache

O que podemos aprender com a memoização

Algumas coisas que já podemos ver com o código acima:

  • adicionarMemoizado retorna uma function que é invocada (chamada) mais tarde. Isso é possível pois, em JavaScript, as funções são objetos de primeira classe que nos permitem usá-los como funções de ordem superior (texto em inglês) e retornar outra função.
  • cache pode lembrar de seus valores já que a função retornada tem uma closure sobre si.
  • É fundamental que a função memoizada seja pura (texto em inglês). Uma função pura retornará o mesmo resultado para uma entrada qualquer específica não importando quantas vezes ela for chamada, o que faz com que cache funcione da maneira que esperamos.

Como escrever sua própria função memoizar

O código anterior funciona bem, mas e se quisermos transformar qualquer função em uma função memoizada?

Aqui vemos como escrever nossa própria função de memoizar (também disponível no Codepen):

// Uma função pura simples para obter um valor adicionando 10
const adicionar = (n) => (n + 10);
console.log('Chamada simples', adicionar(3));
// Uma função de memoizar simples que recebe uma função
// e retorna uma função memoizada
const memoizar = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];  // pegando apenas um argumento aqui
    if (n in cache) {
      console.log('Obtendo do cache');
      return cache[n];
    }
    else {
      console.log('Calculando o resultado');
      let resultado = fn(n);
      cache[n] = resultado;
      return resultado;
    }
  }
}
// Criação de uma função memoizada para a função pura 'adicionar'
const adicionarMemoizado = memoizar(adicionar);
console.log(adicionarMemoizado(3));  // calculado
console.log(adicionarMemoizado(3));  // em cache
console.log(adicionarMemoizado(4));  // calculado
console.log(adicionarMemoizado(4));  // em cache

Agora, está muito bom! Essa função memoizar simples envolverá qualquer outra função function em um equivalente memoizado. O código funciona bem para funções simples e pode ser facilmente ajustado para lidar com um número diversificado de argumentos, conforme sua necessidade. Outra alternativa é usar bibliotecas de fato, tais como:

  • _.memoize(func, [resolver]) da biblioteca Lodash
  • Os decorators @memoize do ES7 (texto em inglês), da biblioteca decko

Memoização de funções recursivas

Se você tentar passar uma função recursiva para a função memoizar acima ou para a função _.memoize do Lodash, os resultados não serão aqueles que você esperaria, pois a função recursiva, em suas chamadas posteriores, acabará chamando a si mesma em vez de chamar a função memoizada e, assim, não fará uso do cache.

Certifique-se de que sua função recursiva chamará a função memoizada. Aqui vemos como ajustar um exemplo de fatorial clássico (código disponível no Codepen):

// A mesma função memoizar de antes
const memoizar = (fn) => {
  let cache = {};
  return (...args) => {
    let n = args[0];
    if (n in cache) {
      console.log('Obtendo do cache', n);
      return cache[n];
    }
    else {
      console.log('Calculando o resultado', n);
      let resultado = fn(n);
      cache[n] = resultado;
      return resultado;
    }
  }
}
const fatorial = memoizar(
  (x) => {
    if (x === 0) {
      return 1;
    }
    else {
      return x * fatorial(x - 1);
    }
  }
);
console.log(fatorial(5)); // calculada
console.log(fatorial(6)); // calculada para 6 e do cache para 5

Alguns pontos importantes de se observar nesse código:

  • A função fatorial está chamando recursivamente uma versão memoizada de si mesma.
  • A função memoizada está guardando em cache os valores dos fatoriais anteriores, o que melhora o cálculo significativamente, já que os resultados podem ser reutilizados, por exemplo: fatorial(6) = 6 * fatorial(5)

Memoização é o mesmo que guardar em cache?

Em parte, sim. A memoização, de fato, é um tipo específico de cache. Embora cache possa, em geral, se referir a qualquer técnica de armazenamento (como o cache do HTTP) para uso futuro, a memoização envolve especificamente o cache dos valores de retorno de uma function.

Quando memoizar suas funções

Embora possa parecer que a memoização possa ser usada com todas as funções, ela, de fato, tem casos de uso limitados:

  • Para memoizar uma função, ela deve ser pura, de modo que os valores retornados por ela sejam sempre os mesmos para as mesmas entradas
  • A memoização faz uma permuta que pode não ser vantajosa entre o espaço adicionado e a velocidade adicionada. Assim sendo, ela só é significativa para funções que tenham um intervalo de entradas limitado, de modo que os valores em cache possam ser usados com mais frequência
  • Pode parecer que você deve memoizar suas chamadas de API. No entanto, isso não é necessário, já que o navegador faz o cache automático dessas chamadas para você. Consulte cache de HTTP para saber mais detalhes
  • O melhor caso de uso que encontrei para funções memoizadas foi o de funções altamente computacionais, onde a memoização pode melhorar significativamente o desempenho (o fatorial e o cálculo de Fibonacci não são bons exemplos do mundo real)
  • Se você gosta de e trabalha com React/Redux, pode conferir a biblioteca reselect, que usa um seletor memoizado para garantir que os cálculos somente aconteçam quando uma mudança acontecer em uma parte relacionada da árvore do state.

Outras leituras

Os links a seguir (em inglês) podem ser úteis se você quiser saber mais detalhes sobre os tópicos deste artigo:

Espero que este artigo tenha sido útil para você e que você agora entenda melhor a memoização no JavaScript. 😀