Was ist der Unterschied zwischen Caching und Memoization?

114

Ich würde gerne wissen, was der eigentliche Unterschied zwischen cachingund memoizationist.
Aus meiner Sicht müssen beide wiederholte Funktionsaufrufe vermeiden, um Daten durch Speichern abzurufen .

Was ist der Hauptunterschied zwischen den beiden?

caching terminology memoization John
quelle
Ich frage mich, ob Sie sagen könnten "Memoisierung ist zu Caching" wie "Array ist zu dünn Array". Mit anderen Worten, Sie speichern Dinge nur "on demand", anstatt jede mögliche Eingabekombination aufzulisten.
Sridhar Sarnobat

Antworten:

110

Memoization ist eine spezielle Form des Caching, bei der der Rückgabewert einer Funktion basierend auf ihren Parametern zwischengespeichert wird .

Caching ist ein allgemeinerer Begriff. Beispielsweise ist HTTP-Caching Caching, aber keine Memoisierung.

Wikipedia sagt :

Die Memoisierung bezieht sich zwar auf das Caching, bezieht sich jedoch auf einen bestimmten Fall dieser Optimierung und unterscheidet sie von Caching-Formen wie dem Puffern oder dem Ersetzen von Seiten.

SLaks
quelle
2
Sie können jedoch den Teil, in dem der Cache verwendet wird, immer mit einer Funktion überschreiben und ihn als "Memoization" bezeichnen. Obwohl der Unterschied darin besteht, dass Sie die Kontrolle über die Caching-Richtlinie in Ihrer Funktion haben, während das Auswendiglernen eine höhere Ordnung hat und außerhalb der Funktion stattfindet, denke ich.
Nicolas
Warum wird HTTP-Caching nicht gespeichert? Dies basiert auch auf dem Parameter (der URL der angeforderten Ressource).
Topo Reinstate Monica
@topomorto: Aufgrund von Funktionen wie If-Matchund Ablaufzeiten . Das Auswendiglernen macht nur für die reine Funktion Sinn, was HTTP selten ist.
SLaks
@nicolas, nicht ganz, denke ich. Ich denke, dass in der Memoisierung der Begriff "Funktion" im rein / mathematischen Sinne verwendet wird. Das Herunterladen einer Webseite von einer bestimmten Adresse kann nicht als Funktion angesehen werden, da sich die Seite möglicherweise ändert.
Alexey
@Alexey gilt nicht die gleiche Bemerkung für das Caching? Alle diese Strategien basieren auf demselben Funktionsaufruf, der dasselbe Ergebnis liefert, auch bekannt als kein Upstream- Nebeneffekt.
Nicolas
47

Wie ich gesehen habe, bedeutet "Memoisierung" "das Ergebnis einer deterministischen Funktion zwischenspeichern", die jederzeit mit derselben Funktion und denselben Eingaben reproduziert werden kann.

"Caching" umfasst grundsätzlich jede Ausgabepufferstrategie, unabhängig davon, ob der Quellwert zu einem bestimmten Zeitpunkt reproduzierbar ist oder nicht. Tatsächlich wird Caching auch verwendet, um auf Eingabepufferstrategien zu verweisen , wie z. B. den Schreibcache auf einer Festplatte oder einem Speicher. Es ist also ein viel allgemeinerer Begriff.

Harpo
quelle
Sind Sie sicher, dass die Funktion deterministisch sein muss?
Gherman
4
@Deutsch, ja, das Auswendiglernen hängt vom Determinismus ab. Das klassische Beispiel ist ein rekursiver Algorithmus wie die Fibonacci-Sequenz oder die Fakultät. Anstatt bis zum Basisfall neu zu berechnen, würde eine gespeicherte Funktion kurzschließen, indem frühere Ergebnisse für bereits berechnete Werte wiederverwendet werden. Dies hängt offensichtlich davon ab, dass dieselbe Eingabe immer dieselbe Ausgabe liefert, was die Definition von Determinismus ist. Caching wird andererseits häufig für nicht deterministische (z. B. zufällige oder zeitgestempelte) Prozesse verwendet, mit dem Verständnis, dass die Ergebnisse möglicherweise nicht mit einem "aktualisierten" Wert übereinstimmen.
Harpo
6

Ich denke, der Begriff Caching wird normalerweise verwendet, wenn Sie Ergebnisse von E / A-Vorgängen oder im Grunde alle Daten speichern, die von außen zu Ihnen kommen (Dateien, Netzwerk, Datenbankabfragen). Term Memoization bezieht sich normalerweise auf das Speichern von Ergebnissen Ihrer eigenen Berechnungen, beispielsweise im Rahmen der dynamischen Programmierung.

MK.
quelle
1

Das Auswendiglernen ist eine spezielle Form des Zwischenspeicherns des Ergebnisses einer deterministischen Funktion. Dies bedeutet, dass das Zwischenspeichern des Ergebnisses außerhalb der Funktion keine Memoisierung ist, da die Funktion den Cache beim Berechnen eines neuen Ergebnisses (nicht bereits im Cache) mutieren müsste, sodass es keine (reine) Funktion mehr wäre. Das Auswendiglernen impliziert im Allgemeinen das Übergeben des Caches als zusätzliches Argument (in einer Hilfsfunktion). Durch das Speichern von Funktionen werden Funktionen optimiert, bei denen Werte für einen einzelnen Zugriff mehrmals berechnet werden müssen. Durch das Caching werden Funktionen optimiert, die mehrmals mit denselben Parametern aufgerufen werden. Mit anderen Worten, Memoization optimiert den ersten Zugriff, unabhängig davon, ob durch das Caching nur wiederkehrende Zugriffe optimiert werden.

Pierre-Yves Saumont
quelle
0

Ich möchte zu den anderen großartigen Antworten hinzufügen, dass das Auswendiglernen auch als Tabling bezeichnet wird . Ich denke, es ist auch wichtig, diesen Begriff für diejenigen zu kennen, die lernen, was Memoisierung und Caching sind.

Vadim S.
quelle