Haskell Fibonacci scheint langsam

ich Haskell lerne, und ich schrieb eine einfache Fibonacci-Funktion:Haskell Fibonacci scheint langsam

fib :: Int -> Int 

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

Es scheint ok zu kompilieren, und Laden des Skripts in die GHCI REPL ich konnte herumspielen mit ein paar Zahlen . Ich versuchte

fib 33

und war überrascht, dass es etwa 4 Sekunden gedauert um das Ergebnis zu geben. (Entschuldigung, ich weiß noch nicht, wie ich eine Funktion in Haskell einstellen soll, also zählte ich selbst).

Fib 33 ist nicht besonders anstrengend. Die Antwort ist weniger als 4 Millionen. Also ich nehme an, dass mein Code nicht sehr gut geschrieben ist oder es gibt ein Problem mit der Art, wie ich Rekursion mache (naja, es ist nicht gut geschrieben, da es negative ganze Zahlen nicht berücksichtigt). Die Frage ist, warum ist es langsam? Jede Hilfe wird geschätzt.

Quelle

2014-12-17 Anonymous

Diese Frage scheint für Codereview ein guter zu sein. – Alexander

Wenn Sie sich Ihren Code anschauen, stellen Sie sich vor, wie oft zum Beispiel 'fib (5)' berechnet wird. Bei jeder Iteration berechnen Sie alle "inneren" Fibonacci-Zahlen erneut. – WeSt

Sie sollten die klassische Lazy Infinite-Version verwenden: 'fibs = 0: 1: zipWith (+) fibs (tail fibs)' mit 'fib n = fabs !! n'. Siehe [das Haskell-Wiki über die Fibonacci-Sequenz] (https://www.haskell.org/haskellwiki/The_Fibonacci_sequence).Es ist amüsant, dass Fibonacci für diese Sequenz berühmt ist, die nur eine kleine Übung in dem Buch war, für das er berühmt sein sollte, das in Westeuropa einen Stellenwert einführte. – AndrewC

Die Auswertung dauerte länger als erwartet, da Ihre Funktion memoization nicht verwendet. Siehe z.B. this question oder that question für Antworten zur Definition der Fibonacci-Funktion in Haskell mit Memoization.

Quelle

2014-12-17 15:59:24

Der Memo-Link erklärte das Problem sehr gut. –

Beide Fragen und ihre Antworten sind eher esoterisch. Was ist mit dem Lehrbuch? –

@ n.m. Je nachdem, welches Lehrbuch Sie gewohnt sind, können Sie feststellen, dass der Haskellwiki-Link "die Lehrbuchmethode" anzeigt (im Abschnitt "Memoisierung mit Rekursion"). –

Haben Sie diese Zeit mit anderen Sprachen verglichen?

Dies ist ein rekursiver Algorithmus mit O (2^n) -Komplexität. Bei n = 33 ergibt sich eine erstaunliche Anzahl von Anrufen. Wenn Sie zählen, wie viele Millisekunden oder Nanosekunden pro Anruf vorhanden sind, erhalten Sie eine sehr bemerkenswerte Antwort auf die tatsächliche Leistung.

Denken Sie daran, dass einige Compiler/Ausführungsumgebung Funktionsrückgabewerte zwischenspeichern kann (Frerich hatte einen besseren Speicher, wie es heißt: memoization), was die Leistung im Falle dieses Algorithmus stark verbessert. In diesem Fall passiert es nicht, so dass alle diese 2^n rekursiven Aufrufe passieren.

Quelle

2014-12-17 16:00:54 Gerino

Technisch ist seine Komplexität "O (fib n)", also ungefähr "O (1,68^n)", was etwas besser ist als "O (2^n)". Dies wirkt sich jedoch nicht auf Ihren Punkt aus: Die Komplexität ist immer noch exponentiell, so dass die Anzahl der rekursiven Aufrufe schnell unpraktisch wird. – chi

Ihr Algorithmus ist nicht sehr gut. Sie können es ein wenig verbessern, indem Sie Memoization bis zu O (n) verwenden. Mit teile und herrsche, können Sie O aufstehen (log n):

import Data.Matrix 

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

Die Idee ist, ist, dass die Multiplikation assoziativ, so dass Sie Ihre Zahnspange auf strategisch wichtigen Orten setzen können:

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

Das gleiche Muster kann angewandt werden, Matrix-Multiplikation. Und Haskell hat dies bereits in seiner Standardbibliothek für (^) implementiert.

Dies funktioniert in der Tat:

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]

Quelle

2014-12-17 17:02:59

Antwort

Verwandte Themen