Haskell的foldl'没有节省预期的空间

Question

尝试实现背包问题的直观动态规划算法。显然，这种方法使用了大量内存，因此我正在尝试优化所使用的内存。我只是简单地尝试在内存中仅存储表格的前一行，以便计算下一行等。起初，我认为我的实现很稳固，但它仍然会耗尽内存，就像一个设计用于存储整个表格的实现一样。所以接下来我想也许我需要使用foldl'而不是foldr，但这并没有产生任何区别。我的程序继续占用内存，直到我的系统用完为止。

因此，我有两个具体的问题：

1. 是什么导致我的代码使用了所有的内存？我认为使用fold是很聪明的，因为我假设只有累加器的当前值会被存储在内存中。 2. 实现我的目标的正确方法是什么？即仅在内存中存储最近的一行？我不一定需要代码，也许只需要一些有用的函数和数据类型。更普遍地说，了解Haskell中内存使用的技巧和技术有哪些？

以下是我的实现：

data KSItem a = KSItem { ksItem :: a, ksValue :: Int, ksWeight :: Int} deriving (Eq, Show, Ord)
dynapack5 size items = finalR ! size
  where
    noItems = length items
    itemsArr = listArray(1,noItems) items
    row = listArray(1,size) (replicate size (0,[]))
    computeRow row item =
      let w = ksWeight item
          v = ksValue item
          idx = ksItem item
          pivot = let (lastVal, selections) = row ! w
                  in if v > lastVal 
                     then (v, [idx])
                     else (lastVal, selections)
          figure r c =
              if (prevVal + v) > lastVal
              then (prevVal + v, prevItems ++ [idx])
              else (lastVal, lastItems)
              where (lastVal, lastItems) = (r ! c)
                    (prevVal, prevItems) = (r ! (c - w))
          theRest = [ (figure row cw) | cw <- [(w+1)..size] ]
          newRow = (map (row!) [1..(w-1)]) ++ 
                   [pivot] ++
                   theRest
      in listArray (1,size) newRow
    finalR = foldl' computeRow row items

在我的理解中，这段代码的作用是将第一行初始化为(0,[])...如有必要，则重复此过程，然后启动折叠操作，其中下一行是基于提供的行计算得出的，并且此值成为累加器。我没有看到越来越多的内存被消耗的地方...

随机想法：如果我在累加器上使用\\操作符会怎样？

- parker.sikand

---

foldl' 在每一步都对累加器进行 WHNF 求值。但这是否足够取决于累加器中存储的值。看起来它是一个包含大量元组的数组。这些必须是普通的箱式数组，因此强制其中一个进行 WHNF 将确保分配该数组并初始化每个单元格 - 以指向（可能未求值的）thunk 的指针。 - Carl

好的，我认为你的意思是即使我在代码中只使用一个数组，实际上每次折叠迭代中数组的每个元素都会消耗内存（这正是我想避免的）。我猜这是有道理的，但我原以为之前的数组会被垃圾回收，因为它不再需要。 - parker.sikand

另外，现在我已经了解了一些关于WHNF的知识，我认为我的代码问题是我在累加器中使用元组内部的列表，对吗？因为该列表直到我在函数外部尝试从中读取时才会被完全评估，所以它仍然需要将所有内容存储在内存中“以防万一”它需要评估该列表。我的WHNF和惰性理解正确吗？ - parker.sikand

你能给一些输入的例子吗？ - Markus1189

Answer 1

正如Tom Ellis所说，对数组使用force可以解决空间问题。但是，这种方法非常慢，因为每次调用force时，它都会遍历数组中所有列表，从头到尾。因此，我们应该根据需要进行强制操作：

let res = listArray (1,size) newRow in force (map fst $ elems res) `seq` res

这修复了空间泄漏问题，并且非常快。

如果您想将空间效率提升到逻辑的下一个步骤，您可以使用索引的位集而不是项目列表。整数在此处很适合此工作，因为它们会自动调整大小以容纳最高设置位。此外，对于整数，强制执行是直观的：

import qualified Data.Vector as V -- using this instead of Array cause I like it more
import Data.List
import Control.Arrow
import Data.Bits
import Control.DeepSeq

data KSItem a = KSItem { ksItem :: a, ksValue :: Int, ksWeight :: Int} deriving (Eq, Show, Ord)

dynapack5' :: Int -> [KSItem a] -> (Int, Integer)
dynapack5' size items = V.last solutions where
    items' = [KSItem i v w | (i, KSItem _ v w) <- zip [0..] items]

    solutions = foldl' add (V.replicate (size + 1) (0, 0::Integer)) items'

    add arr (KSItem item currVal w) = force $ V.imap go arr where
        go i (v, is) | w < i && v' > v = (v', is')
                     | otherwise       = (v, is)
            where (v', is') = (+currVal) *** (`setBit` item) $ arr V.! (i - w)

- András Kovács

---

谢谢。我自己不会想到使用 Control.Arrow (***)，但是看到它像这样实现后就更有意义了。 - parker.sikand

@parker.sikand 另外，另一个提示：您可以按价值密度递减的顺序对项目列表进行排序。这将使启发式最佳项目具有最低的索引，从而减小位集的大小。 - András Kovács

Answer 2

Data.Array在其元素中是非严格的，因此即使foldl'强制它在每次循环时进入WHNF，内容也不会被评估。最简单的修复方法是导入Control.DeepSeq并更改。

in listArray (1,size) newRow

到

in force (listArray (1,size) newRow)

每次循环都做了比严格必要更多的工作，但可以完成任务。

不幸的是，你不能在这里仅仅替换成未装箱的数组，因为你的数组包含一个包含列表的元组。

- Tom Ellis

---

这减缓了内存增长但并未停止它 :( 从我的理解来看，理论上这个答案是正确的，但在我的情况下，我的算法仍然使用了大量的内存，我认为这是由于我试图累加的列表所致。感谢您指引我正确的方向。 - parker.sikand

这很令人惊讶。它在我的一些测试数据上停止了内存增长。你确定不是程序的另一部分导致了增长，或者只是随着列表被附加到其中，foldl'包含的内存自然增加？ - Tom Ellis