Racket中的尾调用优化

Question

我正在做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运行得更慢，花费时间创建和销毁对象。

有人能为我解释一下吗？ （以防万一，我在使用Racket 5.2.1）

- aske

Answer 1

如果你将最后一个从句替换为：

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

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

问题在于你正在将cdr的更长列表附加到前面，这比朴素版本遍历并分配了更多，后者将car的边缘附加到前面。

- Sam Tobin-Hochstadt

Answer 2

给定的代码在非尾部位置有应用，因此该函数尽管名为迭代函数，但并不是迭代函数。 :)

请尝试这个：

(define (fringe-tail tree)
  (define (iter tree k)
    (cond
      [(null? tree)
       (k '())]
      [(not (pair? tree)) 
       (k (list tree))]
      [else
       (iter (car tree)
             (lambda (v1)
               (iter (cdr tree)
                     (lambda (v2)
                       (k (append v1 v2))))))]))
  (iter tree (lambda (a-fringe) a-fringe)))

然而，它仍然使用append，这与其第一个参数的长度一样昂贵。对fringe和fringe-tail的某些退化输入将导致大量的计算痛苦。

让我们举个这种退化输入的例子：

(define (build-evil-struct n)
  (if (= n 0)
      (list 0)
      (list (list (build-evil-struct (sub1 n)))
            (build-evil-struct (sub1 n))
            (list n))))

(define evil-struct (build-evil-struct 20))

应用于 fringe 和 fringe-iter 时，性能非常差：我在自己的系统上观察到数秒的计算时间，以进行 fringe 和 fringe-tail 测试。这些测试是在禁用调试的情况下在DrRacket下运行的。如果启用调试，您的数字将显着不同。

> (time (void (fringe evil-struct)))
cpu time: 2600 real time: 2602 gc time: 1212

> (time (void (fringe-tail evil-struct)))
cpu time: 4156 real time: 4155 gc time: 2740

在这两种情况下，使用append使它们容易受到某些退化输入的影响。如果我们编写一个累积版本的fringe，我们可以消除这个成本，因为我们可以使用常数时间的cons操作：

(define (fringe/acc tree)
  (define (iter tree acc)
    (cond [(null? tree)
           acc]
          [(not (pair? tree))
           (cons tree acc)]
          [else
           (iter (car tree) (iter (cdr tree) acc))]))
  (iter tree '()))

让我们来看一下 fringe/acc 在这个结构上的表现：

> (time (void (fringe/acc evil-struct)))
cpu time: 272 real time: 274 gc time: 92

非常好！将所有这里的调用转换为尾调用也是一件简单的事情。

(define (fringe/acc/tail tree)
  (define (iter tree acc k)
    (cond [(null? tree)
           (k acc)]
          [(not (pair? tree))
           (k (cons tree acc))]
          [else
           (iter (cdr tree) acc
                 (lambda (v1)
                   (iter (car tree) v1 k)))]))
  (iter tree '() (lambda (v) v)))

> (time (void (fringe/acc/tail evil-struct)))
cpu time: 488 real time: 488 gc time: 280

Racket对栈的实现在这种情况下比我们在continuations中表示的具象化栈略快，因此fringe/acc比fringe/acc/tail更快。尽管如此，这两者都比fringe显着更好，因为它们避免了append。

话虽如此：这个函数已经内置在Racket中，作为flatten函数！所以如果你不想重复造轮子，最好直接使用它。 :)

- dyoo

---

你尝试过完全尾递归版本吗？在问题给出的示例上，它速度更快吗？ - Sam Tobin-Hochstadt

在稍微复杂一些的树上添加了一些性能数字。 - dyoo