哈斯克爾自下而上的DP空間泄漏

道歉，如果這太具體，我在這裏是新的，不完全確定什麼是合理的。我幾個小時一直在抨擊這個問題，沒有任何可以證明的問題。下面的代碼是我實現一個有競爭力的編程問題。哈斯克爾自下而上的DP空間泄漏

module Main where 

import Data.List (foldl', groupBy) 
import Debug.Trace 

type Case = (Int, [(Int, Int)]) 
type Soln = Int 

main = interact handle 

handle :: String -> String 
handle = fmt . solve . parse 

fmt :: Soln -> String 
fmt s = (show s) ++ "\n" 

parse :: String -> Case 
parse s = (l, fs) 
    where 
    (l:_:fs') = (map read) $ words s 
    fs = pairs fs' 

pairs :: [a] -> [(a, a)] 
pairs [] = [] 
pairs (a:b:s) = (a, b):(pairs s) 

solve :: Case -> Soln 
solve [email protected](l, fs) = last $ foldl' run [0..l] f 
    where 
    f = concat $ map rep $ map combine $ groupBy samev fs 
    samev a b = (snd a) == (snd b) 
    combine a = (sum $ map fst $ a, snd $ head $ a) 
    rep (n, v) = replicate (min n (l `div` v)) v 

run :: [Int] -> Int -> [Int] 
run b v = (take v b) ++ (zipWith min b (drop v b)) 
-- run b v = (take v b) ++ (zipMin b (drop v b)) 

zipMin :: [Int] -> [Int] -> [Int] 
zipMin [] _ = [] 
zipMin _ [] = [] 
zipMin (a:as) (b:bs) = (min a b):(zipMin as bs)

的意圖是，這就像一個自下而上動態編程溶液使用摺疊在解決產生從先前的DP表的每一行。理論上，GHC應該能夠優化表格的所有舊行。然而，在一箇中等大的投入運行此程序大約l = 2000和length f = 5000，我得到這個：

> time ./E < E.in 
0 
1.98user 0.12system 0:02.10elapsed 99%CPU (0avgtext+0avgdata 878488maxresident)k 
0inputs+0outputs (0major+219024minor)pagefaults 0swaps

這是使用878 MB的內存峯值！我生成的表格只有10,000個Ints，理論上我一次只需要一行！看起來很明顯，這是某種形式的垃圾泄漏或其他空間泄漏。分析顯示run正在消耗總運行時間和內存的99％。挖掘進一步表明，98％是在撥打zipWith。有趣的是，我的自定義更換調用zipWith minzipMin功能產生顯著改善：

> time ./E < E.in 
0 
1.39user 0.08system 0:01.48elapsed 99%CPU (0avgtext+0avgdata 531400maxresident)k 
0inputs+0outputs (0major+132239minor)pagefaults 0swaps

這只是70％的運行時間，以及60％的記憶！我盡了各種努力來完成這項工作。我知道(++)通常是一個壞主意，所以我用Data.Sequence.Seq Int替換了run中的列表...並且它變得更慢並且使用更多內存。我對Haskell並不是特別有經驗，但我在這裏的智慧就此結束。我確信這個問題的答案存在一些問題，但對於Haskell來說，我看起來太新了，以至於無法找到它。

任何幫助你可以提供非常感謝。我很想解釋我做錯了什麼，將來如何診斷它，以及如何解決它。

在此先感謝。

編輯：

以下史蒂芬的優秀建議，並與拆箱載體表現......呃更換我的名單後... signficantly改進：

> time ./E < E.in 
0 
0.01user 0.00system 0:00.02elapsed 80%CPU (0avgtext+0avgdata 5000maxresident)k 
24inputs+0outputs (0major+512minor)pagefaults 0swaps

來源

2017-04-20 Gozz

因此，通過使用foldl'您已確保累加器將處於WHNF中。將列表放在WHNF中僅評估列表的第一個元素。列表的其餘部分以thunk的形式存在，並將作爲thunk傳遞給隨後的摺疊調用。由於您一次對列表中的多個職位感興趣（也就是說，您正在將其中的某些部分放在zipWith中），因此大部分列表都將與以前的迭代保持一致。

您需要的結構是一個未裝箱的向量。一個unboxed的矢量將確保一切都是最嚴格的，並且將運行在更少的內存中。

來源

2017-04-20 15:13:48

感謝您的快速回復。這是一個夢幻般的，清晰的解釋。我有幾個後續問題： 1.爲什麼編譯器無法對此進行優化？這似乎是一個成熟的目標。 2.是否有任何實際的方法來做到這一點與標準分配？我覺得這個解決方案令人滿意，但不幸的是，競爭服務器不支持矢量包。再次感謝。 – Gozz

這將是一個相當複雜的優化級別。有嚴格的分析階段，但由於圖靈的完整性，你不可能總是做到正確。你可以檢查一個嚴格的列表包是否可用，或者製作你自己的嚴格的列表類型的數據SList a = Cons！a！（SList a）|無'，如果頭部被強制，這將強制整個列表。您還可以檢查deepseq是否可用，您可以使用它來強制對常規列表進行充分評估。 –

非常有趣，謝謝你的時間。這是一個黑客，但我發現Data.IntMap.Strict實際上足夠快，可以在這場比賽中工作。再次感謝你的幫助。 – Gozz

哈斯克爾自下而上的DP空間泄漏

回答

相關問題