的執行情況（^）

我讀的標準哈斯克爾庫的實現（^）的代碼：的執行情況（^）

(^) :: (Num a, Integral b) => a -> b -> a 
x0^y0 | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
     | y0 == 0 = 1 
     | otherwise = f x0 y0 
    where -- f : x0^y0 = x^y 
      f x y | even y = f (x * x) (y `quot` 2) 
       | y == 1 = x 
       | otherwise = g (x * x) ((y - 1) `quot` 2) x 
      -- g : x0^y0 = (x^y) * z 
      g x y z | even y = g (x * x) (y `quot` 2) z 
        | y == 1 = x * z 
        | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

現在這部分，其中G是定義似乎有些奇怪我爲什麼不只是實現它像這個：

expo :: (Num a ,Integral b) => a -> b ->a 
expo x0 y0 
    | y0 == 0 = 1 
    | y0 < 0 = errorWithoutStackTrace "Negative exponent" 
    | otherwise = f x0 y0 
    where 
     f x y | even y = f (x*x) (y `quot` 2) 
       | y==1 = x 
       | otherwise = x * f x (y-1)

但的確如此插入3^1000000顯示（^）大約比展會快0,04秒。

爲什麼(^)比expo更快？

來源

2016-07-26 user3726947

這當然不是一個非常戲劇化的問題，但是我認爲你的版本效率低下的原因是它將小數字「x」與f的一個大的結果進行了很多倍增。標準版本通過在遞歸調用之後一直髮送剩餘因子來生成更平衡的乘法樹。 – leftaroundabout

'g'是尾遞歸，而最後一個'f'不是。我想這裏很重要。 – chi

函數是尾遞歸的，如果遞歸調用的返回值按原樣返回，不做進一步處理。在expo,f不是尾遞歸，因爲otherwise = x * f x (y-1)：在返回之前返回值f乘以x。 f和g中的(^)都是尾遞歸，因爲它們的返回值是未經修改而返回的。

這是爲什麼？尾遞歸函數可以比一般遞歸函數更高效地實現。因爲編譯器不需要爲遞歸調用創建新的上下文（棧幀，你有什麼），所以它可以重用調用者的上下文作爲遞歸調用的上下文。這樣可以節省很多調用函數的開銷，就像調用一個函數比調用函數更有效。

來源

2016-07-26 13:36:47 chepner

每當你看到在標準庫中的麪包和奶油的功能，它的古怪實現，其原因幾乎總是「因爲做這樣的觸發一些特殊的關鍵性能優化[可能在不同版本的編譯器]「。

這些奇怪的解決方法通常是「強制」編譯器注意到某些特定的重要優化是可能的（例如，強制特定參數被認爲是嚴格的，允許工作者/包裝器轉換，無論如何）。通常一些人編譯了他們的程序，發現它很慢，向GHC開發者抱怨，他們看着編譯後的代碼，並認爲「哦，GHC沒有看到它可以嵌入第三個工作人員的功能......我如何解決這個問題？「結果是，如果稍微改寫代碼，那麼所需的優化就會觸發。

你說你測試過了，速度差別不大。你沒有說是什麼類型的。（指數是Int還是Integer？基數是多少？這很有可能在一些不太明顯的情況下產生顯着差異。）

偶爾函數也會被奇怪地實現以保持嚴格性/懶惰保證。（例如，庫規範說它必須以某種方式工作，並且以最明顯的方式實現它會使功能比規範聲明更嚴格/更不嚴格。）

我不知道這是怎麼回事具體函數，但我會建議@chi可能是東西。

來源

2016-07-26 13:08:23 MathematicalOrchid

沒有什麼ghc關於代碼的具體細節，它只適用於任何編譯器。 – augustss

作爲編寫代碼的人，我可以告訴你爲什麼它很複雜。 :) 這個想法是尾遞歸得到循環，並且執行最小數量的乘法。我不喜歡它的複雜性，所以如果你找到更優雅的方式，請提交一份錯誤報告。

來源

2016-07-26 14:39:46 augustss

我在這段代碼中看到'even y'後面加上'y''''''''。如果這個部門是通過一個「quotRem」調用完成的話，它的性能是否會有所提高？ – Cactus

我對此表示懷疑。一個是位測試指令，另一個是移位。 – augustss

如何換班，然後進行檢查標誌或類似？或者我在這裏以6502的方式思考？ – Cactus

的執行情況（^）

回答

相關問題