Memoization cache: o que é e como otimizar funções

Memoization cache é uma técnica de otimização que faz uma função lembrar os resultados de chamadas anteriores. Em vez de recalcular tudo do zero, a função consulta um armazenamento interno e, se o resultado para aqueles argumentos já existe, devolve imediatamente. O ganho é maior quando a mesma função é chamada muitas vezes com os mesmos parâmetros, como em recursões de Fibonacci ou em processamento de dados repetitivos.

A ideia central é simples: trocar tempo de processamento por espaço de memória. Cada resultado fica guardado em uma estrutura de dados, geralmente um objeto ou mapa, associado aos argumentos da chamada. Na próxima invocação, a função verifica se a chave já existe. Se existe, retorna o valor salvo. Se não, calcula, armazena e retorna.

O que é memoization cache exatamente?

Memoization cache é a combinação de duas palavras que descrevem o mecanismo. Memoization é o nome da técnica de memorizar resultados de funções. Cache é o local onde esses resultados ficam guardados. Na prática, toda memoization usa um cache, mas nem todo cache é memoization.

O termo vem do latim memorandum, que significa "aquilo que deve ser lembrado". A técnica foi formalizada por Donald Michie em 1968, em um artigo sobre inteligência artificial. Desde então, virou padrão em linguagens como JavaScript, Python e Ruby, principalmente em programação funcional.

Um exemplo clássico é a sequência de Fibonacci. Sem memoization, calcular fib(40) exige milhões de chamadas recursivas. Com memoization, cada valor é calculado uma única vez e reutilizado nas chamadas seguintes. O resultado é o mesmo, mas o tempo de execução cai drasticamente.

Qual é a diferença entre memoization e caching?

Caching é o conceito mais amplo: armazenar qualquer dado para uso futuro. Pode ser um arquivo em disco, uma resposta de API ou um banco de dados. Memoization é um caso específico de caching, aplicado a funções puras.

Uma função pura é aquela que, para os mesmos argumentos, sempre retorna o mesmo resultado, sem efeitos colaterais. É exatamente esse comportamento que torna a memoization segura. Se a função depende de estado global, de data atual ou de entrada do usuário, o cache pode devolver resultados desatualizados.

Por exemplo, um cache de página web pode armazenar o HTML inteiro por alguns minutos. Já a memoization de uma função que soma dois números guarda apenas o resultado da soma. A diferença está no escopo e no controle de invalidação.

Como implementar memoization em JavaScript?

Em JavaScript, a implementação mais direta usa um objeto como cache. A função verifica se a chave existe no objeto antes de calcular. Veja um exemplo com uma função que multiplica dois números:

const memoizedMultiply = (() => { const cache = {}; return (a, b) => { const key = ${a}-${b}; if (key in cache) { return cache[key]; } const result = a * b; cache[key] = result; return result; }; })();

A chave é uma string que combina os argumentos. Para funções com um único argumento numérico, a chave pode ser o próprio número. Para múltiplos argumentos, é preciso criar uma chave única, como um separador ou JSON.stringify.

Outra abordagem é usar um Map em vez de objeto. Map aceita qualquer tipo de chave, inclusive objetos, e mantém a ordem de inserção. Para funções que recebem objetos, Map evita a conversão implícita para string.

Em cenários mais complexos, bibliotecas como Lodash oferecem a função _.memoize, que já lida com a criação de chaves. O uso é simples: _.memoize(fn) retorna uma versão memoizada da função original.

Como aplicar memoization em Python?

Python tem um decorador nativo chamado functools.lru_cache. Ele faz a memoization automaticamente, incluindo o controle de tamanho do cache. Basta adicionar @lru_cache antes da definição da função:

from functools import lru_cache

@lru_cache(maxsize=128) def fibonacci(n): if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2)

O parâmetro maxsize define quantos resultados ficam armazenados. Quando o limite é atingido, os itens menos usados são removidos. Sem o maxsize, o cache cresce sem limite, o que pode consumir memória em funções com muitas combinações de argumentos.

O lru_cache também funciona com funções que recebem múltiplos argumentos, desde que eles sejam hasháveis. Listas e dicionários não podem ser usados diretamente, porque são mutáveis. Nesse caso, é preciso converter para tupla ou usar uma função auxiliar.

Quando a memoization cache vale a pena?

A memoization compensa quando a função é chamada repetidamente com os mesmos argumentos e o custo de cálculo é alto. Recursão, processamento de imagens, consultas a APIs externas e cálculos matemáticos complexos são bons candidatos.

Por outro lado, se a função é chamada poucas vezes ou os argumentos variam muito, o cache pode ocupar memória sem trazer benefício. Também não faz sentido memoizar funções com efeitos colaterais, como leitura de arquivo ou escrita em banco, porque o resultado pode mudar a cada chamada.

Um caso comum de uso é em aplicações web, onde a mesma consulta de dados é feita várias vezes durante uma sessão. Memoizar a função de busca pode reduzir a latência, mas é preciso lembrar de invalidar o cache quando os dados forem atualizados.

Quais são os riscos e limitações da memoization?

O principal risco é o consumo de memória. Se a função recebe muitos argumentos diferentes, o cache cresce rapidamente. Sem um limite, pode causar vazamento de memória em aplicações de longa duração.

Outra limitação é a complexidade de invalidar o cache. Em sistemas dinâmicos, os dados mudam com frequência. Se a memoization não for limpa ou atualizada, a função pode retornar valores obsoletos.

Além disso, funções que dependem de variáveis globais ou de estado externo não são boas candidatas. O comportamento imprevisível torna o cache inútil ou até prejudicial.

Por fim, a memoization não deve ser usada em funções que retornam objetos mutáveis. Se o resultado armazenado for alterado fora da função, o cache fica corrompido. Nesse caso, é melhor retornar uma cópia ou usar imutabilidade.

Como testar se a memoization está funcionando?

A forma mais simples é adicionar um log dentro da função e contar quantas vezes ela é executada. Com memoization, a função deve ser chamada apenas uma vez para cada conjunto de argumentos.

Em JavaScript, você pode usar um contador global:

let count = 0; function soma(a, b) { count++; return a + b; } const memoizedSoma = memoize(soma); memoizedSoma(1, 2); memoizedSoma(1, 2); console.log(count); // deve ser 1

Em Python, o lru_cache expõe estatísticas através do método cache_info(). Ele retorna o número de chamadas, acertos e erros do cache. Isso ajuda a avaliar se a técnica está trazendo ganho real.

Resumo e próximos passos

Memoization cache é uma técnica valiosa para otimizar funções puras com chamadas repetidas. Ela troca memória por tempo de processamento, mas exige cuidado com invalidação e consumo de recursos.

Comece aplicando em funções recursivas ou em cálculos caros no seu projeto. Teste com dados reais e meça o impacto. Se o ganho for significativo, generalize para outras funções com o mesmo padrão.

Perguntas frequentes sobre memoization cache

Memoization cache é a mesma coisa que cache HTTP?

Não. Cache HTTP armazena respostas de rede em navegadores ou servidores. Memoization é específica para funções em tempo de execução. São estratégias diferentes, embora compartilhem o princípio de evitar trabalho repetido.

Posso usar memoization em funções assíncronas?

Sim, mas é mais complexo. Você precisa armazenar a Promise, não o resultado final. Assim, chamadas simultâneas compartilham a mesma Promise em vez de disparar múltiplas execuções.

Como limpar o cache de uma função memoizada?

Em Python, use o método cache_clear() do lru_cache. Em JavaScript, você pode expor uma função que redefine o objeto ou Map de cache. Em bibliotecas como Lodash, use cache.clear().

Memoization funciona com funções que recebem objetos?

Depende. Em JavaScript, objetos são convertidos para string, o que pode gerar colisões. Em Python, os argumentos precisam ser hasháveis. Em ambos os casos, é preciso criar uma chave única e confiável.

Quanto de memória a memoization consome?

Depende do número de argumentos e do tamanho dos resultados. O lru_cache permite limitar o tamanho com maxsize. Em JavaScript, é preciso implementar um limite manualmente ou usar uma biblioteca.

Memoization é uma boa prática para todas as funções?

Não. Só faz sentido para funções puras e caras, chamadas repetidamente com os mesmos argumentos. Para funções simples ou com efeitos colaterais, o custo do cache supera o benefício.