5

这是 7 个月前的一个老问题，当时堆栈溢出者同意 Haskell 计算 Ackermann 函数的效率低下是由于编译器错误造成的。

Ackermann 使用 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)

我只是要求对此有任何见解。更详细的将获得投票。请记住，我是函数式编程的新手，即使是关于尾递归与常规递归的简单评论也会受到赞赏和支持。

4

2 回答 2

9

我不知道你是如何运行它的，但我怀疑完整的列表是：

  1. 您的程序无需更改，无需优化即可编译。初始时间：7m29.755s

  2. 看来您没有使用优化。编译时一定要使用-O2并尝试。-fllvm新时间：1m2.412s

  3. 尽可能使用显式类型签名并使用Int（与默认值相比Integer）。新时间：0m15.486s

因此，我们通过使用优化获得了近 8 倍的加速（为什么所有其他基准测试问题都不使用优化标志？！？！？）并且通过使用Int而不是Integer.

于 2013-12-11T22:55:33.017 回答
2

将类型签名添加到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 会在称为type defaulting的过程中自动选择一个。

在这种情况下，它选择Integer可变长度类型。因为Integer可以处理任意大小的数字，所以它比机器大小的要慢得多Int。

结论

总结一下：

  • 始终为顶级定义编写类型签名。
  • 总是用-Wall.
于 2013-12-11T22:59:22.227 回答