algorithm - 两种组合函数的方法，效率有何不同？

Question

让 f 将一个值转换为另一个值，然后我正在编写一个重复转换 n 次的函数。

我想出了两种不同的方法:

• 一种是显而易见的方式从字面上应用函数 n次，所以 repeat(f, 4) 表示 x →f(f(f(f(x))))
• 另一种方式的灵感来自于快速供电的方法，这意味着将问题一分为二一半大的问题每当 n 是偶数时。所以重复(f, 4)表示 x → g(g(x)) 其中 g(x) =f(f(x))

起初我认为第二种方法不会提高效率。在一天结束时，我们仍然需要申请 f n 次，不是吗？在上面的例子中，g 仍然会被翻译成 f of f，没有任何进一步的简化，对吧？

但是，当我尝试这些方法时，后一种方法明显更快。

;; computes the composite of two functions
(define (compose f g)
  (lambda (x) (f (g x))))

;; identify function
(define (id x) x)

;; repeats the application of a function, naive way
(define (repeat1 f n)
  (define (iter k acc)
    (if (= k 0)
        acc
        (iter (- k 1) (compose f acc))))
  (iter n id))

;; repeats the application of a function, divide n conquer way
(define (repeat2 f n)
  (define (iter f k acc)
    (cond ((= k 0) acc)
          ((even? k) (iter (compose f f) (/ k 2) acc))
          (else (iter f (- k 1) (compose f acc)))))
  (iter f n id))

;; increment function used for testing
(define (inc x) (+ x 1))

事实上，((repeat2 inc 1000000) 0) 比 ((repeat1 inc 1000000) 0) 快得多。我的问题是第二种方法在哪些方面比第一种方法更有效？重复使用相同的函数对象是否保留了存储空间并减少了创建新对象所花费的时间？

毕竟应用要重复n次，或者换个说法，x→((x+1)+1)不能自动缩减为x→( x+2)，对吧？

我在 DrScheme 4.2.1 上运行。

非常感谢。

Answer 1

你是对的，两个版本对 inc 的调用次数相同——但还有更多比你的代码中的开销。具体来说，第一个版本创建了 N 个闭包，而第二个只创建 log(N) 个闭包——如果创建闭包是大部分工作那么您会发现性能有很大差异。

您可以使用三件事来查看更多详细信息:

1. 使用DrScheme 的time 特殊形式来测量速度。除了它的时间执行了一些计算，它还会告诉你在 GC 上花费了多少时间。您会看到第一个版本正在执行一些 GC 工作，而第二个版本则没有。(嗯，确实如此，但它太小了，可能不会显示。)

2. 您的 inc 函数做的事情很少，您只测量循环开销。例如，当我使用这个错误的版本时:

   (define (slow-inc x)
     (define (plus1 x)
       (/ (if (< (random 10) 5)
            (* (+ x 1) 2)
            (+ (* x 2) 2))
          2))
     (- (plus1 (plus1 (plus1 x))) 2))
   

   两种用途之间的差异从大约 11 倍下降到 1.6。

3. 最后，试试这个版本:

   (define (repeat3 f n)
     (lambda (x)
       (define (iter n x)
         (if (zero? n) x (iter (sub1 n) (f x))))
       (iter n x)))
   

   它不做任何合成，它的工作原理大致是与第二个版本的速度相同。