Haskell не спешит вычислять Аккермана 4 1?

Вот старый вопрос от 7 месяцев назад, когда переполнители стека согласились, что неэффективность Haskell в вычислении функции Аккермана была вызвана ошибкой компилятора.

Аккерманн очень неэффективен с Haskell / GHC

7 месяцев спустя, это, кажется, исправлено. Кажется, что Ack работает с линейной памятью, но работает довольно медленно.

main = print (ack 4 1)
-- Ackermann function
ack 0 n = n + 1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n - 1))

$ time ./ack
65533

>real   8m53.274s
>user   8m47.313s
>sys    0m4.868s


Processor  2.8 GHz Intel Core i7
Memory  8 GB 1333 MHz DDR3
Software  Mac OS X Lion 10.7.5 (11G63)

Я просто прошу любую информацию об этом. Более подробные будут проголосованы. Имейте в виду, что я новичок в функциональном программировании, и даже простые замечания о хвостовой рекурсии против обычной рекурсии будут оценены и одобрены.

Источник

2 ответа

Решение

Я не знаю, как вы работаете, но я подозреваю, что полный список:

  1. Ваша программа без изменений и компиляция без оптимизации. Начальное время: 7м29.755с

  2. Похоже, вы не использовали оптимизацию. Обязательно используйте -O2 и попробовать -fllvm при компиляции. Новое время: 1м2.412с

  3. Используйте явные подписи типов и используйте Int (против значения по умолчанию Integer) когда ты можешь. Новое время: 0м15.486с

Таким образом, мы получили почти 8-кратное ускорение с помощью оптимизаций (почему в каждом другом вопросе о тесте производительности не используются флаги оптимизации?!?!?) И дополнительно ~4x с помощью Int вместо Integer,

Источник

Добавить сигнатуру типа в ack:

ack :: Int -> Int -> Int

Это должно решить две проблемы с вашим кодом:

Чрезмерно общие типы

Без подписи компилятор получает следующий тип:

ack :: (Eq a, Eq b, Num a, Num b) => a -> b -> b

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

дающий ack конкретный тип (как Int) удаляет эту косвенность.

Тип по умолчанию

Кроме того, я предполагаю, что ваше основное действие написано так:

main = print (ack 4 1)

Ваш ack работает с любым типом чисел, но вы не указываете, какой именно. Это означает, что GHC выбирает один автоматически в процессе, называемом типом по умолчанию.

В этом случае он выбирает Integerтип переменной длины. Так как Integer может обрабатывать числа произвольного размера, это намного медленнее, чем размер машины Int,

Заключение

Подвести итоги:

  • Всегда пишите сигнатуры типов для определений верхнего уровня.
  • Всегда компилировать с -Wall,
Источник
Другие вопросы по тегам