Jaka jest różnica między buforowaniem a zapamiętywaniem?

114

Chciałbym wiedzieć, jaka jest rzeczywista różnica między cachingi memoization.
Jak widzę, oba obejmują unikanie powtarzających się wywołań funkcji w celu uzyskania danych poprzez ich przechowywanie .

Jaka jest główna różnica między nimi?

caching terminology memoization Jan
źródło
Zastanawiam się, czy można powiedzieć, że „zapamiętywanie jest buforowaniem”, ponieważ „tablica jest tablicą rzadką”. Innymi słowy, przechowujesz rzeczy tylko „na żądanie”, zamiast wyliczać każdą możliwą kombinację danych wejściowych.
Sridhar Sarnobat

Odpowiedzi:

110

Memoizacja to specyficzna forma buforowania, która obejmuje buforowanie wartości zwracanej funkcji na podstawie jej parametrów .

Buforowanie jest terminem bardziej ogólnym; na przykład buforowanie HTTP to buforowanie, ale nie zapamiętywanie.

Wikipedia mówi :

Chociaż jest to związane z buforowaniem, zapamiętywanie odnosi się do konkretnego przypadku tej optymalizacji, odróżniając ją od form buforowania, takich jak buforowanie lub zastępowanie stron.

SLaks
źródło
2
ale zawsze możesz ukryć część, w której pamięć podręczna jest używana z funkcją i nazwać ją „zapamiętywaniem”. chociaż różnica polega na tym, że kontrolujesz zasady buforowania w swojej funkcji, podczas gdy zapamiętywanie jest wyższego rzędu i wydaje mi się, że odbywa się poza funkcją.
nicolas
Dlaczego buforowanie HTTP nie jest zapamiętywane? to również jest oparte na parametrze (adresie URL żądanego zasobu).
topo Przywróć Monikę
@topomorto: Ze względu na funkcje takie jak If-Matchi wygaśnięcia. Zapamiętywanie ma sens tylko dla czystej funkcji, co rzadko jest HTTP.
SLaks
@nicolas, chyba niezupełnie. Myślę, że w zapamiętywaniu termin „funkcja” jest używany w sensie czysto / matematycznym. Ściąganie strony internetowej z podanego adresu nie może być traktowane jako funkcja, ponieważ może się zdarzyć, że strona się zmieni.
Alexey
@Alexey czy ta sama uwaga nie dotyczy buforowania? wszystkie te strategie opierają się na tym samym wywołaniu funkcji, dającym ten sam wynik, czyli brak efektu ubocznego w górę .
nicolas
47

Jak widziałem ich użycie, „zapamiętywanie” to „buforowanie wyniku funkcji deterministycznej”, która może być odtworzona w dowolnym momencie, mając tę ​​samą funkcję i dane wejściowe.

„Buforowanie” obejmuje w zasadzie każdą strategię buforowania wyjścia, niezależnie od tego, czy wartość źródłowa jest odtwarzalna w danym czasie, czy nie. W rzeczywistości buforowanie jest również używane w odniesieniu do strategii buforowania danych wejściowych , takich jak pamięć podręczna zapisu na dysku lub w pamięci. Jest to więc termin znacznie bardziej ogólny.

harpo
źródło
Czy na pewno funkcja musi być deterministyczna?
Gherman,
4
@Niemiecki, tak, zapamiętywanie zależy od determinizmu. Klasycznym przykładem jest algorytm rekurencyjny, taki jak ciąg Fibonacciego lub silnia. Zamiast ponownego obliczania aż do przypadku podstawowego, zapamiętana funkcja spowodowałaby zwarcie przez ponowne użycie wcześniejszych wyników dla wartości, które zostały już obliczone. To oczywiście zależy od tego samego wkładu, który zawsze daje ten sam wynik, co jest definicją determinizmu. Z drugiej strony buforowanie jest często używane w przypadku procesów niedeterministycznych (np. Losowych lub ze znacznikiem czasu), przy założeniu, że wyniki mogą nie odpowiadać „odświeżonej” wartości.
harpo
6

Myślę, że termin buforowanie jest zwykle używany, gdy przechowujesz wyniki operacji IO lub w zasadzie wszelkie dane przychodzące z zewnątrz (pliki, sieć, zapytania bazy danych). Zapamiętywanie terminów zwykle dotyczy przechowywania wyników własnych obliczeń, na przykład w kontekście programowania dynamicznego.

MK.
źródło
1

Memoizacja jest specjalną formą buforowania wyniku funkcji deterministycznej. Oznacza to, że buforowanie wyniku poza funkcją nie jest zapamiętywaniem, ponieważ funkcja musiałaby zmutować pamięć podręczną podczas obliczania nowego wyniku (nie znajdującego się już w pamięci podręcznej), więc nie byłaby już (czystą) funkcją. Zapamiętywanie generalnie oznacza przekazanie pamięci podręcznej jako dodatkowego argumentu (w funkcji pomocniczej). Zapamiętywanie zoptymalizuje funkcje, które muszą obliczać wartości kilka razy dla pojedynczego dostępu. Buforowanie zoptymalizuje funkcje, które są wywoływane kilka razy z tymi samymi parametrami. Innymi słowy, Memoization zoptymalizuje pierwszy dostęp, niezależnie od tego, czy buforowanie będzie optymalizować tylko powtarzające się dostępy.

Pierre-Yves Saumont
źródło
0

Chciałbym dodać do innych wielkich odpowiedzi, które memoization jest również znany jako składania . Myślę, że ważne jest również, aby znać ten termin dla tych, którzy uczą się, czym jest zapamiętywanie i buforowanie.

VS
źródło