为什么这个程序会消耗这么多内存？

Question

前段时间需要用算法解决一个KP问题，在haskell

我的代码如下所示：

stepKP :: [Int] -> (Int, Int) -> [Int]
stepKP l (p, v) = take p l ++ zipWith bestOption l (drop p l)
  where bestOption a = max (a+v)


kp :: [(Int, Int)] -> Int -> Int
kp l pMax = last $ foldl stepKP [0 | i <- [0..pMax]] l



main = print $ kp (zip weights values) 20000
       where weights = [0..2000]
             values = reverse  [8000..10000]

但是当我尝试执行它时（用 ghc 编译后，没有标志），它看起来很糟糕：这是命令 ./kp -RTS -s

的结果

1980100
   9,461,474,416 bytes allocated in the heap
   6,103,730,184 bytes copied during GC
   1,190,494,880 bytes maximum residency (18 sample(s))
       5,098,848 bytes maximum slop
            2624 MiB total memory in use (0 MB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0      6473 colls,     0 par    2.173s   2.176s     0.0003s    0.0010s
  Gen  1        18 colls,     0 par    4.185s   4.188s     0.2327s    1.4993s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    3.320s  (  3.322s elapsed)
  GC      time    6.358s  (  6.365s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    9.679s  (  9.687s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    2,849,443,762 bytes per MUT second

  Productivity  34.3% of total user, 34.3% of total elapsed

我认为我的程序需要 O(n*w) 内存，而它可以在 O(w) 中完成。 (w为总容量)

这是惰性计算占用太多 space 的问题还是其他原因？这段代码如何提高内存和时间效率？

Answer 1

我们可以将左折叠视为执行迭代，同时保留最后返回的累加器。

当有很多迭代时，一个问题是累加器在内存中可能变得太大。而且因为 Haskell 是惰性的，即使累加器是像 Int 这样的原始类型，这也会发生：在一些看似无辜的 Int 值背后可能潜伏着大量未决操作，在thunk 的形式。

这里严格的左折叠函数 foldl' 很有用，因为它确保在评估左折叠时，累加器将始终保持在 weak head normal form (WHNF) 中。

唉，有时候这还不够。 WHNF 只说评估已经进展到值的“最外层构造函数”。这对于 Int 来说已经足够了，但是对于像列表或树这样的递归类型，这并没有说明什么：thunk 可能只是潜伏在列表的更下方，或者下面的分支中。

这里就是这种情况，其中累加器是一个在每次迭代时重新创建的列表。每次迭代，foldl' 只评估列表直到 _ : _。未评估的 max 和 zipWith 操作开始堆积。

我们需要的是一种在每次迭代时触发累加器列表的完整评估的方法，该方法可以从内存中清除任何 max 和 zipWith thunk。这就是force accomplishes. When force $ something is evaluated to WHNF, something is fully evaluated to ，也就是说，不仅到最外层的构造函数，而且“深入”。

请注意，我们仍然需要 foldl' 以便在每次迭代时“触发”force。

为什么这个程序会消耗这么多内存？

why does this programm consume so much memory?

memory

haskell

lazy-evaluation

space-complexity