Qual é a diferença entre Cache e Memoização?

114

Eu gostaria de saber qual é a diferença real entre cachinge memoization.
A meu ver, ambos envolvem evitar chamadas de função repetidas para obter dados armazenando-os .

Qual é a principal diferença entre os dois?

caching terminology memoization John
fonte
Eu me pergunto se você poderia dizer "memoização é para cache" como "array é para array esparso". Em outras palavras, você apenas armazena coisas "sob demanda", em vez de enumerar todas as combinações de entrada possíveis.
Sridhar Sarnobat

Respostas:

110

Memoização é uma forma específica de armazenamento em cache que envolve o armazenamento em cache do valor de retorno de uma função com base em seus parâmetros .

Cache é um termo mais geral; por exemplo, o cache HTTP é cache, mas não memoization.

Wikipedia diz :

Embora relacionada ao armazenamento em cache, a memoização se refere a um caso específico dessa otimização, distinguindo-a das formas de armazenamento em cache, como armazenamento em buffer ou substituição de página.

SLaks
fonte
2
mas você sempre pode ignorar a parte onde o cache é usado com uma função e batizá-la de 'memoização'. embora a diferença seja que você está no controle da política de cache em sua função, enquanto a memoização é de ordem superior e acontece fora da função, eu acho.
nicolas de
Por que o cache HTTP não é memorizado? que também se baseia no parâmetro (a URL do recurso solicitado).
topo Reintegrar Monica
@topomorto: Por causa de recursos como If-Matche vencimentos. Memoização só faz sentido para funções puras, o que o HTTP raramente é.
SLaks
@nicolas, não exatamente, eu acho. Eu acho que na memoização o termo "função" é usado em sentido puro / matemático. Baixar uma página da web de um determinado endereço não pode ser considerado uma função, pois pode acontecer que a página mude.
Alexey
@Alexey não se aplica a mesma observação ao cache? todas essas estratégias dependem da mesma chamada de função dando o mesmo resultado, também conhecido como nenhum efeito colateral upstream .
Nicolas
47

Como já vi serem usados, "memoização" é "armazenar em cache o resultado de uma função determinística" que pode ser reproduzida a qualquer momento com a mesma função e entradas.

"Cache" inclui basicamente qualquer estratégia de buffer de saída, seja o valor de origem reproduzível ou não em um determinado momento. Na verdade, o cache também é usado para se referir a estratégias de buffer de entrada , como o cache de gravação em um disco ou memória. Portanto, é um termo muito mais geral.

arpão
fonte
Tem certeza de que a função deve ser determinística?
Gherman,
4
@German, sim, a memoização depende do determinismo. O exemplo clássico é um algoritmo recursivo, como a sequência de Fibonacci ou fatorial. Em vez de recalcular todo o caminho até o caso base, uma função memoizada entraria em curto-circuito reutilizando resultados anteriores para valores já calculados. Obviamente, isso depende da mesma entrada sempre produzindo a mesma saída, que é a definição de determinismo. O cache, por outro lado, é frequentemente usado para processos não determinísticos (por exemplo, aleatório ou com carimbo de data / hora), com o entendimento de que os resultados podem não corresponder a um valor "atualizado".
Harpo
6

Acho que o termo cache é geralmente usado quando você armazena resultados de operações de E / S, ou basicamente qualquer dado que chega até você de fora (arquivos, rede, consultas de banco de dados). Memoização de termos geralmente se aplica ao armazenamento de resultados de seus próprios cálculos, por exemplo, no contexto de programação dinâmica.

MK.
fonte
1

Memoização é uma forma especial de armazenar em cache o resultado de uma função determinística. Isso significa que armazenar em cache o resultado fora da função não é memoização porque a função teria que sofrer mutação no cache ao calcular um novo resultado (ainda não no cache) para que não fosse mais uma função (pura). A memorização geralmente implica em passar o cache como um argumento adicional (em uma função auxiliar). A memorização otimizará funções que precisam computar valores várias vezes para um único acesso. O armazenamento em cache otimizará funções que são chamadas várias vezes com os mesmos parâmetros. Em outras palavras, a Memoização otimizará o primeiro acesso se o armazenamento em cache otimizará apenas os acessos recorrentes.

Pierre-Yves Saumont
fonte
0

Gostaria de acrescentar às outras ótimas respostas que a memoização também é conhecida como tabling . Também acho importante conhecer esse termo para quem aprende o que são memoização e cache.

VS
fonte