3

Почему код:

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"

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

3
  • Чисто для себя интересуюсь - а вы с включенной оптимизацией собирали?
    – arrowd
    27 янв 2021 в 7:27
  • Честно, даже не знаю. Просто импортирую модуль в ghci, пишу :set +s, вызываю две функции и смотрю на время и память. 27 янв 2021 в 14:19
  • По умолчанию, ghci не оптимизирует. Попробуйте запускать ghci -fobject-code -O.
    – arrowd
    27 янв 2021 в 16:07

2 ответа 2

6

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)

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

5
  • Думаю, ваше описание соответствует тому, как происходит интерпретация, а моё — как компиляция.
    – VladD
    28 янв 2021 в 10:46
  • @VladD то, что я описал, это алгоритм вычисления, но по нему компилятор после нескольких преобразований сделает коротенькую ассемблерную программу. Я просто хотел подчеркнуть, что основную роль тут играет анализатор строгости функции, а не оптимизация хвостовых вызовов. Потому что в haskell функция не обязана содержать (иногда обязана не содержать) хвостовых вызовов, чтобы быть оптимальной.
    – extrn
    28 янв 2021 в 10:52
  • Однако же вопрос ТС противоречит вашему утверждению, разве нет? Если бы оптимизированный код определялся лишь семантикой функции, ассемблерный выхлоп был бы строго одинаков, т. к. функции семантически эквивалентны, верно?
    – VladD
    28 янв 2021 в 10:54
  • Вот например gcc умный, развернул нехвостовую рекурсию в итерацию godbolt.org/z/rjYxdh
    – VladD
    28 янв 2021 в 11:17
  • @VladD тема интересная и сложная, и в комментарии не уместится :) Тут всегда нужно держать в голове ленивые вычисления, и если достоверно не известно, что функция строгая, то описанная мной оптимизация изменит ее семантику. Попробуйте скомпилировать программу со всем пучком оптимизаций, но без анализа строгости ghc -O2 -fno-strictness Main.hs а потом то же самое но без оптимизации хвостовой рекурсии ghc -O2 -fno-loopification Main.hs, и станет понятно, что тут играет первостепенную роль (поменял тип на Int для пущей наглядности)
    – extrn
    28 янв 2021 в 11:36
5

Рискну предположить, потому, что в случае с 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
10
  • Похоже у вас тут есть хейтеры (или кто-то совсем фишку не рубит)
    – avp
    26 янв 2021 в 21:47
  • @avp: Это уже не первый вопрос такой, так что наверное хейтеры
    – VladD
    26 янв 2021 в 21:49
  • Как поживаете ?
    – avp
    26 янв 2021 в 21:58
  • Вроде ничего, в Германии карантин, сижу дома всё время. А у вас что нового?
    – VladD
    26 янв 2021 в 22:02
  • Я тоже какое-то время был на удаленке, но теперь мы постепенно возвращаемся. Надеюсь, к лету заразу отменят (скажут, что победили)
    – avp
    26 янв 2021 в 22:05

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.