球拍中的尾巴呼叫优化(Tail call optimization in Racket)

球拍中的尾巴呼叫优化(Tail call optimization in Racket)

我正在做SICP 练习2.28并偶然发现以下代码的奇怪行为：

(define (fringe tree) (cond ((null? tree) '()) ((not (pair? tree)) (list tree)) (else (append (fringe (car tree)) (fringe (cdr tree)))))) (define (fringe-tail tree) (define (fringe-iter tree result) (cond ((null? tree) result) ((not (pair? tree)) (list tree)) (else (fringe-iter (cdr tree) (append result (fringe-tail (car tree))))))) (fringe-iter tree '())) (define x (make-list (expt 10 4) 4)) (time (fringe x)) (time (fringe-tail x))

普通fringe比其迭代版本fringe-tail速度快得多：

cpu time: 4 real time: 2 gc time: 0

与

cpu time: 1063 real time: 1071 gc time: 191

它看起来像fringe被优化成循环，并避免任何分配，而fringe-tail运行速度更慢，并花时间创建和销毁对象。

任何人都可以向我解释这个吗？ （以防我使用球拍5.2.1）

I was doing SICP exercise 2.28 and stumbled upon a strange behaviour of the following code:

(define (fringe tree) (cond ((null? tree) '()) ((not (pair? tree)) (list tree)) (else (append (fringe (car tree)) (fringe (cdr tree)))))) (define (fringe-tail tree) (define (fringe-iter tree result) (cond ((null? tree) result) ((not (pair? tree)) (list tree)) (else (fringe-iter (cdr tree) (append result (fringe-tail (car tree))))))) (fringe-iter tree '())) (define x (make-list (expt 10 4) 4)) (time (fringe x)) (time (fringe-tail x))

Ordinary fringe runs much faster than its iterative version fringe-tail:

cpu time: 4 real time: 2 gc time: 0

vs.

cpu time: 1063 real time: 1071 gc time: 191

It looks like fringe was optimized into loop and avoids any allocations, while fringe-tail runs much slower and spends time creating and destroying objects.

Can anyone explain this to me? (Just in case I'm using racket 5.2.1)

最满意答案

如果你用最后一个条款替换：

(else (fringe-iter (cdr tree) (append (fringe-tail (car tree)) result)))

然后它们以相同的速度运行该输入，并且尾递归版本对于更大的输入更快。

问题在于你在cdr上append了更长的列表，这个列表比前面的版本更加经过和分配，这个版本会将car的边缘附加到前面。

If you replace the last clause with:

(else (fringe-iter (cdr tree) (append (fringe-tail (car tree)) result)))

then they run at the same speed for that input, and the tail-recursive version is faster for larger input.

The problem is that you're appending the much longer list for the cdr on to the front, which traverses and allocates much more than the naive version, which appends the fringe of the car on to the front.