Dynamic Programming – Memoization
Sumário
Recursões e árvores são técnicas de modelagem e implementação poderosas na construção de algoritmos.
No entanto, também podem ser fontes significativas de ineficiências quando não se observam os padrões que podem fazer tais algoritmos aumentarem de ordem de complexidade.
Esse artigo explicará brevemente o conceito de “dynamic programming” (DP – programação dinâmica) e a técnica de “memoziation” para a otimização de algoritmos. Serão apresentados exemplos práticos e também um do “mundo real”.
Recursão
A técnica de recursão é uma técnica onde se toma um problema de cálculo, não necessariamente matemático, cuja solução propõe “reduzir o problema a uma instância menor do mesmo problema”.
Tais problemas têm uma solução base, de onde a chamada “pilha de recursão” se resolve, devolvendo o resultado parcial para o chamador até que o resultado seja obtido.
Talvez, o exemplo mais comum na literatura de recursão seja o cálculo do fatorial de um número natural (fatorial está para a literatura de recursão como somar dois números está para a literatura de testes unitários). Provavelmente porque a formulação do fatorial seja naturalmente recursiva.
No caso, temos a seguinte definição do fatorial de n:
fatorial(n) := 1, se n == 0
fatorial(n) := n * fatorial(n – 1), se n > 0
E essa definição motiva uma implantação em Java, como:
public static long factorial(long n) {
return n <= 0 ? 1 : n * factorial (n – 1L);
}
A complexidade do cálculo do fatorial é linear – a cada ‘n’ acrescentamos uma nova multiplicação.
Neste momento, você pode estar pensando que poderia dar uma solução não-recursiva para o fatorial. Verdade, o algoritmo iterativo é fácil neste caso. Mas você também pode estar trabalhando com uma linguagem com construções naturalmente recursivas, como o LISP. Então, vamos manter a recursão nos raciocínios a seguir.
Os números de Fibonacci (e o início dos problemas dos algoritmos triviais)
Outra construção recursiva famosa é a regra de formação dos números de Fibonacci:
fibonacci(n) := 0, se n == 0
fibonacci(n) := 1, se n == 1
fibonacci(n) := fibonacci(n-1) + fibonacci(n-2), se n >= 2
Abaixo temos uma tabela com os primeiros números de Fibonacci:
| N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| FIB(N) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
Parece simples de construir, não é mesmo? Temos duas chamadas recursivas nos números de Fibonacci ao invés de uma, no caso do fatorial. Um possível código em Java seria:
public static long fibonacci(int n) {
if (n == 0) return 0L;
if (n == 1) return 1L;
return fibonacci(n – 2) + fibonacci(n – 1);
}
Mas observe o que acontece ao calcular números de Fibonacci um pouco maiores:
simple fibonacci(7) = 13 took 0 ms
simple fibonacci(13) = 233 took 1 ms
simple fibonacci(25) = 75025 took 1 ms
simple fibonacci(36) = 14930352 took 76 ms
simple fibonacci(43) = 433494437 took 1994 ms
simple fibonacci(45) = 1134903170 took 5110 ms
simple fibonacci(47) = 2971215073 took 13305 ms
Para calcular o 43º número de Fibonacci, o algoritmo leva quase dois segundos. Para calcular o 47º, mais de 13 segundos! Convenhamos, 47 não é um índice muito grande. E se quiséssemos calcular o centésimo? Certamente o algoritmo acima (não o teórico; a implementação) não implementa a melhor abordagem para solucionar o problema. O usuário vai tomar um café antes de ter o resultado.
Mas o que está acontecendo? Vamos tentar visualizar um “teste de mesa” para o algoritmo, no caso n == 6:
Cada parcela do número de Fibonacci alvo precisa de duas novas “sub-parcelas”, de forma que o número de cálculos necessários cresce de um fator de 2 a cada nível da árvore, ou seja, aumenta exponencialmente! Imagine a figura acima para o sétimo número de Fibonacci, ou o 47º.
Além disso, observe que existem recálculos. Por exemplo, para calcular o sexto número de Fibonacci, o segundo número de Fibonacci é calculado quatro vezes. Isso é evidenciado pelas subárvores abaixo dos nós destacados. Observem também as repetições dos nós “3(2)”.
São justamente essas duas características, a recursão e o recálculo, que podem ser atacados pelas técnicas de “dynamic programming”.
Dynamic Programming (DP)
As técnicas de DP também consistem em reduzir os problemas a instâncias menores do mesmo problema. No entanto, os cálculos das instâncias menores são preservados e reutilizados a cada vez que se precisa delas para os cálculos das instâncias-alvo.
De maneira geral, portanto, as técnicas de DP procuram otimizar o custo de tempo, com o sacrifício, normalmente muito menor, do custo de espaço em memória.
Não existe apenas uma técnica de DP, mas podemos agrupá-las em dois grandes grupos:
- Técnicas “Top-Down” ou “Lazy”
Nas técnicas “top-down”, mantemos o “raciocínio” recursivo (embora a implementação possa ser iterativa); construímos e preservamos o cálculo dependente apenas quando precisamos deles.
- Técnicas “Bottom-Up” ou “Greedy”
Nas técnicas “bottom-up”, o raciocínio é interativo, as instâncias menores são construídas e preservadas de forma crescente e antes, até chegar na instância alvo.
Memoization
A técnica de “memoization” talvez seja a mais simples das técnicas top-down, e, provavelmente, a mais fácil de implementar. A técnica consiste em criar uma “memória”, ou uma “tabela de lookup” ou ainda um “cache” que preserva os cálculos anteriores, “destruindo” os ramos da árvore que motivariam os recálculos e, portanto, reduzindo a complexidade exponencial do algoritmo.
Uma possível implementação do algoritmo para os números de Fibonacci em Java:
public class MemoizedFibonacci {
public static long fibonacci(int n) {
final HashMap<Integer, Long> lookupTable = new HashMap<Integer,Long>();
return fibonacci(n, lookupTable);
}
private static long fibonacci(int n, Map<Integer,Long> lookupTable) {
if (lookupTable.containsKey(n)) return lookupTable.get(n);
if (n == 0) return 0L;
if (n == 1) return 1L;
long result = fibonacci(n – 2, lookupTable) + fibonacci(n – 1, lookupTable);
lookupTable.put(n, result);
return result;
}
}
No algoritmo acima, a lookup table é implementada como um mapa que leva um índice ao número de Fibonacci correspondente.
Cada vez que um número de uma instância menor é calculado, ele é acrescentado na lookup table. Por outro lado, quando o cálculo parcial começa, a primeira providência é verificar se a lookup table já contém aquele índice, de forma que isso indica que o cálculo já foi realizado antes. Assim o valor na tabela é retornado sem a recursão.
Observe os resultados dessa versão:
Running br.nom.dailton.fibonacci.MemoizedFibonacciTest
memoized test 7 = 13 : 0 ms
memoized test 13 = 233 : 0 ms
memoized test 25 = 75025 : 0 ms
memoized test 36 = 14930352 : 0 ms
memoized test 43 = 433494437 : 0 ms
memoized test 45 = 1134903170 : 0 ms
memoized test 47 = 2971215073 : 0 ms
memoized test 50 = 12586269025 : 0 ms
Tests run: 8, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 0.086 sec
Os tempos praticamente não crescem (na verdade o algoritmo se tornou linear, mas está tão rápido que não chegou na casa dos milissegundos ainda). E reduzir algoritmos exponenciais para lineares é um ganho absurdo!
Um exemplo do mundo real – o problema do caixa eletrônico
Suponha que você tenha uma lista de valores de cédulas que estarão no “estoque” de um caixa eletrônico. Por exemplo, notas de 20, 50 e 100 reais. Você quer saber se dado um valor a sacar, digamos, 140, se é possível sacá-lo do caixa eletrônico e voltar uma combinação de cédulas que some tal valor, ou null/nil se não houver.
O mesmo valor de cédula pode ser usado mais de uma vez. Por exemplo, podemos sacar 150 reais com 3 cédulas de 50 reais (ou “1×50 + 1×100” ou “5×20 + 1×50”). Para efeito de raciocínio, podemos considerar que o estoque de cada cédula é “infinito”. Não é uma hipótese tão fora da realidade, podemos assumir que o estoque é grande o suficiente para não se esgotar ao longo do dia e toda noite há reposição, ou que uma validação prévia desse estoque acontece antes de montar a lista de cédulas.
A ideia aqui é pensar com a recursão e verificar como resolver este problema.
Em primeiro lugar, é razoável pensar que, no exemplo acima, se conseguimos sacar 120 reais, então conseguimos sacar 140, porque o estoque tem notas de 20 reais.
Por outro lado, não é possível sacar 10 reais, porque todas as cédulas são maiores que 10.
Um possível teste de mesa, então:
O algoritmo, para cada cédula menor que o valor de referência, cria um ramo na árvore e tenta resolver a instância menor com a diferença entre o valor de referência e aquela cédula. Exemplo, para os 140, tomando uma cédula de 20 gera-se o mesmo subproblema para 140-20=120.
Toda vez que o algoritmo chega num nó verde (zero), temos uma solução válida. No entanto, toda vez que chega num nó vermelho (valor negativo), chegamos num beco sem saída.
Vamos ver um outro exemplo: suponha que queremos sacar 50 reais, e temos cédulas de 20 e 40 reais:
Observe que não é possível sacar 50 reais com cédulas de 20 e 40.
Vamos implementar o algoritmo simples e observar a saída para alguns valores:
public class SimpleATM {
public static List<Integer> combineSum(int targetSum, int[] bills) {
if (targetSum == 0) return new LinkedList<>();
if (targetSum < 0) return null;
for (int i = 0, n = bills.length; i < n; i++) {
int remainder = targetSum – bills[i]; //remainder pode ser negativo
List<Integer> remainderResult = combineSum(remainder, bills);
if (remainderResult != null) {
List<Integer> currentResult = new LinkedList<>(remainderResult); //esta operacao custa
currentResult.add(bills[i]);
return currentResult;
}
}
return null;
}
}
Salvo os casos-base, o algoritmo itera os valores das cédulas (bills) e testa se há solução para o problema com o valor targetSum-bills[i] e, se tiver, também terá solução para o valor targetSum. Quanto maior o número de cédulas diferentes, mais ramos terá a árvore e mais lento será o algoritmo. E quanto maior o valor a sacar, também.
Seguem algumas saídas:
- 7, [2,3] -> [3,2,2]
- 7, [5,3,4,7] -> [4,3]
- 7, [2,4] -> null
- 300, [7,14] -> null //LEVOU CERCA DE 4 SEGUNDOS
Mas por que ele está tão lento? Estamos no mesmo caso do exemplo ruim do cálculo dos números de Fibonacci. O algoritmo do saque está exponencial. E repare, no exemplo da árvore de saque dos 140 reais, a quantidade de vezes que temos nós com os valores 40 ou 30.
Podemos então usar a mesma estratégia, usando uma lookup table para valores já calculados. Segue uma implementação em Java:
public class MemoizedATM {
public static List<Integer> combineSum(int targetSum, int[] bills) {
return combineSum(targetSum, bills, new HashMap<>());
}
public static List<Integer> combineSum(int targetSum, int[] bills, Map<Integer, List<Integer>> lookupTable) {
if (lookupTable.containsKey(targetSum)) return lookupTable.get(targetSum);
if (targetSum == 0) return new LinkedList<>();
if (targetSum < 0) return null;
for (int i = 0, n = bills.length; i < n; i++) {
int remainder = targetSum – bills[i]; //remainder pode ser negativo
List<Integer> remainderResult = combineSum(remainder, bills, lookupTable);
if (remainderResult != null) {
List<Integer> currentResult = new LinkedList<>(remainderResult); //esta operacao custa
currentResult.add(bills[i]);
lookupTable.put(targetSum, currentResult);
return currentResult;
}
}
lookupTable.put(targetSum, null);
return null;
}
}
Algumas variações:
- Retornar a combinação de cédulas que podem compor o valor a sacar, utilizando o menor número de cédulas possível. A alteração necessária no algoritmo acima é bem pequena.
- Considerar o estoque de cédulas finito. Você pode considerar que “bills”, ao invés de ser um array, é um Map<Integer,Integer> que leva um valor de cédula em sua quantidade, no início do algoritmo. Observe nessa construção que o mapa na chamada recursiva não será igual ao mapa na chamada original e isso pode significar bastante uso de memória.
Notas finais
A técnica de DP/memoization é fundamental para a otimização de algoritmos e deve ser de domínio de todos os desenvolvedores.
É importante estabelecer que não necessariamente uma lookup table precisa ter unidimensional. Conforme as características do problema, podemos ter que trabalhar com tabelas multidimensionais. Veja o exemplo do “grid traveler” no vídeo do freeCodeCamp.org abaixo. Nesse mesmo vídeo temos outra técnica de dynamic programming, o “tabulation”, que não exploraremos neste texto. Vale assistir.
Referências
Links Wikipedia
https://en.wikipedia.org/wiki/Dynamic_programming
https://en.wikipedia.org/wiki/Memoization
YouTube — freeCodeCamp.org
Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges
