0

抱歉，如果这太具体了，我是新来的，不确定什么是合理的。几个小时以来，我一直在抨击这个问题，却没有任何表现。以下代码是我对竞争性编程问题的实现。

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 表的每一行。理论上 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，理论上我一次只需要一行！很明显，这是某种形式的 thunk 泄漏或其他空间泄漏。分析显示，run它消耗了 99% 的总运行时间和内存。进一步挖掘表明，其中 98% 都在zipWith通话中。有趣的是，zipWith min用我的自定义zipMin函数替换调用会产生显着的改进：

> 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% 的内存！我尝试了各种方法来完成这项工作。我知道(++)这通常是一个坏主意，所以我run用Data.Sequence.Seq Int... 替换了列表，它变得更慢并且使用了更多内存。我对 Haskell 不是特别有经验，但我在这里束手无策。我确信这个问题的答案存在于 SO 上，但我对 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
4

1 回答 1

1

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

您在这里需要的结构是一个未装箱的向量。未装箱的向量将确保一切都尽可能严格，并且将在更少的内存中运行。

于 2017-04-20T15:13:48.913 回答