Почему рекурсия с аккумулированием быстрее?

Question

Почему код:

fact2 :: Integer -> Integer
fact2 n | n >= 0    = helper 1 n
        | otherwise = error "error"


helper acc 0 = acc
helper acc n = helper (acc*n) (n - 1)

Быстрее и ест меньше памяти, чем:

fact1 :: Integer -> Integer
fact1 n | n == 0 = 1
        | n > 0  = n * fact1(n - 1)
        | otherwise = error "error"

В обоих же случаях мы используем одну рекурсию

Answer 1

Рискну предположить, потому, что в случае с helper-ом у нас хвостовая рекурсия: рекурсивный вызов в теле функции — последний вызов.

Этот вроде бы частный случай настолько важен потому, что для него компиляторы (не только Хаскеля) используют специальную оптимизацию, по существу разворачивая рекурсивный код в итеративный. Простейшим методом оптимизации было бы замена финального рекурсивного вызова (call) на передачу управления в начало функции (jump). Или помещение всего тела функции в цикл, и замена рекурсивного вызова на continue (что по сути то же самое).

Можно представить себе это так. Ваш код функции helper преобразуется следующим образом:

(эквивалент на императивном языке):

// helper (acc, n)
if (n == 0) return acc
newacc = acc*n
newn = n-1
return helper(newacc, newn)

и хвостовая рекурсия преобразуется в передачу управления на начало (то есть цикл):

// helper (acc, n)
while (true) :
    if (n == 0) return acc;
    newacc = acc*n
    newn = n-1
    // подготовим аргументы для повторения
    acc = newacc
    n = newn

Оптимизатор далее может выбросить ненужные временные переменные, и получим такой код:

// helper (acc, n)
while (true) :
    if (n == 0) return acc;
    acc = acc*n
    n = n-1

Answer 2

INB4 много букв, если вы не сильно заинтересованы в теме, просто считайте, что fact2 потенциально лучше оптимизируется.

На самом деле, ответ на вопрос несколько сложнее чем может показаться на первый взгляд

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

fact1, fact2 :: Integer -> Integer

fact1 1 = 1
fact1 n = n * fact1 (n - 1)

fact2 = go 1
  where
    go acc 1 = acc
    go acc n = go (acc * n) (n - 1)

Теперь несколько слов о том, как haskell осуществляет вычисление. Он постепенно сокращает выражение, заменяя в нем одно применение функции (или оператора) на тело этой функции (или оператора), подставляя фактические параметры.

Согласно ленивой модели вычисления, для подстановки он выбирает в первую очередь то подвыражение, без вычисления которого дальше продвинуться не получится. Вместо тысячи слов:

fact1 5
~> 5 * fact1 (5 - 1)
~> 5 * fact1 4
~> 5 * (4 * fact1 (4 - 1))
~> 5 * (4 * fact1 3)
~> 5 * (4 * (3 * fact1 (3 - 1)))
~> 5 * (4 * (3 * fact1 2))
~> 5 * (4 * (3 * (2 * fact1 (2 - 1))))
~> 5 * (4 * (3 * (2 * fact1 1)))
~> 5 * (4 * (3 * (2 * 1)))
~> 5 * (4 * (3 * 2))
~> 5 * (4 * 6)
~> 5 * 24
~> 120

Обратите внимание, что результат вычисления 5 - 1 нам необходим, чтобы выбрать дальнейший путь подстановки, но некоторые выражения могут оставаться невычисленными очень долго, занимая память и тратя время на их сохранение.

Большая часть времени тратится именно на это: выражение разрастается примерно до середины вычисления, и только потом начинает сокращаться, освобождая память.

А теперь для сравнения

fact2 5
~> go 1 5
~> go (1 * 5) (5 - 1)
~> go (1 * 5) 4
~> go ((1 * 5) * 4) (4 - 1)
~> go ((1 * 5) * 4) 3
~> go (((1 * 5) * 4) * 3) (3 - 1)
~> go (((1 * 5) * 4) * 3) 2
~> go ((((1 * 5) * 4) * 3) * 2) (2 - 1)
~> go ((((1 * 5) * 4) * 3) * 2) 1
~> (((1 * 5) * 4) * 3) * 2
~> ((5 * 4) * 3) * 2
~> (20 * 3) * 2
~> 60 * 2
~> 120

Чувствуете разницу? А? И я не чувствую, все так же плохо.

Вычисление выражения 1 * 5 не требуется для выбора следующего шага подстановки, поэтому оно остается не вычисленным.

Если скомпилировать оба примера без оптимизации, второй может оказаться даже медленнее первого, так в чем же его преимущество? Как раз в возможности оптимизации.

Если включить оптимизацию, процесс вычисления второго выражения пойдет по такому пути.

fact2 5
~> go 1 5
~> go (1 * 5) (5 - 1)
~> go 5 (5 - 1)
~> go 5 4
~> go (5 * 4) (4 - 1)
~> go 20 (4 - 1)
~> go 20 3
~> go (20 * 3) (3 - 1)
~> go 60 (3 - 1)
~> go 60 2
~> go (60 * 2) (2 - 1)
~> go 120 (2 - 1)
~> go 120 1
~> 120

Обратите внимание, хоть результат вычисления 1 * 5 нам в ближайшее время и не понадобится, компилятор все равно его выполнит, потому, что проанализировав функцию go, поймет что она строгая.

Это значит, что переданный ей аргумент обязательно будет вычислен так или иначе в дальнейшем, а значит откладывать его вычисление на потом не выгодно.

Ленивые вычисления это дар и проклятье haskell, иногда приходится повозиться, чтобы убедить компилятор выполнить вычисления заранее, там где это правда будет быстрее, но компилятор этого не видит.

Например, можно переписать fact2 с использованием очевидно строгой версии функции go, не дожидаясь милости компилятора

fact2 = go 1
  where
    go acc 1 = acc
    go acc n = acc `seq` go (acc * n) (n - 1)

В таком случае даже без включенной оптимизации (в т.ч. оптимизации хвостовых вызовов) второе выражение будет вычислено значительно более эффективно.

БЛОГ НА HUSL

Почему рекурсия с аккумулированием быстрее?

Ответы (2 шт):