Haskell的方法太慢

我寫在Haskell一個函數，它看起來像這樣：Haskell的方法太慢

maxSumme :: [[Int]] -> Int 
maxSumme [] = 0 
maxSumme (x:l) = if subSumme x < maxSumme l then maxSumme l else subSumme x 

subSumme :: [Int] -> Int 
subSumme [] = 0    
subSumme (x:l) = x + subSumme(l) 

-- function call 
maxSumme [[7,2,4],[5,8,1],[7,9,2]] -- with 25 innerLists

我測試，但這種方法是非常緩慢。如果我用一個包含3個項目的25個innerLists列表調用它，計算maxSumme需要一分鐘時間。那不正常不是嗎？我一定犯了一個錯誤，但是我找不到它。我怎樣才能優化我的方法？有沒有更快的方法來做到這一點？

編輯：我覺得發現了錯誤。我確信它是maxSumme l then maxSumme l。我每次循環遍歷列表，並且需要很長時間。但實際上我不知道如何避免這種情況。

來源

2013-12-13 Cilenco

'let'解除'maxSumme l'將時間複雜度從指數式降低到線性。懶惰語言中的CSE並不總是可行，但在這種情況下。 –

我是Haskell的新手。左提升和CSE意味着什麼？如果我可以將它改變爲線性函數，那將是非常好的。 – Cilenco

他意味着在'let ssx = subSumme x in ...'中重複'subSumme x'的代碼（並且用'ssx'替換'subSumme x'）。這就像定義一個新的變量一樣。 'maxSumme l'也是一樣。 CSE的意思是「共同的子表達式消除」。如果編譯器意識到這些表達式是相同的，那麼它可以完成我們剛剛描述的內容，並將代碼中的_hell_視爲代碼，但由於某種原因它沒有（可能並不總是像Philip所建議的那樣）。 – Guido

所以你已經找到了問題的功能。這是因爲對於每個名單，您多次致電subSumme。你可以做的反而是地圖subSumme傳遞給每個maxSumme名單，然後找出最大的數字：

maxSumme xs = maximum $ map subSumme xs

如果您不能使用maximum，你需要弄清楚如何實現自己= P

爲了解釋$運營商，這意味着始終運行一切向左前的權利。這使得像

f (g (h (i (j (k (l x))))))

表達成

f $ g $ h $ i $ j $ k $ l x

被警告，這得到棘手與多個參數的函數。這不會編譯

map $ (1+) $ replicate 10 1

，因爲它是一樣

map ((1+) (replicate 10 1)) 
= map ((1+) replicate 10 1)) 
= map (1 + replicate 10 1) 
= map (1 + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) 
     ^------ Can't add a number to a list!

但是你可以做

map (1+) $ replicate 10 1

基本上，它是是不需要用括號在很多情況下，。

來源

2013-12-13 00:18:02 bheklilr

上，GHC 7.6似乎也能執行CSE謝謝你的工作非常棒！我知道最大的功能，但我不知道$操作符。它是爲了什麼？ – Cilenco

@Cilenco：它幾乎不做任何事情（事實上'（$）= id'！），但是被解析爲低優先級的運算符。簡單閱讀它就可以知道所有需要它們的東西，無論是左邊還是右邊。在這種情況下，最大（map subSumme xs）'。 – leftaroundabout

'subSumme'實際上與Prelude的標準'sum'功能相同，只是平臺的版本更好。所以@ bheklilr的解決方案可以進一步改進爲'maxSumme xs =最大$地圖總和xs'。 –

Haskell的方法太慢

回答

相關問題