Oto prosty problem programistyczny SPOJ: http://www.spoj.com/problems/PROBTRES/ .
Zasadniczo zostaniesz poproszony o podanie największego cyklu Collatza dla liczb między i i j. (Cykl Collatz liczby $ n $ to liczba kroków, które ostatecznie można uzyskać z $ n $ do 1.)
Szukałem sposobu Haskell, aby rozwiązać problem z wydajnością porównawczą niż w Javie lub C ++ (tak, aby pasował do dozwolonego limitu czasu działania). Chociaż proste rozwiązanie Java, które zapamiętuje długość każdego już obliczonego cyklu, będzie działać, nie udało mi się zastosować pomysłu uzyskania rozwiązania Haskell.
Wypróbowałem Data.Function.Memoize, a także technikę zapamiętywania czasu zapisanego w dzienniku domowym, korzystając z pomysłu z tego postu: /programming/3208258/memoization-in-haskell . Niestety zapamiętywanie powoduje, że obliczenia cyklu (n) są jeszcze wolniejsze. Uważam, że spowolnienie pochodzi z górnej części drogi Haskell. (Próbowałem uruchomić ze skompilowanym kodem binarnym, zamiast interpretować.)
Podejrzewam również, że zwykłe iterowanie liczb od i do j może być kosztowne ($ i, j \ le10 ^ 6 $). Próbowałem nawet wstępnie obliczyć wszystko dla zapytania o zakres, używając pomysłu z http://blog.openendings.net/2013/10/range-trees-and-profiling-in-haskell.html . Nadal jednak pojawia się błąd „Przekroczenie limitu czasu”.
Czy możesz pomóc w poinformowaniu o tym porządnego konkurencyjnego programu Haskell?
źródło
Odpowiedzi:
Odpowiem w Scali, ponieważ mój Haskell nie jest tak świeży, więc ludzie uwierzą, że jest to ogólne pytanie dotyczące algorytmu programowania funkcjonalnego. Będę trzymać się struktur danych i pojęć, które można łatwo przenosić.
Możemy zacząć od funkcji, która generuje sekwencję collatz, która jest względnie prosta, z wyjątkiem konieczności przekazania wyniku jako argumentu, aby rekursywnie się kończył:
To faktycznie ustawia sekwencję w odwrotnej kolejności, ale jest to idealne rozwiązanie dla naszego następnego kroku, który polega na zapisaniu długości na mapie:
Można to nazwać odpowiedzią z pierwszego kroku, początkową długością i pustą mapą
calculateLengths(collatz(22), 1, Map.empty))
. W ten sposób zapamiętasz wynik. Teraz musimy zmodyfikować,collatz
aby móc użyć tego:Eliminujemy
n == 1
sprawdzenie, ponieważ możemy po prostu zainicjować mapę1 -> 1
, ale musimy dodać1
do długości, które umieszczamy na mapiecalculateLengths
. Teraz zwraca również zapamiętaną długość, w której przestał się powtarzać, którą możemy użyć do zainicjowaniacalculateLengths
, na przykład:Teraz mamy stosunkowo wydajne implementacje elementów, musimy znaleźć sposób, aby wprowadzić wyniki poprzednich obliczeń do danych wejściowych następnego obliczenia. Nazywa się to a
fold
i wygląda następująco:Teraz, aby znaleźć rzeczywistą odpowiedź, musimy tylko przefiltrować klucze na mapie między podanym zakresem i znaleźć maksymalną wartość, dając końcowy wynik:
W mojej REPL dla zakresów wielkości około 1000, podobnie jak przykładowe dane wejściowe, odpowiedź zwraca się niemal natychmiast.
źródło
Karl Bielefeld już dobrze odpowiedział na pytanie, dodam tylko wersję Haskell.
Najpierw prosta, niepamiętująca wersja podstawowego algorytmu, aby pokazać efektywną rekurencję:
To powinno być prawie oczywiste.
Ja również użyję prostego
Map
do przechowywania wyników.Zawsze możemy sprawdzić nasze ostateczne wyniki w sklepie, więc dla jednej wartości jest to podpis
Zacznijmy od przypadku końcowego
Tak, moglibyśmy to dodać wcześniej, ale mnie to nie obchodzi. Proszę o następną prostą skrzynkę.
Jeśli wartość istnieje, to jest. Nadal nic nie robię.
Jeśli wartości nie ma, musimy coś zrobić . Ustawmy funkcję lokalną. Zauważ, że ta część wygląda bardzo blisko „prostego” rozwiązania, tylko rekurencja jest nieco bardziej złożona.
Teraz wreszcie coś robimy. Jeśli znajdziemy obliczoną wartość w
store''
(sidenote: istnieją dwa znaczniki składni haskell, ale jeden jest brzydki, drugi jest zdezorientowany przez pierwszy symbol. To jedyny powód podwójnej liczby pierwszej)., Po prostu dodajemy nowy wartość. Ale teraz robi się ciekawie. Jeśli nie znajdziemy wartości, musimy ją obliczyć i wykonać aktualizację. Ale mamy już funkcje dla obu! WięcA teraz możemy efektywnie obliczyć jedną wartość. Jeśli chcemy obliczyć kilka, po prostu przekazujemy sklep przez fold.
(Tutaj możesz zainicjować przypadek 1/1.)
Teraz wszystko, co musimy zrobić, to wyodrębnić maksimum. Na razie nie może być w sklepie wartości wyższej niż jedna w zakresie, więc wystarczy powiedzieć
Oczywiście, jeśli chcesz obliczyć kilka zakresów i udostępnić sklep również dla tych obliczeń (foldy są twoim przyjacielem), potrzebujesz filtra, ale to nie jest tutaj główny cel.
źródło
Data.IntMap.Strict
należy użyć.