12

我们有两个函数可以计算给定数字的阶乘。第一个,!,使用累加器样式。第二个,fact,使用自然递归。

(define (! n0)
  (local (;; accumulator is the product of all natural numbers in [n0, n)
      (define (!-a n accumulator)
        (cond
          [(zero? n) accumulator]
          [else (!-a (sub1 n) (* n accumulator))])))
    (!-a n0 1)))

(define (fact n)
  (cond
    [(= 0 n) 1]
    [else (* n (fact (- n 1)))]))

在第 31 节的底部,HtDP指出自然递归版本通常与累加器版本一样快,但没有说明原因。我对此进行了一些阅读,似乎答案是“尾调用优化/消除”,但维基百科的文章似乎与 HtDP 所说的不一致,至少在性能方面。为什么会这样?


在工作中,递归风格更快。在家里,蓄能器风格更快。是否没有一般的启发式方法来指导选择通常首选哪种风格?我知道累加器样式更节省内存,但如果我们将讨论仅限于性能,至少对我来说不清楚,哪个是更好的选择。


我对此进行了更深入的考虑,并且不得不支持维基百科关于一般情况下累加器式递归的优越性的文章。它不仅减少了堆栈/堆空间的使用,而且内存访问总是落后于寄存器访问,并且只有在多核出现后才能更加明显。尽管如此,HtDP 证明在所有情况下都需要进行实际测试。

4

4 回答 4

10

答案将取决于球拍系统的细节。这是我的看法。

自然递归版本和累加器版本之间有两个主要区别。首先,累加器版本以允许尾调用优化的方式编写。这有助于使累加器版本更快,因为需要创建的堆栈帧更少。但这与 HtDP 中讨论的内容以及您在工作计算机上看到的内容相反。

另一个区别是乘法的顺序。自然递归版本将数字从 1 到 20 以升序相乘,即

((((1 * 2) * 3) * … * 19) * 20)

累加器版本按降序乘以相同的数字,即

((((20 * 19) * 18) * … * 2) * 1)

在数学上,它们是相同的,两个阶乘函数将给出相同的结果。尽管如此,这种差异可能很重要。特别是,在任何中间乘法中,后面计算的中间结果将大于前面计算的中间结果。

20 的阶乘是一个很大的数字。它不适合 32 位整数。这意味着球拍将需要使用任意长度的整数(“bignum”)来表示答案,以及一些中间结果。任意精度算术,包括涉及 bignums 的乘法,比固定精度算术要慢。

由于累加器版本中的中间结果总是大于自然递归版本,因此累加器版本将需要比递归版本更早的 bignum。简而言之,虽然两个版本都需要相同数量的乘法,但累加器版本需要更多的任意精度乘法。这使得累加器版本变慢。显然,算术的额外成本超过了减少堆栈帧数量所节省的成本。

那么为什么你的家用电脑上不会出现同样的趋势呢?你说它是 Intel iMac,所以它可能是 64 位系统。虽然20!是一个很大的数字,与适合 64 位整数的数字相比,它很小,因此您的家用计算机不会执行任何任意精度的算术运算,并且顺序无关紧要。HtDP 已经足够老了,它可以使用 32 位系统,就像工作计算机上的 Windows XP 一样。

探索差异更有用的是计算数字列表乘积的函数,或者

(define (product numlist)
  (* (car numlist) (product (cdr numlist)))

或蓄能器版本。然后,无论您使用的是自然递归还是基于累加器的方法,您都可以按升序或降序输入数字。

于 2011-01-21T12:37:48.337 回答
2

我不知道 Racket 编译器的内部结构,但我会推测。

尾调用通常比普通调用更昂贵(在 .NET 中确实如此,最多慢 7 倍),但在某些情况下,尾调用可以被消除,它最终成为while(1) { ... }C 风格的循环,因此不会有额外的调用,只是一个简单的本地跳转,有效地消除了程序应用程序开销。

于 2011-01-19T09:24:24.680 回答
0

一个好的编译器会将递归 fac 转换为尾递归。所以编译后的代码应该没有区别。

于 2011-01-20T22:42:33.090 回答
0

上面有很多好点。我喜欢分析应该是什么以及为什么不应该。这就是欧拉计划成功的原因。太早从 fixnums 出发可能会有问题。

数字序列可以从大到小相乘,反之亦然。我们还有直接类似地进行迭代的“do”命令。

(define (fact n)  (if (= n 1) 1 (* n (fact (- n 1)))))

(define (fact1 n) (do ([n n (- n 1)] [p 1 (* p n)]) ((= n 1) p)))

(define (fact2 n) (do ([i 1 (+ i 1)] [p 1 (* p i)]) ((< n i) p)))

(define (fact3 n) (let f ((n n) (p 1)) (if (= n 1) p (f (- n 1) (* p n)))))

(define (fact4 n) (let f ((i 1) (p 1)) (if (< n i) p (f (+ i 1) (* p i)))))
于 2011-02-28T05:24:41.780 回答