haskell - 为什么 [x|x<-[1..10]] 方法在 Haskell 中这么慢？

Question

为什么这样的事情在 Haskell 中运行得非常慢？

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

print $ length test

大约只有 10^8数字跑，应该是一眨眼就跑完了，但又好像永远跑，差点死机。

Answer 1

您是在 ghci 中还是在已编译的程序中运行它？它有很大的不同。

如果在 ghci 中，则 ghci 将保留 test 的计算值以防您以后想使用它。通常这是一个好主意，但在这种情况下，test是一个巨大的值(value)，无论如何重新计算都很便宜。多大？对于初学者来说，它是一个包含 10^8 个元素的列表，并且(在 64 位系统上)一个列表每个元素花费 24 个字节，所以已经是 2.4G。然后是值本身的空间使用。有人可能会认为这些值都取自 [1..100] ，因此它们应该被共享并且总共使用的空间量可以忽略不计。但是列表中的值实际上是 x 的形式。 , 这可能取决于 a , b , c和 d , 和 length从不检查列表中的值，因为它遍历它。所以每个元素都将被表示为一个指向 a 的闭包。 , b , c和 d ，这至少需要 8*(4+1) = 40 个字节，总共需要 6.4G。

这相当多，当您分配 6.4G 数据时，垃圾收集器必须进行大量复制，所有这些数据都永久存在。这就是需要这么长时间，而不是实际计算列表或其长度。

如果你编译程序

test = [x|a<-[1..100],b<-[1..100],c<-[1..100],d<-[1..100],let x = a]

main = print $ length test

然后 test不必保持事件状态，因为它的长度正在被计算，因为很明显它永远不会被再次使用。所以现在 GC 几乎没有工作要做，程序在几秒钟内运行(对于 ~10^8 列表节点分配和 Integer 上的计算是合理的)。