Haskell自下而上的DP空间泄漏

Question

道歉，如果这太具体了，我在这里是新手，不确定什么是合理的。我一直在殴打这个问题数小时，没有什么可显示的。以下代码是我实施竞争性编程问题。

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 c@(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表的每一行，使用solve中的折叠。从理论上讲，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个INT，从理论上讲，我一次只需要一行！显然，这是某种形式的Thunk泄漏或其他空间泄漏。分析表明，run消耗了总运行时和内存的99％。进一步挖掘表明，其中98％是在zipWith调用中。有趣的是，用我的自定义zipMin函数替换对zipWith min的呼叫会产生重大改进：

> 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并不是特别的经验，但我在这里的智慧。我确定这个问题的答案有些存在，但是我太陌生了，无法找到它，看来。

。

您可以提供的任何帮助都非常感谢。我想对我做错了什么，如何诊断将来以及如何修复它的确切解释。

预先感谢。

编辑：

遵循史蒂文的出色建议并用未盒子的矢量代替我的列表后，性能是...嗯... 明显地改进了：

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

Answer 1

因此，通过使用foldl'，您确保累加器将在WHNF中。在WHNF中放置列表仅评估列表的第一个元素。列表的其余部分作为thunk存在，并将以thunk的身份传递给您随后的折叠呼叫。由于您一次对列表中的多个位置感兴趣(也就是说，您在zipWith中丢弃了其中的某些部分(，从以前的迭代中保留了大部分列表。

您需要的结构是一个未包装的向量。一个未框的向量将确保一切都最大程度地严格，并且在内存少得多。