两种组合函数的方法,效率有多不同?

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

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

• 重复(f,4) 手段 f(f(f)(f(x)))
• 快速供电方法,这意味着 问题只有一半大 只要n是偶数。所以 重复(f,4) 手段 g(x)=

起初我以为第二种方法不会提高那么多效率。最终,我们仍然需要申请f n次,不是吗?在上述示例中, 克 没有任何进一步的简化,对吧?

然而,当我尝试这些方法时,后一种方法明显更快。

;; 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+2) 正确的

我正在运行DrScheme 4.2.1。

非常感谢