Desmistificando a Memoização

O que é Memoização e por que ela é utilizada?

Quando falamos em aumento de performance, um dos conceitos mais utilizados é a memoização, um termo criado em 1968 por Donald Michie, sendo derivado do latim “memorandum”, carregando o significado de “transformar o resultado de uma função em algo para ser lembrado”.

No mundo da computação, sempre buscamos por aumento de performance e simplificação no código, de forma eficaz e eficiente. Um dos conceitos mais utilizados para atingir esse objetivo, é o cache, que basicamente armazena dados que são derivados de serviços executados anteriormente, para que sejam utilizados futuramente, de forma que não seja necessário o reprocessamento para a obtenção do resultado já conhecido.

A recuperação dos dados é realizada através da leitura do cache, que funciona como um Local Storage, que é mais performático do que reprocessar o serviço ou ler de uma base de dados.

A memoização é uma das técnicas de otimização de performance, utilizada para acelerar programas, armazenando resultados de funções complexas, retornando o resultado em cache. Em linhas gerais, por mais que seja um tipo específico de cache, a memoização se refere a um caso especifico dessa otimização, e tem suas diferenças com relação a outros tipos de cache mais conhecidos como por exemplo, o buffering.

Onde e como utilizar a Memoização?

Pode-se utilizar a memoização em vários casos, principalmente em problemas que envolvem subproblemas sobrepostos, como por exemplo em casos que utilizam a recursividade, busca binária, árvore binária, dentre outros.

Fatorial com Memoização

Neste primeiro exemplo, implementaremos a resolução do fatorial de um número específico, que utiliza a seguinte fórmula:

n! = n * (n – 1)

Segue abaixo a implementação em Java de um método, utilizando recursividade para encontrar o fatorial:

Calculando o fatorial de 2, 3, 9 e 5, respectivamente, temos o seguinte processamento:

Se notarmos na imagem acima, enquanto calculamos o fatorial de 9, estamos calculando o fatorial de 2, 3 e 5, portanto, se armazenarmos o resultado de cada processamento individual na primeira vez, podemos retornar o fatorial de qualquer número já conhecido, necessário apenas em 0(1).

Portanto, é seguro dizer que, para encontrar fatorial de números K, a complexidade de tempo necessária será O(N*K):

O(N) para encontrar o fatorial de um número específico;
O(K) para chamar o método fatorial() K vezes diferentes;

Utilizando a memoização, excluímos parte do processamento que já é conhecido pelo armazenamento local, retirando a complexidade e aumentando a performance do retorno do método.

Portanto, a complexidade de tempo para encontrar números fatoriais usando a memorização será O(N):

O(N) para encontrar o fatorial da maior entrada;
O(1) para imprimir o fatorial de cada entrada;

Progressão Aritmética com Memoização

Neste exemplo, implementaremos a resolução de uma sequência matemática complexa sem e com memoização, que é definida da seguinte forma:

n =0 =>a(0) = 0
n =1 =>a(1) = 1
n =2 =>a(2) = 1
n>2 => a(n) = a(n-3) + a(n-2)

Exemplo dos primeiros valores da sequência: 0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 […].

Segue abaixo a implementação em Java, utilizando recursividade para encontrar o valor da progressão aritmética, com base no index passado:

Primeiramente, realizamos a contingência para valores já conhecidos:

n =0 =>a(0) = 0
n =1 =>a(1) = 1
n =2 =>a(2) = 1

Depois disso, utilizamos recursividade para definir o resultado do index da progressão aritmética, seguindo a fórmula inicial.

Quando utilizamos a recursividade sem memoização, pode-se tornar um processo muito custoso e demorado, de forma que seja necessário reprocessar o método com valores já conhecidos, até que a solução seja definida.

Para provar este ponto de vista, fiz uma contagem de quantas vezes a recursividade é executada, e do tempo de processamento, para o index 50 da sequência. Segue abaixo o resultado:

Resultado: 696081
CALLED [1844221] TIMES - Processing time: 0 s 045 ms 45402700 ns

*O tempo de processamento pode variar conforme o equipamento utilizado.

Segue abaixo a implementação em Java, utilizando recursividade COM memoização para encontrar o valor da progressão aritmética, com base no index passado:

A primeira e grande diferença, foi a necessidade de criar um CacheMemoizationManager, responsável pelo gerenciamento do cache memoizado. Para isso, utilizei um HashMap, que armazena o index e o valor que foram processados anteriormente.

Podemos perceber que temos alguns métodos acessórios para conseguirmos implementar a memoização, sendo eles o método get(), para recuperar um valor com base no index passado, clearCache() para limpar completamente o cache e startup(), que nesse caso foi utilizado para popular os valores já conhecidos no mapa, no momento de sua inicialização.

IMPORTANTE: Como o projeto foi feito em Spring Boot, utilizei a anotação @PostConstruct para que não tenhamos conflitos com outros Beans no Lifecycle do Spring. Caso o Spring não fosse utilizado, os valores poderiam ser introduzidos via construtor, ou até mesmo no momento de sua instância.

Com o CacheMemoizationManager devidamente injetado (no caso do Spring, utilizamos a anotação @Autowired), podemos perceber que primeiramente, realizamos uma consulta no HashMap para recuperar o valor com base no index passado. Se o valor for conhecido pelo sistema, irá apenas retornar o número recuperado do HashMap, se não, o valor seqNumber será nulo, então entrará na estrutura de decisão, executando a recursividade e salvando o resultado no HashMap posteriormente.

Segue abaixo a quantidade de vezes que essa recursividade foi chamada, além do tempo de processamento:

Resultado: 696081
CALLED [95] TIMES - Processing time: 0 s 010 ms 10673700 ns

*O tempo de processamento pode variar conforme o equipamento utilizado.

Conclusão

Utilizando a memoização, temos um resultado muito mais satisfatório e surpreendente, reduzindo a quantidade que a recursividade foi chamada em 20.000x e tornando o tempo de processamento 5x mais rápido.

Nesse caso, utilizamos a técnica conhecida como Top-Down, que consiste na aplicação da memoização utilizando recursão e cache. Diferente da técnica Bottom-Up, que utiliza tabulação, porém sem recursão. Segue comparação entre elas:

Existem tipos específicos de memoização que não foram abordados nesse artigo, caso tenha interesse, acesse: https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/

Segue abaixo repositório no GitHub do código utilizado no segundo exemplo:
https://github.com/wienerdev/alticci-sequence

Além disso, implementei um front-end e efetuei o deploy da aplicação, caso você tenha interesse, acesse:
https://github.com/wienerdev/alticci-sequence-angular
https://wienerdev.github.io/alticci-sequence-angular/

Referências

https://www.geeksforgeeks.org/memoization-1d-2d-and-3d/
https://www.geeksforgeeks.org/program-for-factorial-of-a-number/
https://www.geeksforgeeks.org/what-is-memoization-a-complete-tutorial/
https://en.wikipedia.org/wiki/Memoization