Na computação, a memoização (do inglês memoization, também grafado memoisation) é uma técnica de otimização usada principalmente para acelerar programas de computador. Ela funciona armazenando os resultados de chamadas computacionalmente custosas a funções puras, para que esses resultados possam ser retornados rapidamente caso as mesmas entradas ocorram novamente. É um tipo de armazenamento em cache, normalmente implementado por meio de uma tabela de dispersão. Constitui um exemplo típico de compromisso espaço–tempo, no qual o tempo de execução de um programa é reduzido mediante o aumento do uso de memória. A memoização pode ser implementada em qualquer linguagem de programação, embora algumas linguagens tenham suporte integrado que facilita ao programador memoizar uma função, enquanto outras memoizam determinadas funções por padrão.
A memoização também tem sido usada em outros contextos — e para fins diferentes do ganho de velocidade —, como na análise sintática descendente simples com recursão mútua. No contexto de algumas linguagens de programação lógica, a memoização também é conhecida como tabulação.
Etimologia O termo inglês memoization foi cunhado por Donald Michie em 1968 e deriva da palavra latina (“a ser lembrado”), geralmente abreviada como memo no inglês estadunidense, carregando assim o sentido de “transformar [os resultados de] uma função em algo a ser lembrado”. Embora a memoização possa ser confundida com a memorização — pois as palavras são cognatas do ponto de vista etimológico —, memoização tem significado especializado na computação.
Visão geral
Uma função memoizada, ao ser chamada pela primeira vez com determinado conjunto de entradas, armazena essas entradas juntamente com os resultados calculados. Nas chamadas seguintes com entradas já registradas, a função retorna os resultados armazenados em vez de recalculá-los, eliminando assim o custo do recálculo. O conjunto de associações lembradas pode ser um conjunto de tamanho fixo controlado por um algoritmo de substituição ou um conjunto fixo, dependendo da natureza e do uso da função. Uma função somente pode ser memoizada se for referencialmente transparente; isto é, somente se chamar a função tiver exatamente o mesmo efeito que substituir a chamada da função por seu valor de retorno. Há, entretanto, exceções especiais a essa restrição. Embora esteja relacionada às tabelas de consulta, já que a memoização frequentemente emprega essas tabelas em sua implementação, a memoização preenche seu cache de resultados de forma transparente e à medida que a execução ocorre, em vez de exigir que os resultados sejam fornecidos previamente.
As funções memoizadas são otimizadas quanto à velocidade em troca de maior utilização do espaço da memória do computador. O “custo” de tempo e espaço dos algoritmos tem um nome específico na computação: complexidade computacional. Todas as funções têm complexidade computacional em tempo — isto é, levam tempo para ser executadas — e em espaço.
Embora ocorra um compromisso espaço–tempo — isto é, o espaço utilizado é convertido em ganho de velocidade —, isso difere de outras otimizações que envolvem esse tipo de compromisso, como a redução de força, porque a memoização é uma otimização em tempo de execução, e não em tempo de compilação. Além disso, a redução de força pode substituir uma operação custosa, como a multiplicação, por uma operação menos custosa, como a adição, e a economia resultante pode ser altamente dependente da máquina — portanto, não portável entre máquinas —, enquanto a memoização é uma estratégia mais independente da máquina e multiplataforma.
Considere a seguinte função em pseudocódigo para calcular o fatorial de n:
função factorial (n é um número inteiro não negativo) se n for 0 então retorne 1 [pela convenção de que 0! = 1] senão retorne factorial(n – 1) vezes n [invoque factorial recursivamente com o parâmetro 1 menor que n] fim se fim função
Para todo número inteiro n tal que n ≥ 0, o resultado final da função factorial é invariante; se ela for chamada como x = factorial(3), a variável x receberá sempre o valor 6. A implementação não memoizada acima, em razão da natureza recursiva do algoritmo envolvido, exigiria n + 1 chamadas de factorial para chegar a um resultado, e cada uma dessas chamadas, por sua vez, tem um custo associado ao tempo necessário para que a função retorne o valor calculado. Dependendo da máquina, esse custo pode ser a soma de:
O custo de configurar o quadro da pilha da chamada de função. O custo de comparar n com 0. O custo de subtrair 1 de n. O custo de configurar o quadro da pilha da chamada recursiva, como acima. O custo de multiplicar por n o resultado da chamada recursiva de factorial. O custo de armazenar o resultado de retorno para que ele possa ser usado pelo contexto que realizou a chamada.
Em uma implementação não memoizada, toda chamada de nível superior a factorial inclui o custo acumulado das etapas 2 a 6, proporcional ao valor inicial de n.
Uma versão memoizada da função factorial é apresentada a seguir:
função factorial (n é um número inteiro não negativo) se n for 0 então retorne 1 [pela convenção de que 0! = 1] senão, se n estiver em lookup-table, então retorne lookup-table-value-for-n senão defina x = factorial(n – 1) vezes n [invoque factorial recursivamente com o parâmetro 1 menor que n] armazene x em lookup-table na na posição [lembre o resultado de n! para uso posterior] retorne x fim se fim função
Neste exemplo específico, se factorial for chamada primeiro com 5 e depois com qualquer valor menor ou igual a cinco, esses valores de retorno também terão sido memoizados, pois factorial terá sido chamada recursivamente com os valores 5, 4, 3, 2, 1 e 0, e o valor de retorno de cada uma dessas chamadas terá sido armazenado. Se ela for então chamada com um número maior que 5, como 7, somente duas chamadas recursivas serão realizadas — 7 e 6 —, e o valor de 5! já estará armazenado desde a chamada anterior. Dessa forma, a memoização permite que uma função se torne mais eficiente em termos de tempo quanto mais vezes for chamada, resultando em uma aceleração geral ao longo do uso.
Um exemplo extremo de memoização é o padrão Singleton, especificamente a implementação de seu getter: uma função que cria um objeto na primeira chamada, armazena a instância em cache e retorna o mesmo objeto em todas as chamadas seguintes.
Outras considerações Programação funcional
A memoização é muito utilizada em compiladores de linguagens de programação funcional, que frequentemente empregam a estratégia de avaliação por nome. Para evitar a sobrecarga de calcular os valores dos argumentos, os compiladores dessas linguagens utilizam amplamente funções auxiliares chamadas thunks para calcular esses valores e memoizam tais funções para evitar cálculos repetidos.
Memoização automática
Embora a memoização possa ser adicionada às funções de maneira interna e explícita por um programador, de forma semelhante à implementação da versão memoizada de factorial apresentada acima, funções referencialmente transparentes também podem ser memoizadas automaticamente de maneira externa. As técnicas utilizadas por Peter Norvig têm aplicação não apenas em Common Lisp — a linguagem na qual seu artigo demonstrou a memoização automática —, mas também em várias outras linguagens de programação. Aplicações da memoização automática também foram exploradas formalmente no estudo de reescrita de termos e de inteligência artificial.
Em linguagens de programação nas quais as funções são objetos de primeira classe — como Lua, Python ou Perl —, a memoização automática pode ser implementada substituindo-se, em tempo de execução, uma função pelo valor calculado por ela assim que um valor tiver sido calculado para determinado conjunto de parâmetros. A função que realiza essa substituição do objeto-função pelo valor pode envolver genericamente qualquer função referencialmente transparente. Considere o pseudocódigo a seguir, no qual se pressupõe que as funções sejam valores de primeira classe:
função memoized-call (F é um parâmetro que contém um objeto-função) se F não tiver um vetor values associado, então aloque um vetor associativo chamado values; associe values a F; fim se;
se F.values[arguments] estiver vazio, então F.values[arguments] = F(arguments); fim se;
retorne F.values[arguments]; fim função
Para chamar uma versão automaticamente memoizada de factorial usando a estratégia acima, em vez de chamar factorial diretamente, o código chama memoized-call(factorial)(n). Cada chamada desse tipo verifica primeiro se um vetor de armazenamento foi alocado para guardar os resultados e, caso contrário, associa esse vetor à função. Se não existir uma entrada na posição values[arguments] — em que arguments é usado como chave do vetor associativo —, uma chamada real é feita a factorial com os argumentos fornecidos. Por fim, a entrada do vetor na posição da chave é retornada ao chamador.
A estratégia acima requer o envolvimento explícito em cada chamada de uma função que deva ser memoizada. Nas linguagens que permitem clausuras, a memoização pode ser efetuada implicitamente por meio de uma fábrica de funtores que retorna um objeto-função memoizado e envolvido em um padrão decorador. Em pseudocódigo, isso pode ser expresso da seguinte forma:
função construct-memoized-functor (F é um parâmetro que contém um objeto-função) aloque um objeto-função chamado memoized-version;
defina memoized-version(arguments) como se self não tiver um vetor values associado, então [self é uma referência ao objeto this] aloque um vetor associativo chamado values; associe values a self; fim se;
se self.values[arguments] estiver vazio, então self.values[arguments] = F(arguments); fim se;
retorne self.values[arguments]; fim da definição;
retorne memoized-version; fim função
Em vez de chamar factorial, cria-se um novo objeto-função memfact da seguinte maneira:
memfact = construct-memoized-functor(factorial)
O exemplo acima pressupõe que a função factorial já tenha sido definida antes de ser feita a chamada a construct-memoized-functor. A partir desse ponto, memfact(n) é chamada sempre que se deseja o fatorial de n. Em linguagens como Lua, existem técnicas mais sofisticadas que permitem substituir uma função por uma nova função com o mesmo nome, o que possibilitaria:
factorial = construct-memoized-functor(factorial)
Essencialmente, essas técnicas envolvem associar o objeto-função original ao funtor criado e encaminhar as chamadas à função original memoizada por meio de um alias quando for necessário chamar a função real — evitando uma recursão interminável —, como ilustrado a seguir:
função construct-memoized-functor (F é um parâmetro que contém um objeto-função) aloque um objeto-função chamado memoized-version;
defina memoized-version(arguments) como se self não tiver um vetor values associado, então [self é uma referência a este objeto] aloque um vetor associativo chamado values; associe values a self; aloque um novo objeto-função chamado alias; associe alias a self; [para permitir posteriormente a chamada indireta de F] self.alias = F; fim se;
se self.values[arguments] estiver vazio, então self.values[arguments] = self.alias(arguments); [não é uma chamada direta a F] fim se;
retorne self.values[arguments]; fim da definição;
retorne memoized-version; fim função
(Observação: algumas das etapas mostradas acima podem ser administradas implicitamente pela linguagem de implementação e são apresentadas para fins de ilustração.)
Analisadores sintáticos