为什么（sum $ takeWhile（< 10000000）[1 ..]）使用这么多内存？ [英] Why does (sum $ takeWhile (<10000000) [1..]) use so much memory?

问题描述

这是我在控制台中得到的结果：

  ghci> sum $ takeWhile（< 10000000）[1 ..] 
 49999995000000 
（11.96秒，2174569400字节）
  

超过2GB！我会想象 sum 可以放弃它已经求和的任何东西。你将如何写这篇文章？

您正在创建一千万整数和很多列表单元格。另外，如果你运行的是解释器代码，那么你会在编译器中运行它，这会减少分配。

主要问题是解释器没有优化因此， sum 使用构建巨大 thunk的惰性变体。 sum 放弃它已经使用的列表部分，但它会用thunk替换它以计算结果，所以

  sum [1,2,3,4 ...] 
  

变为

pre> （...（（（（0 + 1）+2）+ 3）+ 4）+ ...）


之后。这不是最佳替代方法，因为添加 Integer s是严格的。

在ghci提示符下，您应该写

  Prelude Data.List> （+）0 $ takeWhile（< 10000000）[1 ..] 
 49999995000000 
（1.41秒，1443355832字节）
  

来解决这个问题。在编译（当然有优化）程序中， sum 可以正常工作。

This is what I get in the console:

ghci> sum $ takeWhile (<10000000) [1..]
49999995000000
(11.96 secs, 2174569400 bytes)

That's over 2GB! I would imagine that sum can discard whatever it has already summed. How would you write this?

解决方案

You're creating ten million Integers, and a lot of list cells. Also, you're running interpreted code, if you ran it through the compiler, that would reduce the allocation somewhat.

The main problem is that the interpreter doesn't optimise at all, so the sum uses the lazy variant that builds a huge thunk. sum discards the part of the list it has consumed just fine, but it replaces it with a thunk to compute the result afterward, so

sum [1,2,3,4 ...]

becomes

(...((((0 + 1) + 2) + 3) + 4) + ...)

afterward. That's not the optimal substitution, since addition of Integers is strict.

At the ghci prompt, you should write

Prelude Data.List> foldl' (+) 0 $ takeWhile (< 10000000) [1 .. ]
49999995000000
(1.41 secs, 1443355832 bytes)

to fix that. In a compiled (with optimisations, of course) programme, sum will work fine.

这篇关于为什么（sum $ takeWhile（< 10000000）[1 ..]）使用这么多内存？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！