Umsetzung von (^)

Question

ich den Code der Umsetzung von (^) der Standard Haskell Bibliothek zu lesen:

(^) :: (Num a, Integral b) => a -> b -> a 
x0^y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
     | y0 == 0 = 1 
     | otherwise = f x0 y0 
    where -- f : x0^y0 = x^y 
      f x y | even y = f (x * x) (y `quot` 2) 
       | y == 1 = x 
       | otherwise = g (x * x) ((y - 1) `quot` 2) x 
      -- g : x0^y0 = (x^y) * z 
      g x y z | even y = g (x * x) (y `quot` 2) z 
        | y == 1 = x * z 
        | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z) 

Nun ist dieser Teil, wo g definiert ist, scheint mich seltsam, warum es nicht einfach umzusetzen wie dies:

expo :: (Num a ,Integral b) => a -> b ->a 
expo x0 y0 
    | y0 == 0 = 1 
    | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
    | otherwise = f x0 y0 
    where 
     f x y | even y = f (x*x) (y `quot` 2) 
       | y==1 = x 
       | otherwise = x * f x (y-1) 

Aber in der Tat aufstecken sagen 3^1000000 zeigt, dass (^) etwa 0,04 Sekunden schneller als expo ist.

Warum ist (^) schneller als expo?

Answer 1

Eine Funktion ist tail-rekursiv, wenn der Rückgabewert eines rekursiven Aufrufs ohne weitere Verarbeitung unverändert zurückgegeben wird. In expo ist f nicht tail-rekursiv, da otherwise = x * f x (y-1): der Rückgabewert von f mit x multipliziert wird, bevor es zurückgegeben wird. Sowohl f als auch g in (^)sind tail-recursive, da ihre Rückgabewerte unverändert zurückgegeben werden.

Warum ist das wichtig? Tail-rekursive Funktionen können viel effizienter als allgemeine rekursive Funktionen implementiert werden. Da der Compiler für einen rekursiven Aufruf keinen neuen Kontext (Stapelrahmen, was Sie haben) erstellen muss, kann er den Kontext des Aufrufers als Kontext des rekursiven Aufrufs wiederverwenden. Dies spart viel Aufwand beim Aufruf einer Funktion, ähnlich wie das Einfügen einer Funktion effizienter ist als das Aufrufen der Funktion.

Answer 2

Jedes Mal, wenn Sie eine Brot-und-Butter-Funktion in der Standardbibliothek zu sehen und es ist bizarr umgesetzt wird, ist der Grund fast immer „, weil es wie das zu tun einige spezielle leistungskritische Optimierung löst [möglicherweise in einer anderen Version von der Compiler] ". Diese seltsamen Problemumgehungen sind normalerweise, um den Compiler zu "zwingen", zu bemerken, dass eine bestimmte, wichtige Optimierung möglich ist (z. B. um zu erzwingen, dass ein bestimmtes Argument als streng angesehen wird, um eine Worker/Wrapper-Transformation zu erlauben). Typischerweise hat jemand sein Programm kompiliert, es ist episch langsam, hat sich bei den GHC-Entwicklern beschwert und sie haben sich den kompilierten Code angeschaut und gedacht: "Oh, GHC sieht nicht, dass es diese dritte Arbeitsfunktion inline ... wie kann ich repariere das?" Wenn Sie den Code nur geringfügig umformulieren, wird die gewünschte Optimierung ausgelöst.

Sie sagen, Sie haben es getestet und es gibt nicht viel Geschwindigkeitsunterschied. Sie haben nicht gesagt, für welche Art. (Ist der Exponent Int oder Integer? Was ist mit der Basis? Es ist durchaus möglich, es einen signifikanten Unterschied in einem obskuren Fall macht.)

Gelegentlich Funktionen auch weirdly umgesetzt werden Strikt/Faulheit Garantien zu erhalten. (ZB die Bibliotheksspezifikation sagt, dass sie auf eine bestimmte Weise arbeiten muss, und die Implementierung der offensichtlichsten Weise würde die Funktion strikter/weniger streng machen als die Spezifikation behauptet.)

Ich weiß nicht, was los ist spezifische Funktion, aber ich würde vorschlagen, @chi ist wahrscheinlich auf etwas.

Answer 3

Als die Person, die den Code schrieb, kann ich Ihnen sagen, warum es komplex ist. :) Die Idee ist es, tail rekursiv zu sein, um Schleifen zu erhalten und auch die minimale Anzahl von Multiplikationen durchzuführen. Ich mag die Komplexität nicht. Wenn Sie also einen eleganteren Weg finden, reichen Sie bitte einen Fehlerbericht ein.