haskell 内存不足，列表有限 [英] haskell running out of memory with finite lists

问题描述

我尝试运行中等输入时内存不足，例如:

I run out of memory trying to run moderate inputs such as this:

variation_models 15 25

也为 ncars 运行更高的数字似乎对速度和内存使用产生了巨大的影响.

also running higher numbers for ncars seems to make a huge difference in speed and memory usage.

放缓是意料之中的(有更多的东西可以比较)，但内存使用量的指数增长对我来说没有意义

The slowdown is expected (there are more things to compare), but the exponential increase of memory usage doesn't make sense to me

import Control.Monad

orderedq f [] = True
orderedq f (x:[]) = True
orderedq f (x:y:zs) = f x y && orderedq f (y:zs)

num_orderedq = orderedq (<=)

adds_up_to n xs = n == sum xs

both_conditions f g xs = f xs && g xs

variation_models ncars nlocations =
  filter (both_conditions (adds_up_to nlocations) num_orderedq) $ replicateM ncars [1..nlocations-ncars+1]

是什么导致了内存使用量的巨大差异?replicateM?

What is causing the large difference in memory usage? replicateM?

推荐答案

我想您已经在别处看到您的特定问题(创建求和为给定数字的整数的有序列表)使用替代算法可以更好地解决，而不是而不是过滤大量的整数列表.

I think you've seen elsewhere that your specific problem (creating ordered lists of integers that sum to a given number) is better solved using an alternative algorithm, rather than filtering a huge list of lists of integers.

然而，回到你最初的问题，可以构造一个等价的:

However, getting back to your original issue, it is possible to construct an equivalent of:

replicateM p [1..n]

以指数时间运行(当然)但空间不变.

that runs in exponential time (of course) but constant space.

问题在于这个表达式或多或少等价于递归:

The problem is that this expression is more or less equivalent to the recursion:

badPower 0 _ = pure []
badPower p n = [x:xs | x <- [1..n], xs <- badPower (p-1) n]

所以，在列表推导中，对于每一个选中的x，需要从头开始重新生成整个列表badPower (p-1) n.GHC 很明智地决定保留 badPower (p-1) n 以便不需要每次都重新计算.因此，badPower pn 调用需要将整个 badPower (p-1) n 列表保存在内存中，这已经占了 n^(p-1) 元素和指数内存使用，即使不考虑 badPower (p-2) n 等

So, in the list comprehension, for each selected x, the whole list badPower (p-1) n needs to be re-generated from the start. GHC, sensibly enough, decides to keep badPower (p-1) n around so it doesn't need to be recomputed each time. So, the badPower p n call needs the entire badPower (p-1) n list kept in memory, which already accounts for n^(p-1) elements and exponential memory use, even without considering badPower (p-2) n, etc.

如果你只是翻转隐式循环的顺序:

If you just flip the order of the implicit loops around:

goodPower 0 _ = pure []
goodPower p n = [x:xs | xs <- goodPower (p-1) n, x <- [1..n]]

这解决了问题.即使列表 goodPower (p-1) n 是大"的，我们还是取它的第一个元素，对 x 的每个值使用它 n 次code> 然后可以丢弃它并移动到下一个元素.因此，goodPower (p-1) n 可以在使用时被垃圾收集.

That fixes the problem. Even though the list goodPower (p-1) n is "big", we take it's first element, use it n times for each value of x and then can discard it and move to the next element. So, goodPower (p-1) n can be garbage collected as it's used.

请注意，goodPower 以与 badPower 不同的顺序生成元素，列表的第一个坐标变化最快，而不是最后一个.(如果这很重要，您可以map reverse $ goodPower ....虽然reverse慢"，但它仅适用于此处的短列表.)

Note that goodPower generates the elements in a different order than badPower, with the first coordinate of the lists varying fastest, instead of the last. (If this matters, you can map reverse $ goodPower .... While reverse is "slow", it's only being applied to short lists here.)

无论如何，以下程序(实际上)永远运行，但在恒定空间中运行:

Anyway, the following program runs (practically) forever, but does so in constant space:

power :: Int -> [a] -> [[a]]
power 0 _ = [[]]
power p lst = [x:xs | xs <- power (p-1) lst, x <- lst ]

main = do
  print $ length (power 15 [1..11])

这篇关于haskell 内存不足，列表有限的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！