我尝试计算Ackermann(4,1)
,不同语言/编译器之间的性能差异很大。以下是我的Core i7 3820QM, 16G, Ubuntu 12.10 64bit上的结果,
C:1.6s,gcc -O3
(使用 gcc 4.7.2)
int ack(int m, int n) {
if (m == 0) return n+1;
if (n == 0) return ack(m-1, 1);
return ack(m-1, ack(m, n-1));
}
int main() {
printf("%d\n", ack(4,1));
return 0;
}
OCaml:3.6s,ocamlopt
(使用 ocaml 3.12.1)
let rec ack = function
| 0,n -> n+1
| m,0 -> ack (m-1, 1)
| m,n -> ack (m-1, ack (m, n-1))
in print_int (ack (4, 1))
标准 ML:5.1s mlton -codegen c -cc-opt -O3
(带 mlton 20100608)
fun ack 0 n = n+1
| ack m 0 = ack (m-1) 1
| ack m n = ack (m-1) (ack m (n-1));
print (Int.toString (ack 4 1));
球拍:11.5s racket
(使用球拍 v5.3.3)
(require racket/unsafe/ops)
(define + unsafe-fx+)
(define - unsafe-fx-)
(define (ack m n)
(cond
[(zero? m) (+ n 1)]
[(zero? n) (ack (- m 1) 1)]
[else (ack (- m 1) (ack m (- n 1)))]))
(time (ack 4 1))
Haskell:未完成,22 秒后被系统杀死ghc -O2
(使用 ghc 7.4.2)
Haskell: ajhc
1.8 秒(使用 ajhc 0.8.0.4)
main = print $ ack 4 1
where ack :: Int -> Int -> Int
ack 0 n = n+1
ack m 0 = ack (m-1) 1
ack m n = ack (m-1) (ack m (n-1))
Haskell 版本是唯一无法正确终止的版本,因为它占用了太多内存。它会冻结我的机器并在被杀死之前填充交换空间。在不严重修改代码的情况下,我能做些什么来改进它?
编辑:我很欣赏一些渐近更智能的解决方案,但它们并不是我所要求的。这更多是关于查看编译器是否以相当有效的方式(堆栈、尾调用、拆箱等)处理某些模式,而不是计算 ackermann 函数。
编辑 2:正如一些回复所指出的,这似乎是GHC 最新版本中的一个错误。我用AJHC尝试相同的代码并获得更好的性能。
非常感谢你 :)