Реализация (^)

Question

Я читал код реализации (^) из стандартной библиотеки 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) 

Теперь эта часть, где определяется г, кажется странным, почему не просто реализовать, как это:

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) 

Но на самом деле подключения сказать 3^+1000000 показывает, что (^) составляет около 0,04 секунды быстрее, чем экспо.

Почему именно (^) быстрее expo?

Answer 1

Функция рекурсивная, если возвращаемое значение рекурсивного вызова возвращается как есть, без дальнейшей обработки. В expo, f не является хвостовым рекурсивным, из-за otherwise = x * f x (y-1): возвращаемое значение f умножается на x, прежде чем оно будет возвращено. Как f, так и g в (^)являются хвостовыми рекурсивными, поскольку их возвращаемые значения возвращаются без изменений.

Почему это имеет значение? Хвост-рекурсивные функции могут реализовываться гораздо эффективнее, чем общие рекурсивные функции. Поскольку компилятору не требуется создавать новый контекст (кадр стека, для чего у вас) для рекурсивного вызова, он может повторно использовать контекст вызывающего в качестве контекста рекурсивного вызова. Это экономит много накладных расходов при вызове функции, так же как и наложение функции более эффективно, чем вызов функции.

Answer 2

Всякий раз, когда вы видите функцию хлеб с маслом в стандартной библиотеке, и она реализована причудливо, причина почти всегда «, потому что делает это так вызывает некоторые специальные производительности критичных оптимизации [возможно, в другой версии компилятор] ".

Эти нечетные обходные методы обычно «вынуждают» компилятор заметить, что возможна какая-то конкретная важная оптимизация (например, чтобы заставить конкретный аргумент считаться строгим, чтобы разрешить преобразование работника/обертки, что угодно). Как правило, какой-то человек скомпилировал свою программу, заметил, что она эпично медленна, жаловалась разработчикам GHC, и они посмотрели на скомпилированный код и подумали: «О, GHC не видит, что он может встроить эту 3-ю функцию рабочего ... как мне исправить? В результате, если вы слегка перефразировали код, тогда запускается желаемая оптимизация.

Вы говорите, что вы протестировали его, и разница в скорости невелика. Вы не сказали , для какого типа. (Является ли показатель Int или Integer? Как насчет базы? Вполне возможно, что делает существенное различие в какой-то неясной случае.)

Иногда функции реализуются также причудливо поддерживать строгость/леность гарантии. (Например, спецификация библиотеки говорит, что она должна работать определенным образом, и ее реализация наиболее очевидным образом сделает функцию более строгой/менее строгой, чем требования к спецификации.)

Я не знаю, что с этим связано специфический функция, но я бы предложил @chi, вероятно, на что-то.

Answer 3

Как человек, который написал код, могу рассказать вам, почему он сложный. :) Идея состоит в том, чтобы быть хвостом рекурсивным для получения циклов, а также для выполнения минимального количества умножений. Мне не нравится сложность, поэтому, если вы найдете более элегантный способ, напишите отчет об ошибке.