Haskell 自下而上的 DP space 泄漏

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 table 的每一行。理论上 GHC 应该能够优化掉 table 的所有旧行。然而，运行在大约 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 内存！我生成的 table 只有 10,000 Int，理论上我一次只需要一行！很明显，这是某种形式的 thunk 泄漏或其他 space 泄漏。分析表明 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 不是特别有经验，但我在这里束手无策。我确信这个问题的答案存在于 SO 上，但我对 Haskell 太陌生了，似乎无法找到它。

非常感谢您提供的任何帮助。我希望能准确解释我做错了什么，以后如何诊断它，以及如何修复它。

提前致谢。

编辑：

在遵循 Steven 的优秀建议并用未装箱的向量替换我的列表后，性能是......呃......显着改进：

> 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 传递给您 fold 的后续调用。由于您同时对列表中的多个位置感兴趣（也就是说，您将它的某些部分放在 zipWith 中），所以列表的大部分都保留在以前的迭代中。

这里你需要的结构是一个未装箱的向量。一个未装箱的矢量将确保一切都是最严格的，并且运行内存要少得多。

Haskell 自下而上的 DP space 泄漏

Haskell bottom-up DP space leak

haskell

space-leak