這兩種球拍功能在速度/效率方面有什麼區別？

(define (myminus x y) 
    (cond ((zero? y) x) 
     (else (sub1 (myminus x (sub1 y)))))) 

(define (myminus_v2 x y) 
    (cond ((zero? y) x) 
     (else (myminus_v2 (sub1 x) (sub1 y)))))

請評論這些功能之間的差異，如何在每次遞歸調用時在堆棧上需要多少內存。另外，您希望哪個版本更快，爲什麼？這兩種球拍功能在速度/效率方面有什麼區別？

謝謝！

來源

2013-10-18 dahui

他們都應該有幾個步驟與y成比例。

第二個是一尾調用意思解釋器可以做尾消除這意味着它佔用堆棧上的恆定空間而在第一堆棧的大小正比於Y.

來源

2013-10-18 18:23:05 WorBlux

有沒有必要包裝它。 'racket'確實可以調用外部函數的優化。 – Sylwester

@Sylwester相關知識，編輯反映 – WorBlux

感謝您的回答 – dahui

myminus創建y延續到sub1遞歸評估的內容。這意味着您可以消耗球拍內存限制，從而使程序失敗。在我的試驗中，即使只有一千萬個不會成功使用DrRacket中的標準128MB限制。

myminus_v2是tail recursive以來racket具有相同的屬性，什麼scheme要求，即尾調用將被優化到一個跳轉，而不是成長的堆棧，y可以是任意大小，即只可用內存和處理能力是限制的大小。

您的程序是peano arithmetic的很好例子。

來源

2013-10-18 18:33:25 Sylwester

感謝您的回答！ – dahui

球拍支持深度遞歸，所以第一個不會得到一個特殊的「堆棧溢出」錯誤，它只會耗盡內存。用於實現延續的技術通常免費提供深度遞歸。 –

@RyanCulpepper你是對的。我已經多次看到它在所有內存中徘徊，從不堆棧溢出。更新。 – Sylwester

這兩種球拍功能在速度/效率方面有什麼區別？

回答

相關問題