考慮這個整數素數分解的微不足道的演算法n：設d'是n最后找到的除數。最初，設定d'=1. 找出最小除數d>d'的n，并找到最大值e，使得分歧。附加到答案并重復 上的程序。最后，當變為 1時停止。為簡單起見，讓我們忽略數學優化，例如 stop at等。denden/densqrt n
我已經通過兩種方式實作了它。第一個生成除法“嘗試”串列，然后按除數對成功的進行分組。例如，對于n=20，我們首先生成[(2,20),(2,10),(2,5),(3,5),(4,5),(5,5),(5,1)]，然后將其轉換為所需的[(2,2),(5,1)]usinggroup和其他庫函式。
第二個實作是顯式遞回，它e一路跟蹤指數，一旦達到最大值就附加到答案，繼續尋找“下一個” ，依此類推。deed
問題 1：盡管有以下情況，為什么第一個實作的運行速度比第二個慢：
- 兩種實作都執行
div演算法的核心步驟，執行次數大致相同。 - 懶惰評估（和融合？）的效果是上面說明的長串列永遠不必首先實作。正如您在下面的代碼中看到的那樣，
divTrials n我正在談論的串列由一系列高階函式轉換。在那，我認為這部分map (\xs-> (head xs,length xs)) ... group應該告訴編譯器串列只是中間的：
{-# OPTIONS_GHC -O2 #-}
module GroupCheck where
import Data.List
import Data.Maybe
implement1 :: Integral t=> t -> [(t,Int)] -- IMPLEMENTATION 1
implement1 = map (\xs-> (head xs,length xs)).factorGroups where
tryDiv (d,n)
| n `mod` d == 0 = (d,n `div` d)
| n == 1 = (1,1) -- hack
| otherwise = (d 1,n)
divTrials n = takeWhile (/=(1,1)) $ (2,n): map tryDiv (divTrials n)
factorGroups = filter (not.null).map tail.group.map fst.divTrials
implement2 :: Show t => Integral t => t -> [(t,Int)] -- IMPLEMENTATION 2
implement2 num = keep2 $ tail $ go (1,0,1,num) where
range d n = [d 1..n]
nextd d n = fromMaybe n $ find ((0==).(n`mod`)) (range d n)
update (d,e,de,n)
| n `mod` d == 0 = update (d,e 1,de*d,n`div`d)
| otherwise = (d,e,de,n)
go (d,e,de,1) = [(d,e,de,1)]
go (d,e,de,n) = (d,e,de,n) : go (update (nextd d n,0,1,n))
keep2 = map (\(d,e,_,_)->(d,e))
main :: IO ()
main = do
let n = 293872
let ans1 = implement1 n
let ans2 = implement2 n
print ans1
print ans2
剖析告訴我們，tryDiv并divTrials一起吃了>的整個執行時間99％：
> stack ghc -- -main-is GroupCheck.main -prof -fprof-auto -rtsopts GroupCheck
> ./GroupCheck RTS -p >/dev/null && cat GroupCheck.prof
GroupCheck RTS -p -RTS
total time = 18.34 secs (18338 ticks @ 1000 us, 1 processor)
total alloc = 17,561,404,568 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
implement1.divTrials GroupCheck GroupCheck.hs:12:3-69 52.6 69.2
implement1.tryDiv GroupCheck GroupCheck.hs:(8,3)-(11,25) 47.2 30.8
問題 1.5：那么……這些函式有什么不好？還，
問題 2：在更一般的情況下，必須從非遞減序列中聚合相同元素的連續塊，implement2如果我們想要速度，我們應該采用笨重的方式嗎？（同樣，忽略特定領域的優化。）
還是我完全錯過了一些明顯的東西？謝謝！
uj5u.com熱心網友回復：
只是為了建立一個基線，我在一個稍大的起始數字上運行你的程式（所以time沒有列印出 0.00s）。我選擇n = 2938722345623沒有特別的原因。這是開始調整之前的時間：
ans1：與無窮大沒有區別（我寫完了整個答案，它仍在運行，總共大約 26 分鐘）
ans2：2.78 秒
首先要嘗試的是調整這一行：
divTrials n = takeWhile (/=(1,1)) $ (2,n): map tryDiv (divTrials n)
這看起來是一個很自然的定義，但事實證明 GHC 從不記憶函式呼叫。因此，如果您想創建一個根據自身遞回定義的串列，則不得在遞回中進行函式呼叫。就是這樣：
divTrials n = xs where xs = takeWhile (/=(1,1)) $ (2,n): map tryDiv xs
正是這種變化將時間縮短到 7.85 秒。仍然降低了大約 3 倍，但要好得多。
不太明顯的問題就在這里：
factorGroups = filter (not.null).map tail.group.map fst.divTrials
將group如此早的中斷融合，導致該中間串列實際上被物化。這意味著分配和釋放大量的 cons 單元和元組。這是一個具有相同精神的實作，但在 之前做了更多的作業group：
tryDiv d n
| n `mod` d == 0 = d : tryDiv d (n `div` d)
| n == 1 = []
| otherwise = tryDiv (d 1) n
factorGroups = group . tryDiv 2
有了這個，我們下降到 2.65 秒——比 略快ans2，盡管我只對每個都做了一個測驗，所以很可能只是測量噪聲。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/330628.html