編寫函數的兩種方法，效率如何不同？

Question

讓f將一個值轉換爲另一個值，然後我正在寫一個重複n次轉換的函數。

我已經提出了兩種不同的方式：

• 一個是 字面上應用函數N 次明顯的方式，所以重複（F，4）指X→ F（ F（F（F（X））））
• 另一種方法是從 快速方法啓發用於供電，這意味着 將問題分爲2個 問題是一半大每當n是偶數時，。所以重複（F，4） 裝置X→G（G（X））其中G（X）= F（F（X））

起初我以爲第二方法不會提高效率。在一天結束時，我們仍然需要應用n次，不是嗎？在上面的例子中，g仍然會被翻譯成從沒有任何進一步的簡化，對吧？

但是，當我試用這些方法時，後一種方法明顯更快。

;; 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個閉包，而第二個創建了N個閉包，而第二個創建了只有日誌（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))) 
   

   它沒有做任何組合物，以及它的工作原理大致 相同的速度你的第二個版本。

Answer 2

第一種方法本質上應用函數n次，因此它是O（n）。但第二種方法實際上並沒有將函數應用n次。每當重複2被調用時，每當n是偶數時，它將n分開2。因此，大部分時間問題的大小減半，而不是僅減1。這給出了O（log（n））的總體運行時間。

由於Martinho Fernandez建議，關於exponentiation by squaring explains的維基百科文章非常清楚。