4

我在做 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）

4

2 回答 2

6

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

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

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

问题是您append为 on 设置了更长的列表cdr到前面，它遍历和分配的内容比将 on 的边缘附加到前面的简单版本要多得多car。

于 2012-07-16T17:07:15.603 回答
4

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

试试这个：

(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 。边缘和边缘尾的某些退化输入会导致大量计算问题。

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

(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 的堆栈实现比我们在延续中表示的具体堆栈快一点，因此fringe/acc比fringe/acc/tail快。尽管如此，这两者都比fringe好得多，因为它们避免了append。

话虽这么说：这个函数已经作为flatten函数内置在 Racket 中！因此，如果您不想重新发明轮子，不妨使用它。:)

于 2012-07-17T20:56:40.580 回答