Haskell Fibonacciego wydaje się powolny

uczę Haskell, i napisałem prostą funkcję Fibonacciego:Haskell Fibonacciego wydaje się powolny

fib :: Int -> Int 

fib 1 = 1 
fib 0 = 0 
fib n = (fib (n-1)) + (fib (n-2))

Wydaje skompilować OK, a załadunek ten skrypt do GHCI REPL mogłem poeksperymentować z kilkoma numerami . Próbowałem

fib 33

i był zaskoczony, że zajęło to około 4 sekund, uzyskując rezultat. (Przepraszam, nie wiem jeszcze, jak czasować funkcję w Haskell, więc liczyłem się).

Fib 33 nie jest szczególnie podatkowy. Odpowiedź jest mniejsza niż 4 miliony. Zakładam więc, że mój kod nie jest napisany zbyt dobrze lub jest jakiś problem ze sposobem, w jaki robię rekurencję (no cóż, nie jest dobrze napisane, że nie bierze pod uwagę liczb całkowitych ujemnych). Pytanie brzmi: dlaczego jest wolny? Każda pomoc doceniona.

Źródło

2014-12-17 Anonymous

To pytanie wydaje się być dobry dla inspekcja kodu. – Alexander

Patrząc na swój kod, wyobraź sobie, jak często oblicza się na przykład 'fib (5)'. W każdej iteracji obliczasz ponownie wszystkie "wewnętrzne" liczby fibonaccich. – WeSt

Powinieneś użyć klasycznej wersji nieskończonej listy leniwej: 'fibs = 0: 1: zipWith (+) fibs (tail fibs)' with 'fib n = fibs !! n'. Zobacz [wiki haskell o sekwencji Fibonacciego] (https://www.haskell.org/haskellwiki/The_Fibonacci_sequence).Zabawne jest to, że Fibonacci słynie z tej sekwencji, która była zaledwie małym ćwiczeniem w książce, z której powinien być znany, co wprowadziło wartość dodaną do Europy Zachodniej. – AndrewC

Ocena trwała dłużej niż oczekiwano, ponieważ funkcja nie używa memoization. Zobacz np. this question lub that question w celu uzyskania odpowiedzi na pytanie, jak zdefiniować funkcję fibonacci w Haskell za pomocą zapamiętywania.

Źródło

2014-12-17 15:59:24

Łącze do pamię ci umożliwiajĘ ... cej wyjaś nienie problemu. –

Zarówno pytania, jak i odpowiedzi są raczej ezoteryczne. A co z * podręcznikiem * podręcznikiem? –

@ n.m. W zależności od tego, do jakiego podręcznika jesteś przyzwyczajony, możesz zauważyć, że link haskellwiki pokazuje "metodę podręcznika" (w sekcji "Memoization with recursion"). –

Czy porównałeś ten czas z innymi językami?

To jest algorytm rekursywny, który ma złożoność O (2^n). W n = 33, co daje oszałamiającą liczbę połączeń. Jeśli policzysz ile milisekund lub nanosekund było na takie połączenie, pozostaje ci bardzo niezwykła odpowiedź co do rzeczywistej wydajności.

Należy pamiętać, że niektóre kompilatory/środowisko wykonawcze może buforować wartości zwracane przez funkcję (Frerich miał lepszą pamięć, jak się nazywa: memoization), co znacznie poprawia wydajność w przypadku tego algorytmu. W tym przypadku tak się nie dzieje, więc wszystkie te 2^n wywołania rekursywne się zdarzają.

Źródło

2014-12-17 16:00:54 Gerino

Technicznie, jego złożoność to "O (fib n)", stąd mniej więcej "O (1.68^n)", która jest nieco lepsza niż "O (2^n)". Nie ma to jednak wpływu na twój punkt widzenia: jego złożoność jest nadal wykładnicza, więc liczba rekurencyjnych wywołań szybko staje się niepraktyczna. – chi

Twój algorytm nie jest zbyt dobry. Możesz ją nieco poprawić za pomocą memoizacji, aż do O (n). Korzystanie dziel i rządź, można dostać się do O (log N):

import Data.Matrix 

fib :: Integer -> Integer 
fib n = ((fromLists [[1,1],[1,0]])^n) ! (1,2)

Chodzi o to, że mnożenie jest łączne, więc można umieścić swoje szelki na strategicznych miejscach:

5^10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5)^2 = ((5 * 5) * (5 * 5) * 5)^2 = ((5 * 5)^2 * 5)^2 = (((5^2)^2) * 5)^2

Ten sam wzór można zastosować do mnożenia macierzy. A Haskell już to zaimplementował w domyślnej bibliotece dla (^).

Działa to rzeczywiście:

map fib [1..21] 
--! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]

Źródło

2014-12-17 17:02:59

Haskell Fibonacciego wydaje się powolny

Odpowiedz

Powiązane problemy