Realizacja (^)

Question

czytałem kod realizacji (^) z biblioteki standardowej Haskell:

(^) :: (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) 

Teraz ta część, gdzie g jest zdefiniowana wydaje się dziwne dla mnie, dlaczego nie wystarczy wdrożyć go jak to:

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) 

Ale rzeczywiście podłączenie powiedzmy 3^1000000 pokazuje, że (^) jest około 0,04 sekundy szybciej niż expo.

Dlaczego numer (^) jest szybszy niż expo?

Answer 1

Funkcja jest rekursywna, jeśli zwracana wartość wywołania cyklicznego jest zwracana bez zmian. W expo, f nie jest rekursywna, z powodu wartości otherwise = x * f x (y-1): wartość zwracana f jest mnożona przez x przed zwróceniem. Zarówno f, jak i są rekursywne, ponieważ ich wartości zwracane są zwracane niezmodyfikowane.

Dlaczego to ma znaczenie? Rekurencyjne funkcje ogonowe mogą być realizowane znacznie wydajniej niż ogólne funkcje rekursywne. Ponieważ kompilator nie musi tworzyć nowego kontekstu (ramka stosu, co ty) dla wywołania rekurencyjnego, może ponownie użyć kontekstu dzwoniącego jako kontekstu wywołania rekursywnego. Pozwala to zaoszczędzić wiele kosztów związanych z wywołaniem funkcji, podobnie jak włączenie funkcji jest bardziej efektywne niż wywołanie właściwej funkcji.

Answer 2

Ilekroć widzisz funkcję Chleb i masło w bibliotece standardowej i jest realizowany dziwnie, powodem jest prawie zawsze „, bo robi to tak, że wywołuje pewne wydajności krytycznych specjalną optymalizację [ewentualnie w innej wersji kompilator] ".

Te nieparzyste obejścia zwykle "zmuszają" kompilator do zauważenia, że ​​możliwa jest jakaś konkretna, ważna optymalizacja (np. Wymuszenie uznania konkretnego argumentu za ścisły, umożliwienie transformacji pracownik/opakowanie, cokolwiek). Zazwyczaj ktoś skompilował swój program, zauważył, że jest bardzo powolny, narzekał na programistów GHC, i spojrzał na skompilowany kod i pomyślał: "och, GHC nie widzi, że może wbudować tę trzecią funkcję pracownika ... jak to zrobić? napraw to?" Rezultat jest taki, że jeśli nieznacznie zmienisz nieco kod, pożądana optymalizacja zostanie uruchomiona.

Mówisz, że to wypróbowałeś i nie ma dużej różnicy prędkości. Nie powiedziałeś dla jakiego typu. (Jest wykładnikiem Int lub Integer? Co z bazy? To całkiem możliwe, że czyni istotną różnicę w jakimś niejasnym przypadku).

Czasami funkcje są realizowane również w celu utrzymania gwarancji dziwnie surowość/lenistwo. (Np. Specyfikacja biblioteki mówi, że musi działać w określony sposób, a wdrożenie go w najbardziej oczywisty sposób spowodowałoby, że funkcja jest bardziej ścisła/mniej rygorystyczna niż roszczenia specyfikacji.)

Nie wiem co jest grane specyficzna funkcja, ale sugerowałbym, że @chi jest prawdopodobnie na czymś.

Answer 3

Jako osoba, która napisała kod, mogę powiedzieć, dlaczego jest to skomplikowane. :) Chodzi o to, aby być rekurencyjnym w celu uzyskania pętli, a także wykonać minimalną liczbę mnożeń. Nie podoba mi się złożoność, więc jeśli znajdziesz bardziej elegancki sposób, zgłoś zgłoszenie błędu.