Quelle est la différence entre la mise en cache et la mémorisation?

114

Je voudrais savoir quelle est la différence réelle entre cachinget memoization.
À mon avis, les deux impliquent d' éviter les appels de fonction répétés pour obtenir des données en les stockant .

Quelle est la différence fondamentale entre les deux?

caching terminology memoization John
la source
Je me demande si vous pourriez dire "la mémorisation est à la mise en cache" comme "le tableau est au tableau clairsemé". En d'autres termes, vous ne stockez que les éléments «à la demande» plutôt que d'énumérer toutes les combinaisons d'entrée possibles.
Sridhar Sarnobat

Réponses:

110

La mémorisation est une forme spécifique de mise en cache qui implique la mise en cache de la valeur de retour d'une fonction en fonction de ses paramètres .

La mise en cache est un terme plus général; par exemple, la mise en cache HTTP est la mise en cache mais pas la mémorisation.

Wikipedia dit :

Bien que liée à la mise en cache, la mémorisation fait référence à un cas spécifique de cette optimisation, la distinguant des formes de mise en cache telles que la mise en mémoire tampon ou le remplacement de page.

SLaks
la source
2
mais vous pouvez toujours entourer la partie où le cache est utilisé avec une fonction et l'a baptisée «mémorisation». bien que la différence soit que vous contrôlez la politique de mise en cache dans votre fonction, alors que la mémorisation est d'ordre supérieur et se produit en dehors de la fonction, je suppose.
nicolas
Pourquoi la mise en cache HTTP n'est-elle pas une mémorisation? qui est également basé sur le paramètre (l'URL de la ressource demandée).
topo Réintégrer Monica
@topomorto: en raison de fonctionnalités telles If-Matchque les expirations. La mémorisation n'a de sens que pour la fonction pure, ce que HTTP est rarement.
SLaks
@nicolas, pas tout à fait, je pense. Je pense que dans la mémorisation, le terme «fonction» est utilisé au sens pur / mathématique. Le téléchargement d'une page Web à partir d'une adresse donnée ne peut pas être considéré comme une fonction, car il peut arriver que la page change.
Alexey
@Alexey, la même remarque ne s'applique-t-elle pas à la mise en cache? toutes ces stratégies reposent sur le même appel de fonction donnant le même résultat, c'est-à-dire sans effet secondaire en amont .
nicolas
47

Comme je les ai vus utilisés, la "mémorisation" consiste à "mettre en cache le résultat d'une fonction déterministe" qui peut être reproduite à tout moment avec la même fonction et les mêmes entrées.

La "mise en cache" comprend essentiellement toute stratégie de mise en mémoire tampon de sortie, que la valeur source soit reproductible ou non à un instant donné. En fait, la mise en cache est également utilisée pour désigner des stratégies de mise en mémoire tampon d' entrée , telles que le cache d'écriture sur un disque ou une mémoire. C'est donc un terme beaucoup plus général.

harpo
la source
Etes-vous sûr que la fonction doit être déterministe?
Gherman
4
@Allemand, oui, la mémorisation dépend du déterminisme. L'exemple classique est un algorithme récursif, comme la séquence de Fibonacci ou factorielle. Au lieu de recalculer jusqu'au cas de base, une fonction mémorisée court-circuiterait en réutilisant les résultats antérieurs pour les valeurs déjà calculées. Cela dépend évidemment de la même entrée produisant toujours la même sortie, qui est la définition du déterminisme. La mise en cache, en revanche, est fréquemment utilisée pour les processus non déterministes (par exemple aléatoires ou horodatés), étant entendu que les résultats peuvent ne pas correspondre à une valeur "actualisée".
harpo
6

Je pense que la mise en cache du terme est généralement utilisée lorsque vous stockez les résultats des opérations d'E / S, ou essentiellement toutes les données qui vous parviennent de l'extérieur (fichiers, réseau, requêtes de base de données). La mémorisation des termes s'applique généralement au stockage des résultats de vos propres calculs, par exemple dans le contexte de la programmation dynamique.

MK.
la source
1

La mémorisation est une forme spéciale de mise en cache du résultat d'une fonction déterministe. Cela signifie que la mise en cache du résultat en dehors de la fonction n'est pas une mémorisation car la fonction devrait muter le cache lors du calcul d'un nouveau résultat (pas déjà dans le cache) afin que ce ne soit plus une fonction (pure). La mémorisation implique généralement de passer le cache comme argument supplémentaire (dans une fonction d'assistance). La mémorisation optimisera les fonctions qui doivent calculer des valeurs plusieurs fois pour un seul accès. La mise en cache optimisera les fonctions appelées plusieurs fois avec les mêmes paramètres. En d'autres termes, la mémorisation optimisera le premier accès si la mise en cache optimisera uniquement les accès récurrents.

Pierre-Yves Saumont
la source
0

Je voudrais ajouter aux autres excellentes réponses que la mémorisation est également connue sous le nom de dépôt . Je pense qu'il est également important de connaître ce terme pour ceux qui apprennent ce que sont la mémorisation et la mise en cache.

CONTRE
la source