Czy ktoś może wyjaśnić koncepcję zapamiętywania Haskella?

12

(uwaga: zadaję to pytanie, ponieważ dotyczy ono mechaniki pojęciowej, a nie problemu z kodowaniem)

Pracowałem nad małym programem, który wykorzystywał sekwencję liczb Fibonacciego w swojej równowadze, ale zauważyłem, że jeśli przekroczyłem pewną liczbę, robi się to boleśnie powolne, przeglądając trochę, natknąłem się na technikę w Haskell znaną jako Memoization: pokazali kod działający w następujący sposób:

-- Traditional implementation of fibonacci, hangs after about 30
slow_fib :: Int -> Integer
slow_fib 0 = 0
slow_fib 1 = 1
slow_fib n = slow_fib (n-2) + slow_fib (n-1)

-- Memorized variant is near instant even after 10000
memoized_fib :: Int -> Integer
memoized_fib = (map fib [0 ..] !!)
   where fib 0 = 0
         fib 1 = 1
         fib n = memoized_fib (n-2) + memoized_fib (n-1)

Więc moje pytanie do was brzmi: jak, a raczej dlaczego to działa?

Czy to dlatego, że jakoś udaje mu się przejrzeć większość listy przed obliczeniem? Ale jeśli haskell jest leniwy, tak naprawdę nie ma żadnych kalkulacji, które trzeba nadrobić ... Więc jak to działa?

Kawa elektryczna
źródło
1
czy możesz wyjaśnić, co masz na myśli the calculation catches up? BTW, zapamiętywanie nie jest specyficzne dla haskell: en.wikipedia.org/wiki/Memoization
Simon Bergot
zobacz moje wyjaśnienie pod odpowiedzią killana
Electric Coffee,
2
Uwielbiam twoje pytanie; tylko krótka notatka: Technika nazywa notatka ja zacji, nie notatka ri zacji.
Racheet

Odpowiedzi:

11

Aby wyjaśnić mechanikę rzeczywistej zapamiętywania,

memo_fib = (map fib [1..] !!)

tworzy listę „niezgrabnych” obliczeń. Pomyśl o nich jak o nieotwartych prezentach, dopóki ich nie dotkniemy, nie uciekną.

Teraz, gdy oceniamy thunk, nigdy nie oceniamy go ponownie. Jest to właściwie jedyna forma mutacji w „normalnym” haskellu, mutacje thunks po ocenie w celu uzyskania konkretnych wartości.

Wracając do kodu, masz listę kawałków i nadal wykonujesz rekursję tego drzewa, ale rekurencja jest wykonywana przy użyciu tej listy, a kiedy element na liście jest oceniany, nigdy więcej nie jest obliczany. W ten sposób unikamy rekurencji drzewa w naiwnej funkcji Fib.

Jako stycznie interesująca uwaga, jest to szczególnie szybkie w obliczaniu szeregu liczb fibonnaci, ponieważ ta lista jest oceniana tylko raz, co oznacza, że ​​jeśli obliczysz memo_fib 10000dwa razy, drugi raz powinien być natychmiastowy. Wynika to z tego, że Haskell tylko raz przeanalizował argumenty funkcji i używasz częściowej aplikacji zamiast lambda.

TLDR: Przechowując obliczenia na liście, każdy element listy jest oceniany jeden raz, dlatego każda liczba fibonnacci jest obliczana dokładnie raz w całym programie.

Wyobrażanie sobie:

 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_5]
 -- Evaluating THUNK_5
 [THUNK_1, THUNK_2, THUNK_3, THUNK_4, THUNK_3 + THUNK_4]
 [THUNK_1, THUNK_2, THUNK_1 + THUNK_2, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 1 + 1, THUNK_4, THUNK_3 + THUNK_4]
 [1, 1, 2, THUNK_4, 2 + THUNK4]
 [1, 1, 2, 1 + 2, 2 + THUNK_4]
 [1, 1, 2, 3, 2 + 3]
 [1, 1, 2, 3, 5]

Możesz więc zobaczyć, jak ocena THUNK_4jest znacznie szybsza, ponieważ jej podwyrażenia są już oceniane.

Daniel Gratzer
źródło
czy możesz podać przykład, jak zachowują się wartości z listy w krótkiej sekwencji? Myślę, że może to przyczynić się do wizualizacji tego, jak powinno działać ... I chociaż to prawda, że ​​jeśli zadzwonię memo_fibz tą samą wartością dwa razy, drugi raz będzie natychmiastowy, ale jeśli wywołam to z wartością 1 wyższą, to wciąż trwa wieczność (jak powiedzmy, przechodząc od 30 do 31)
Electric Coffee
@ElectricCoffee Dodano
Daniel Gratzer
@ElectricCoffee Nie, nie będzie odtąd memo_fib 29i memo_fib 30są już ocenione, dodanie dokładnie tych dwóch liczb potrwa tak długo, jak to konieczne :) Gdy coś zostanie sprawdzone, pozostanie ewaluowane.
Daniel Gratzer
1
@ElectricCoffee Twoja rekurencja musi przejść przez listę, w przeciwnym razie nie zyskasz żadnego występu
Daniel Gratzer
2
@ElectricCoffee Tak. ale 31. element listy nie korzysta z poprzednich obliczeń, zapamiętujesz tak, ale w całkiem bezużyteczny sposób. Powtarzane obliczenia nie są obliczane dwa razy, ale nadal masz rekurencję drzewa dla każdej nowej wartości, która jest bardzo, bardzo powoli
Daniel Gratzer,
1

Celem zapamiętywania nigdy nie jest dwukrotne obliczenie tej samej funkcji - jest to niezwykle przydatne, aby przyspieszyć obliczenia, które są czysto funkcjonalne, tj. Bez skutków ubocznych, ponieważ dla tych proces może być całkowicie zautomatyzowany bez wpływu na poprawność. Jest to szczególnie konieczne w przypadku funkcji takich fibo, które prowadzą do rekurencji drzewa , tj. Wykładniczego wysiłku, gdy są implementowane naiwnie. (Jest to jeden z powodów, dla których liczby Fibonacciego są w rzeczywistości bardzo złym przykładem do nauczania rekurencji - prawie wszystkie implementacje demonstracyjne, które można znaleźć w samouczkach lub książkach, nie nadają się do użycia przy dużych wartościach wejściowych).

Jeśli prześledzisz przebieg wykonywania, zobaczysz, że w drugim przypadku wartość dla fib xzawsze będzie dostępna, gdy fib x+1zostanie wykonana, a system wykonawczy będzie w stanie po prostu odczytać ją z pamięci zamiast za pomocą innego wywołania rekurencyjnego, podczas gdy pierwsze rozwiązanie próbuje obliczyć większe rozwiązanie, zanim wyniki dla mniejszych wartości będą dostępne. Jest tak ostatecznie, ponieważ iterator [0..n]jest oceniany od lewej do prawej i dlatego zacznie się od 0, podczas gdy rekurencja w pierwszym przykładzie zaczyna się od, na dopiero potem pyta o n-1. To prowadzi do wielu niepotrzebnych wywołań funkcji.

Kilian Foth
źródło
och, rozumiem o co chodzi, po prostu nie rozumiem, jak to działa, na przykład z tego, co widzę w kodzie, że kiedy piszesz memorized_fib 20na przykład, tak naprawdę po prostu piszesz map fib [0..] !! 20, nadal trzeba będzie obliczyć cały zakres liczb do 20, czy coś tu brakuje?
Kawa elektryczna
1
Tak, ale tylko raz dla każdej liczby. Naiwna implementacja oblicza fib 2tak często, że sprawi, że głowa się zakręci - śmiało, zapisz futro drzewa wywołań tylko małą wartość n==5. Nigdy nie zapomnisz zapamiętywania, gdy zobaczysz, co Cię ratuje.
Kilian Foth
@ElectricCoffee: Tak, obliczy fib od 1 do 20. Nie zyskasz nic z tego połączenia. Teraz spróbuj obliczyć Fib 21, a zobaczysz, że zamiast obliczać 1-21, możesz po prostu obliczyć 21, ponieważ już obliczyłeś 1-20 i nie musisz tego robić ponownie.
Phoshi,
Próbuję zapisać drzewo połączeń n = 5, a obecnie doszedłem do punktu, w którym do n == 3tej pory było tak dobrze, ale może to tylko mój imperatywny umysł tak myśli, ale czy to nie znaczy n == 3, że po prostu dostajesz map fib [0..]!!3? który następnie trafia do fib ngałęzi programu ... skąd dokładnie czerpię korzyści z wcześniej obliczonych danych?
Kawa elektryczna
1
Nie, w memoized_fibporządku. To slow_fibsprawi, że będziesz płakać, jeśli go wyśledzisz.
Kilian Foth