Memoização

A memoização armazena o resultado de uma função para uma entrada e o reutiliza quando a mesma entrada reaparece. Ela é mais confiável quando a função é referencialmente transparente: entradas iguais implicam resultados iguais, e a avaliação não possui efeitos colaterais necessários.

Da recursão exponencial ao trabalho linear

A recursão ingênua de Fibonacci recalcula os mesmos subproblemas. A versão memoizada avalia cada argumento não negativo no máximo uma vez:

static BigInteger fibonacci(int n, Map<Integer, BigInteger> memo) {
    if (n < 0) throw new IllegalArgumentException("n must be non-negative");
    BigInteger known = memo.get(n);
    if (known != null) return known;

    BigInteger result = n < 2
            ? BigInteger.valueOf(n)
            : fibonacci(n - 1, memo).add(fibonacci(n - 2, memo));
    memo.put(n, result);
    return result;
}

Supondo acesso ao mapa em tempo esperado constante, existem n + 1 estados, trabalho não recursivo constante por estado, Θ(n) resultados armazenados e profundidade Θ(n) na pilha de chamadas. A tabulação mantém o mesmo limite de tempo e pode reduzir a Θ(1) o espaço auxiliar dessa recorrência.

A chave faz parte da correção

A chave deve conter toda entrada capaz de afetar o resultado, inclusive configuração, localidade, permissões ou modo do algoritmo relevantes. Chaves mutáveis são inseguras quando sua igualdade ou código hash muda após a inserção. Entradas de ponto flutuante e grafos de objetos muito grandes também exigem uma política explícita de equivalência.

Não memoize uma operação apenas porque sua assinatura se parece com uma função. Tempo, valores aleatórios, estado do banco de dados, variáveis de ambiente e chamadas externas são entradas ocultas, salvo quando capturados explicitamente.

Ciclo de vida, limites e concorrência

Uma tabela por invocação possui um ciclo de vida natural e costuma bastar para programação dinâmica. Uma tabela que abrange todo o processo precisa de uma política de remoção ou alcançabilidade; caso contrário, a memoização se torna um vazamento de memória. Sob concorrência, um mapa thread-safe protege sua estrutura, mas não necessariamente evita computação duplicada. A coordenação single-flight pode ser útil somente quando o trabalho duplicado for caro e a limpeza após falhas estiver bem definida.

Memoizar falhas pode impedir a recuperação. Decida se uma exceção, um resultado vazio ou um timeout pode ser reutilizado e por quanto tempo.

Memoização não é cache geral

A memoização preserva o resultado de uma função para entradas iguais. Um cache da aplicação normalmente espelha dados cuja fonte pode mudar e, portanto, precisa de semânticas de atualidade, invalidação, capacidade e indisponibilidade. As duas implementações podem usar mapas, mas seus contratos de correção são diferentes.

Lista de verificação

• compare os resultados com um oráculo sem memoização em entradas pequenas;
• conte as avaliações de estados para confirmar a reutilização;
• teste entradas vazias, básicas, máximas e inválidas;
• teste as premissas de igualdade e mutação das chaves;
• meça a memória retida, além do tempo decorrido.