Haskell：代碼的兩個版本之間的速度差

我已經開始通過嘗試解決一些小問題來潛入Haskell。Haskell：代碼的兩個版本之間的速度差

我於「標準哈斯克爾友好」解決方案，我「極醜和Haskell不友好」版本之間有很大的性能差異（〜100-200x）絆倒了。

我敢肯定，對於同性戀者來說，這種表現上的差異有一個很好的理由，我錯過了，可以教我關於這個話題。

問題：查找數字串

內的最高5位數字都用在解決相同概念：產生所有5位數字，並找出最大。

優雅和快速的代碼

digit5 :: String -> Int 
digit5 = maximum . map (read . take 5) . init . tails

長得醜，而且速度很慢的代碼（一旦字符串大小大）

digit5' :: String -> String -> String 
-- xs - input string 
-- maxim - current maximal value 
digit5' xs maxim 
    | (length xs) < 5 = maxim 
    | y > maxim = digit5' (drop 1 xs) y -- use new detected maximum value 
    | otherwise = digit5' (drop 1 xs) maxim 
    where y = take 5 xs 

digit5 :: String -> Int 
digit5 xs 
-- return the original string if the input size is smaller than 6 
    | length (xs) < 6 = read xs 
    | otherwise = read $ digit5' xs "00000"

對於小的投入，我得到大致相同的執行時間，對於大的投入我開始看到很大的差異（對於44550個元素的輸入）：

Computation time for ugly version: 2.047 sec 
Computation time for nice version: 0.062 sec

我的膚淺對此的瞭解是，快速代碼是使用預先提供的高階功能。對於較慢的版本遞歸使用，但我認爲咬尾應該是可能的。但在天真的水平，對我來說似乎都做同樣的事情。

而較慢的功能確實比較對字符串，而不是將它們轉換爲數字，我也試着轉換字符串整數，但沒有任何大的改善

我試着使用GHC不帶任何標誌，並與編譯下面的命令：

ghc 
ghc -O2 
ghc -O2 -fexcess-precision -optc-O3 -optc-ffast-math -no- 
recomp 
stack runhaskell 
ghc -O3

對於重複性我加入的鏈接代碼contaning也測試向量的緣故：https://pastebin.com/kuS5iKgd

來源

2017-08-11 twosan

您有遞歸地在一個列表，並調用函數'length'在每一次迭代。長度是O（n）。您不小心向運行時添加了O（n^2）項。 – Carl

只是跳過警衛'|長度爲xs <5 = maxim'爲額外的模式'digit5'[] maxim = maxim'給我0.004秒而不是1.7秒。這比優雅的解決方案還要快。（讀取總是會消耗部分字符串的5個字節，而字符串比較可能只需要比較第一個字符）。 – Krom

與「慢」的版本問題是THI s的線路：

| length xs < 5 = maxim

此計算的xs長度，並且因爲Haskell的列表是單鏈表，這操作需要整個列表的完整遍歷，其爲O（n）。它發生在每一次迭代。並且有N次迭代。這使得整個過程O（n^2）。

另一方面，「快速」代碼只是線性的，在大型輸入上顯示得淋漓盡致。

如果只需更換與此問題的行：

| null xs = maxim

就會使整個事情只是線性的，這將是一樣快的「優雅」的解決方案。當然，這會導致額外的5次迭代，但是這種損失通過降低整體複雜性而得到補償。

，或者，可以使「優雅」的解決方案只是通過過濾掉5個字符或短尾巴一樣慢：

digit5 = maximum . map (read . take 5) . filter ((>= 5) . length) . tails

來源

2017-08-11 14:15:49

一些關於進一步加速的建議：String中的字典順序和Integer中的順序一致你可以完全跳過'read'。你也可以用一個奇特的技巧來避免'filter'：'zipWith const（tail xs）（drop 4 xs）'將產生'xs'的所有長度至少爲5的尾部。 –

（...或者你可以移動'read'，如'read。maximum。map（take 5）'，如果你想保持相同的類型，我在下面的時間測試中做了這個。）結果： 'digit5ReadFilter'，長度爲10000的String爲0.32s; 'digit5ReadZipwith'，0.04s; 'digit5LexFilter'，0.27s; 'digit5LexZipwith'甚至沒有註冊（報告0.00s）。 –

這是我在學習Haskell時遇到的第一個嚴重錯誤：由於'Int'太嚴格，所以'length xs <5'在這裏太嚴格了。如果使用像Data.Nat這樣的惰性數字類型，它將在5個元素後停止計算'xs'：'genericLength xs <（5 :: Nat）'。 'filter（（> =（5 :: Nat））。genericLength）'也是一樣。 –

Haskell：代碼的兩個版本之間的速度差

回答

相關問題