Właśnie uruchomiłem Python i nie mam pojęcia, co to jest memoization i jak go używać. Czy mogę też podać uproszczony przykład?
python
memoization
blur959
źródło
źródło
Odpowiedzi:
Zapamiętywanie efektywnie odnosi się do zapamiętywania („zapamiętywanie” → „memorandum” → do zapamiętania) wyników wywołań metod opartych na danych wejściowych metody, a następnie zwracania zapamiętanego wyniku zamiast ponownego obliczania wyniku. Można to traktować jako pamięć podręczną wyników metod. W celu uzyskania dalszych informacji, patrz strona 387, definicja w Wprowadzenie do algorytmów (3e), Cormen i in.
Prostym przykładem obliczania silni przy użyciu zapamiętywania w Pythonie byłoby coś takiego:
Możesz się bardziej skomplikować i zamknąć proces zapamiętywania w klasie:
Następnie:
W Pythonie 2.4 dodano funkcję znaną jako „ dekoratory ”, która pozwala teraz po prostu napisać następujące rzeczy, aby osiągnąć to samo:
Python Decorator Library ma podobny dekorator nazwie
memoized
, który jest nieco bardziej wytrzymałe niżMemoize
klasy przedstawionej tutaj.źródło
factorial_memo
, ponieważfactorial
wnętrzedef factorial
nadal wywołuje stary unememizefactorial
.if k not in factorial_memo:
, który czyta lepiej niżif not k in factorial_memo:
.args
jest krotką.def some_function(*args)
robi krotkę args.Nowością w Python 3.2 jest
functools.lru_cache
. Domyślnie tylko buforuje 128 ostatnio używany nazywa, ale można ustawićmaxsize
, abyNone
wskazać, że skrzynka nie powinny wygasa:Ta funkcja sama w sobie jest bardzo powolna, spróbuj
fib(36)
i będziesz musiał poczekać około dziesięciu sekund.Dodanie
lru_cache
adnotacji gwarantuje, że jeśli funkcja została ostatnio wywołana dla określonej wartości, nie przeliczy tej wartości, ale użyje poprzedniego wyniku w pamięci podręcznej. W takim przypadku prowadzi to do ogromnej poprawy prędkości, a kod nie jest zaśmiecony szczegółami buforowania.źródło
fib
wywołaniu trzeba będzie odwołać się do przypadku podstawowego, zanim będzie możliwe zapamiętanie. Twoje zachowanie jest więc prawie oczekiwane.Pozostałe odpowiedzi dotyczą tego, co jest całkiem nieźle. Nie powtarzam tego. Tylko kilka punktów, które mogą Ci się przydać.
Zazwyczaj zapamiętywanie jest operacją, którą można zastosować do dowolnej funkcji, która oblicza coś (kosztownie) i zwraca wartość. Z tego powodu często jest wdrażany jako dekorator . Wdrożenie jest proste i byłoby coś takiego
lub wyrażone jako dekorator
źródło
Memoizacja zachowuje wyniki kosztownych obliczeń i zwraca wynik z pamięci podręcznej, a nie stale go przelicza.
Oto przykład:
Pełniejszy opis można znaleźć we wpisie w Wikipedii dotyczącym zapamiętywania .
źródło
if input not in self.cache
iself.cache[input]
(has_key
jest przestarzałe, ponieważ ... na początku serii 2.x, jeśli nie 2.0.self.cache(index)
Nigdy nie było poprawne. IIRC)Nie zapomnijmy o wbudowanej
hasattr
funkcji dla tych, którzy chcą ręcznie wytwarzać. W ten sposób możesz przechowywać pamięć podręczną wewnątrz definicji funkcji (w przeciwieństwie do globalnej).źródło
Uważam to za bardzo przydatne
źródło
functools.wraps
.memo
pamięć, aby zwolnić pamięć?Zapamiętywanie polega zasadniczo na zapisywaniu wyników poprzednich operacji wykonanych algorytmami rekurencyjnymi w celu zmniejszenia potrzeby przechodzenia przez drzewo rekurencyjne, jeśli takie samo obliczenie jest wymagane na późniejszym etapie.
patrz http://scriptbucket.wordpress.com/2012/12/11/introduction-to-memoization/
Przykład zapamiętywania Fibonacciego w Pythonie:
źródło
Zapamiętywanie to konwersja funkcji na struktury danych. Zazwyczaj chce się, aby konwersja następowała stopniowo i leniwie (na żądanie danego elementu domeny - lub „klucza”). W leniwych językach funkcjonalnych ta leniwa konwersja może odbywać się automatycznie, a zatem zapamiętywanie może być realizowane bez (wyraźnych) skutków ubocznych.
źródło
Cóż, najpierw powinienem odpowiedzieć na pierwszą część: czym jest zapamiętywanie?
To tylko metoda wymiany pamięci na czas. Pomyśl o tabliczce mnożenia .
Użycie zmiennego obiektu jako wartości domyślnej w Pythonie jest zwykle uważane za złe. Ale jeśli użyjesz go mądrze, może być użyteczne wdrożenie
memoization
.Oto przykład zaadaptowany z http://docs.python.org/2/faq/design.html#why-are-default-values-shared-between-objects
Używając zmiennej
dict
w definicji funkcji, wyniki pośrednie obliczone mogą być buforowane (np. Podczas obliczaniafactorial(10)
po obliczeniufactorial(9)
możemy ponownie wykorzystać wszystkie wyniki pośrednie)źródło
Oto rozwiązanie, które będzie działać z argumentami typu list lub dict bez marudzenia:
Zauważ, że to podejście można oczywiście rozszerzyć na dowolny obiekt, implementując własną funkcję skrótu jako specjalny przypadek w handle_item. Na przykład, aby to podejście działało dla funkcji, która przyjmuje zestaw jako argument wejściowy, możesz dodać do handle_item:
źródło
list
argument[1, 2, 3]
można błędnie uznać za taki sam jak innyset
argument o wartości{1, 2, 3}
. Ponadto zestawy są nieuporządkowane jak słowniki, więc i tak powinny byćsorted()
. Zauważ również, że argument rekurencyjnej struktury danych spowodowałby nieskończoną pętlę.list
siset
są „zmontowane” w to samo i dlatego stają się nierozróżnialne. Przykładowy kod dodawania obsługisets
opisanego w najnowszej aktualizacji nie pozwala uniknąć tego. Można to łatwo zauważyć, osobno przekazując[1,2,3]
i{1,2,3}
jako argument funkcji testowej „zapamiętaj” i sprawdzając, czy jest wywoływana dwukrotnie, tak jak powinna, czy nie.list
si idict
s, ponieważ możliwe jest,list
aby mieć dokładnie to samo, co wynikało z wywołaniamake_tuple(sorted(x.items()))
słownika. Prostym rozwiązaniem dla obu przypadków byłoby uwzględnienietype()
wartości w wygenerowanej krotce. Mogę wymyślić jeszcze prostszy sposób obsługiset
s, ale nie uogólnia.Rozwiązanie, które działa zarówno z argumentami pozycyjnymi, jak i słowami kluczowymi niezależnie od kolejności przekazywania argumentów słów kluczowych (przy użyciu inspect.getargspec ):
Podobne pytanie: Identyfikacja równoważnych wywołań funkcji varargs do zapamiętywania w Pythonie
źródło
źródło
if n not in cache
zamiast tego możesz użyć po prostu . użyciecache.keys
spowoduje zbudowanie niepotrzebnej listy w Pythonie 2Chciałem tylko dodać do już podanych odpowiedzi, biblioteka dekoratorów Pythona ma kilka prostych, ale przydatnych implementacji, które mogą zapamiętywać „typy niewymagalne”, w przeciwieństwie do
functools.lru_cache
.źródło