GHC-Optimierung

Question

Die beiden folgenden Haskell-Funktionen scheinen sich nur dadurch zu unterscheiden, ob die Indexvariable implizit oder explizit ist, aber der Unterschied in der Leistung um zwei Größenordnungen ist.

Diese Funktion dauert etwa 0,03 Sekunden MFI B berechnen 30:

let mfib = (map fib [0..] !!) 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

Diese Funktion nimmt ca. 3 Sekunden für MFI B 30:

let mfib i = map fib [0..] !! i 
    where 
    fib 0 = 0 
    fib 1 = 1 
    fib x = mfib (x-1) + mfib (x-2) 

Ich vermute, es hat mit GHC inline zu tun Regeln und haben versucht, inline/noinline Pragmas hinzuzufügen, um eine übereinstimmende Leistung zu erhalten.

EDIT: Ich verstehe, wie ein Nachschlagen in die faule Liste verwendet werden kann, um die Fib-Funktion zu memotisieren und warum die traditionelle Definition von fib sehr langsam ist. Ich habe erwartet, dass die Memoisierung sowohl in der zweiten als auch in der ersten Funktion funktioniert und nicht versteht, warum dies nicht der Fall ist.

Answer 1

Es ist einfacher, diese Unterschiede zu verstehen, wenn man sich den entzuckerten Code anschaut, daher sind hier einige entzuckte Versionen der beiden Funktionen.

let mfib = let fib 0 = 0 
       fib 1 = 1 
       fib x = mfib (x-1) + mfib (x-2) 
      in (!!) (map fib [0..]) 

Vergleich

let mfib = \i -> 
       let fib 0 = 0 
        fib 1 = 1 
        fib x = mfib (x-1) + mfib (x-2) 
       in map fib [0..] !! i 

anzumerken, dass in dem zweiten Programm, der Ausdruck map fib [0..] innen \i -> ... angezeigt wird, so wird es (in der Regel, ohne Optimierungen) für jeden Wert von i bewertet. Siehe When is memoization automatic in GHC Haskell?

Answer 2

Nein, das hat nichts mit Inlining zu tun. Der Unterschied ist, dass mfib = (map fib [0..] !!) keine Argumente hat. Es ist natürlich immer noch eine Funktion, aber die Auswertung dieser Funktion erfordert im Vorfeld kein Argument. Insbesondere wird durch Auswertung dieser mfib die Liste so generiert, dass sie für alle Indizes wiederverwendet werden kann.

OTOH, mfib i = map fib [0..] !! i bedeutet, dass der gesamte where Block nur berücksichtigt wird, wenn Sie tatsächlich ein Argument übergeben i.

Die beiden sind nur dann unterschiedlich wenn man eine Funktion mehrfach mehrfach auswertet. Leider für die zweite Version, die Funktionen eigene Rekursion ruft sie immer wieder auf! So muss mfib (x-1) + mfib (x-2) dann die gesamte Arbeit von mfib (x-1), und dann wieder die gesamte Arbeit von mfib (x-2) tun. So nimmt mfib n mehr als das Doppelte der Rechenaufwand von mfib (n-1) daher mfib ∈ O (2 ⁿ).

Das ist unglaublich verschwenderisch, denn die meisten Begriffe in mfib (x-2) sind auch schon in mfib (x-1) und könnten einfach wiederverwendet werden. Nun, das ist genau das, was Ihre erste Version tut, weil sie die fib Liste ein für allemal berechnet, so dass die Bewertung mfib (x-1) bereits die meisten Arbeiten erledigt, die dann einfach von mfib (x-2) wieder gelesen werden können, was die Komplexität auf Polynom reduziert.