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

为ncar设置更高的数字似乎会在速度和内存使用方面产生巨大的差异.

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 p n调用需要将整个badPower (p-1) n列表保存在内存中，即使不考虑badPower (p-2) n等，该列表也已经考虑了n^(p-1)元素和指数内存使用.

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次，然后可以将其丢弃并移至下一个元素.因此，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屋！