Wszelkie wskazówki, jak skutecznie rozwiązać następującą funkcję w Haskellu dla dużych liczb (n > 108)
f(n) = max(n, f(n/2) + f(n/3) + f(n/4))
Widziałem przykłady zapamiętywania w Haskellu w celu rozwiązania liczb Fibonacciego, które obejmowały (leniwie) obliczanie wszystkich liczb Fibonacciego do wymaganego n. Ale w tym przypadku dla danego n wystarczy obliczyć bardzo niewiele wyników pośrednich.
Dzięki
haskell
memoization
Angel de Vicente
źródło
źródło
Odpowiedzi:
Możemy to zrobić bardzo efektywnie, tworząc strukturę, którą możemy indeksować w czasie nieliniowym.
Ale najpierw,
Zdefiniujmy
f
, ale niech używa „otwartej rekursji” zamiast wywoływać się bezpośrednio.Możesz uzyskać niezapamiętać
f
, używającfix f
Pozwoli ci to sprawdzić,
f
czy to, co masz na myśli, dla małych wartościf
, dzwoniąc, na przykład:fix f 123 = 144
Moglibyśmy to zapamiętać, definiując:
To działa dość dobrze i zastępuje to, co miało zająć O (n ^ 3) czas, czymś, co zapamiętuje wyniki pośrednie.
Ale wciąż potrzeba czasu liniowego, aby indeksować, aby znaleźć zapamiętaną odpowiedź
mf
. Oznacza to, że wyniki takie jak:są do zaakceptowania, ale wynik nie skaluje się dużo lepiej. Możemy zrobić lepiej!
Najpierw zdefiniujmy nieskończone drzewo:
Następnie zdefiniujemy sposób indeksowania do niego, abyśmy mogli zamiast tego znaleźć węzeł z indeksem
n
w czasie O (log n) :... i możemy znaleźć drzewo pełne liczb naturalnych dla wygody, więc nie będziemy musieli bawić się tymi indeksami:
Ponieważ możemy indeksować, możesz po prostu przekonwertować drzewo na listę:
Możesz sprawdzić dotychczasową pracę, weryfikując, która
toList nats
daje[0..]
Teraz,
działa tak samo, jak w przypadku powyższej listy, ale zamiast potrzebować czasu liniowego na znalezienie każdego węzła, można go ścigać w czasie logarytmicznym.
Wynik jest znacznie szybszy:
W rzeczywistości jest to o wiele szybsze, że możesz przejść przez powyższe i zastąpić
Int
jeInteger
powyższymi i niemal natychmiast uzyskać absurdalnie duże odpowiedziźródło
f_tree
być definiowany wwhere
klauzuli, aby uniknąć zapisywania niepotrzebnych ścieżek w drzewie między wywołaniami?Odpowiedź Edwarda jest tak wspaniałą perełką, że ją zduplikowałem i dostarczyłem implementacje
memoList
imemoTree
kombinatory, które zapamiętują funkcję w formie otwarto-rekurencyjnej.źródło
Nie jest to najbardziej efektywny sposób, ale zapamiętuje:
przy żądaniu
f !! 144
sprawdza się, czyf !! 143
istnieje, ale jego dokładna wartość nie jest obliczana. Nadal jest to nieznany wynik obliczeń. Jedynymi dokładnymi obliczonymi wartościami są te potrzebne.Tak więc początkowo, o ile zostało obliczone, program nic nie wie.
Kiedy wysyłamy żądanie
f !! 12
, zaczyna ono dopasowywać wzorce:Teraz zaczyna obliczać
To rekurencyjnie tworzy kolejne żądanie na f, więc obliczamy
Teraz możemy trochę cofnąć
Co oznacza, że program teraz wie:
Nadal sączy się:
Co oznacza, że program teraz wie:
Teraz kontynuujemy obliczenia
f!!6
:Co oznacza, że program teraz wie:
Teraz kontynuujemy obliczenia
f!!12
:Co oznacza, że program teraz wie:
Więc obliczenia są wykonywane dość leniwie. Program wie, że
f !! 8
istnieje jakaś wartość for , że jest równag 8
, ale nie ma pojęcia, co niąg 8
jest.źródło
g n m = (something with) f!!a!!b
To jest dodatek do doskonałej odpowiedzi Edwarda Kmetta.
Kiedy wypróbowałem jego kod, definicje
nats
iindex
wydawały się dość tajemnicze, więc piszę alternatywną wersję, która była dla mnie łatwiejsza do zrozumienia.Definiuję
index
inats
w kategoriachindex'
inats'
.index' t n
jest zdefiniowany w zakresie[1..]
. (Przypomnij sobie, żeindex t
jest to zdefiniowane w zakresie[0..]
.) To działa przeszukuje drzewo traktując jen
jako ciąg bitów i odczytując je w odwrotnej kolejności. Jeśli bit jest1
, bierze prawą gałąź. Jeśli bit jest0
, bierze lewą gałąź. Zatrzymuje się, gdy osiągnie ostatni bit (który musi być a1
).Tak jak
nats
jest zdefiniowane dla,index
takindex nats n == n
jest zawsze prawdziwe,nats'
jest zdefiniowane dlaindex'
.Teraz
nats
iindex
są po prostunats'
iindex'
ale z wartościami przesuniętymi o 1:źródło
Jak stwierdzono w odpowiedzi Edwarda Kmetta, aby przyspieszyć działanie, trzeba buforować kosztowne obliczenia i mieć do nich szybki dostęp.
Aby funkcja nie była monadyczna, rozwiązanie polegające na budowaniu nieskończonego leniwego drzewa z odpowiednim sposobem jego indeksowania (jak pokazano w poprzednich postach) spełnia ten cel. Jeśli zrezygnujesz z niemonadycznego charakteru funkcji, możesz użyć standardowych kontenerów asocjacyjnych dostępnych w Haskell w połączeniu z monadami „stanowymi” (takimi jak State lub ST).
Chociaż główną wadą jest to, że otrzymujesz funkcję niemonadyczną, nie musisz już samodzielnie indeksować struktury i możesz po prostu użyć standardowych implementacji kontenerów asocjacyjnych.
Aby to zrobić, musisz najpierw ponownie napisać swoją funkcję, aby akceptowała jakąkolwiek monadę:
W swoich testach nadal możesz zdefiniować funkcję, która nie wykonuje zapamiętywania za pomocą Data.Function.fix, chociaż jest nieco bardziej szczegółowa:
Następnie możesz użyć State monad w połączeniu z Data.Map, aby przyspieszyć działanie:
Po drobnych zmianach można zamiast tego dostosować kod do pracy z Data.HashMap:
Zamiast trwałych struktur danych możesz także wypróbować zmienne struktury danych (takie jak Data.HashTable) w połączeniu z monadą ST:
W porównaniu z implementacją bez zapamiętywania, każda z tych implementacji pozwala, przy dużych nakładach, na uzyskanie wyników w mikro-sekundach, zamiast czekać kilka sekund.
Używając Criterion jako benchmarku, mogłem zauważyć, że implementacja z Data.HashMap faktycznie działała nieco lepiej (około 20%) niż ta z Data.Map i Data.HashTable, dla których czasy były bardzo podobne.
Wyniki testu porównawczego okazały się nieco zaskakujące. Moje początkowe wrażenie było takie, że HashTable przewyższy implementację HashMap, ponieważ jest zmienna. W tej ostatniej implementacji może być ukryty jakiś defekt wydajności.
źródło
Kilka lat później przyjrzałem się temu i zdałem sobie sprawę, że istnieje prosty sposób na zapamiętanie tego w czasie liniowym przy użyciu
zipWith
funkcji pomocniczej:dilate
ma tę przydatną właściwośćdilate n xs !! i == xs !! div i n
.Więc zakładając, że mamy f (0), to upraszcza obliczenia do
Wygląda bardzo podobnie do naszego oryginalnego opisu problemu i daje liniowe rozwiązanie (
sum $ take n fs
zajmie O (n)).źródło
Kolejny dodatek do odpowiedzi Edwarda Kmetta: samodzielny przykład:
Użyj go w następujący sposób, aby zapamiętać funkcję z pojedynczą liczbą całkowitą arg (np. Fibonacci):
Buforowane będą tylko wartości argumentów nieujemnych.
Aby również buforować wartości argumentów ujemnych, użyj
memoInt
, zdefiniowane w następujący sposób:Aby buforować wartości dla funkcji z dwoma argumentami całkowitymi, użyj
memoIntInt
, zdefiniowanych w następujący sposób:źródło
Rozwiązanie bez indeksowania, a nie oparte o Edward KMETT.
Oddzielam wspólne poddrzewa do wspólnego rodzica (
f(n/4)
jest dzielone międzyf(n/2)
if(n/4)
if(n/6)
jest dzielone międzyf(2)
if(3)
). Zapisując je jako pojedynczą zmienną w rodzicu, obliczenie poddrzewa jest wykonywane raz.Kod nie jest łatwo rozszerzany do ogólnej funkcji zapamiętywania (przynajmniej nie wiedziałbym, jak to zrobić) i naprawdę musisz pomyśleć, w jaki sposób podproblemy się pokrywają, ale strategia powinna działać dla ogólnych parametrów wielu niecałkowitych . (Wymyśliłem to dla dwóch parametrów ciągów.)
Notatka jest odrzucana po każdym obliczeniu. (Ponownie myślałem o dwóch parametrach ciągów.)
Nie wiem, czy to jest bardziej wydajne niż inne odpowiedzi. Technicznie każde wyszukiwanie składa się z jednego lub dwóch kroków („Spójrz na swoje dziecko lub dziecko”), ale może wymagać dużo dodatkowej pamięci.
Edycja: to rozwiązanie nie jest jeszcze poprawne. Udostępnianie jest niekompletne.Edycja: Powinno teraz poprawnie udostępniać poddzieci, ale zdałem sobie sprawę, że ten problem ma wiele nietrywialnych współdzielenia:
n/2/2/2
in/3/3
może być taki sam. Problem nie pasuje do mojej strategii.źródło