lru_cache: memoização sem esforço

O que é memoização

Algumas funções são caras de calcular e acabam sendo chamadas várias vezes com os mesmos argumentos. Recalcular tudo de novo é desperdício. A memoização resolve isso guardando os resultados: na primeira chamada com certos argumentos, a função calcula e guarda; nas próximas com os mesmos argumentos, ela devolve o valor guardado na hora. É uma troca de memória por tempo. Só funciona bem com funções puras, porque o resultado precisa depender apenas dos argumentos para o cache ser confiável.

Fazer isso à mão dá trabalho: você precisaria criar um dicionário, checar se o argumento já está lá, guardar o resultado, e ainda cuidar do tamanho do cache. O functools oferece tudo pronto no decorador lru_cache. Você o coloca acima da função e ela passa a memoizar sozinha, sem mudar o corpo. O nome LRU vem de least recently used: quando o cache atinge o limite, ele joga fora os resultados usados há mais tempo, mantendo os mais recentes.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(30))   # 832040
print(fib(50))   # 12586269025  (instantaneo com cache)

# Sem o cache, fib(50) recalcularia bilhoes de vezes os mesmos valores.

@lru_cache memoiza fib: cada valor é calculado uma vez, tornando a recursão viável.

O ganho dramático em recursões

O exemplo do Fibonacci recursivo mostra o poder da memoização. Sem cache, calcular o termo 50 é inviável na prática, porque a função recalcula os mesmos valores um número gigantesco de vezes, ramificando a cada chamada. Com o lru_cache, cada termo é calculado uma única vez e reaproveitado, e a mesma função que travava passa a responder instantaneamente. A lógica não mudou; só o decorador foi adicionado. Esse é o tipo de ganho que faz a memoização valer tanto a pena em cálculos repetitivos e caros.

O parâmetro maxsize controla o tamanho do cache. Passar None deixa o cache crescer sem limite, o que é ótimo para uma recursão finita como o Fibonacci, mas perigoso num programa longo com muitos argumentos diferentes, porque a memória só cresce. Definir um limite, por exemplo alguns milhares de entradas, faz o cache descartar os resultados mais antigos quando enche. A escolha depende do padrão de uso: cache pequeno e limitado para uso contínuo, cache livre para cálculos pontuais e delimitados.

Quando o cache atrapalha

A memoização não é gratuita nem universal. Ela só é segura com funções puras: se o resultado depende de algo externo que muda, como a hora atual ou um arquivo, o cache devolveria um valor velho e errado. Ela consome memória, que cresce com a variedade de argumentos, então um cache sem limite pode virar um vazamento. E ela exige que os argumentos sejam hasheáveis, ou seja, imutáveis o bastante para virar chave: listas, por exemplo, não servem de argumento de uma função memoizada. Fora desses casos, é uma das otimizações mais fáceis que existem.

Fechando o functools, o lru_cache é o exemplo perfeito de como o estilo funcional e o desempenho se encontram. Ele só funciona porque a função é pura, o que reforça o valor da pureza que abriu o módulo. E ele resolve um problema real com uma linha. A próxima aula muda de assunto dentro do mesmo espírito e apresenta o itertools, uma caixa de ferramentas de iteradores que produz sequências, combina e fatia dados de forma preguiçosa e eficiente.