可以對此Haskell代碼進行哪些優化？

--Returns last N elements in list 
lastN :: Int -> [a] -> [a] 
lastN n xs = let m = length xs in drop (m-n) xs 

--create contiguous array starting from index b within list a 
produceContiguous :: [a] -> Int -> [[a]] 
produceContiguous [] _ = [[]] 
produceContiguous arr ix = scanl (\acc x -> acC++ [x]) [arr !! ix] inset 
    where inset = lastN (length arr - (ix + 1)) arr 

--Find maximum sum of all possible contiguous sub arrays, modulo [n] 
--d is dummy data 
let d = [1,2,3,10,6,3,1,47,10] 
let maxResult = maximum $ map (\s -> maximum s) $ map (\c -> map (\ac -> (sum ac)`mod` (last n)) c) $ map (\n -> produceContiguous d n) [0..(length d) -1]

我是一個Haskell福利局 - 短短几天到它。如果我做的事情顯然是錯誤的，whoopsies可以對此Haskell代碼進行哪些優化？

來源

2016-02-05 jaggedGoofy

如果代碼正常工作，而您只是想要改進建議，則應該在codereview.stackexchange.com上發帖。否則，您需要明確指出您想解決的問題。 – chepner

這是最大的子陣列問題的一個奇怪的變化。我猜測模n'位是爲了打破標準（高效）解決方案而設計的。我不確定是否有類似的有效解決方案，但我對此表示懷疑。一般來說，模塊化算術和最大化並不能很好地齧合。 – dfeuer

在這類問題中，你應該總是包含一個規範，用簡單的話來說明程序應該做什麼。這將提供更多的可見性 - 我想大多數讀者只會看到一段代碼並停止閱讀。代碼中有一個非常簡短的代碼，在'd'上面的註釋中，但是它在噪聲中丟失了。 – chi

您可以通過觀察map sum (produceContiguous d n)（其運行時Ω提高運行了很多（m^2），可以摺疊爲scanl (+) 0 (drop n d)（其具有運行時間O（m）），因此您可以在每個迭代中追加到acc的末尾，因此可能需要O（m^3）時間。我還會做很多其他的風格變化，但這是我能想到的主要算法。

清理所有風格的東西，我可能會寫：

import Control.Monad 
import Data.List 
addMod n x y = (x+y) `mod` n 
maxResult n = maximum . (scanl (addMod n) 0 <=< tails)

在ghci的：

*Main> jaggedGoofyMax 100 [1..1000] 
99 
(12.85 secs, 24,038,973,096 bytes) 
*Main> dmwitMax 100 [1..1000] 
99 
(0.42 secs, 291,977,440 bytes)

這裏沒有顯示是版本的jaggedGoofyMax有只有我提到的優化在我應用的第一段中，運行時/內存使用情況統計信息略好於在ghci中運行時的dmwitMax（但基本上與dmwitMax相同，兩者均編譯爲wi th -O2）。所以你可以看到，即使是適度的輸入尺寸，這種優化也可以產生很大的差異。

來源

2016-02-05 03:06:03

我建議使用'<= <'代替'> =>'保持所有成分以相同的方式流動。 – dfeuer

這就是Haskell的迷人之處，它吸引了我。感謝您的解釋 – jaggedGoofy

@dfeuer好主意;完成。 –

可以對此Haskell代碼進行哪些優化？

回答

相關問題