9

如这段代码：

import Data.Char
groupsOf _ [] = []
groupsOf n xs = 
    take n xs : groupsOf n ( tail xs )

problem_8 x = maximum . map product . groupsOf 5 $ x
main = do t <- readFile "p8.log" 
      let digits = map digitToInt $concat $ lines t
      print $ problem_8 digits

我意识到在 Haskell 中许多程序构造并似乎存储了一些中间结果，例如groupsOf上面代码中的列表。以上代码是欧拉项目第8题的参考答案，取自Haskell网站。最初的问题要求在很长的数字链中 5 个连续数字的最大乘积，例如45343231635723421312443535767983456. 因此代码将计算所有产品并将其存储为列表。在其他语言中，我认为它们只会保留暂时的最大值并丢弃任何较小的值。

那么groupsOf真的存储所有中间结果吗？如果问题扩大了怎么办？它会分配太多内存吗？

4

3 回答 3

12

不，不是因为groupsOf。那个人一次只需要在内存中保留一组。但是，由于太懒，可能会产生很大的thunkmaximum，因此请确保使用or进行编译以执行严格性分析，或者使用1代替。-O-O2foldl1' max

1 foldl1'发现于Data.List

于 2011-11-26T00:07:18.043 回答
8

我意识到在 Haskell 中许多程序构造并似乎存储了一些中间结果，例如上面代码中的 groupsOf 列表。

“似乎”在这里说得很好，因为老实说，这就是 Haskell 真正发光的地方。事实上，由于懒惰，它可以占用更少的内存，而无需您进行复杂的微管理。

惰性 IO（例如 ）的一个妙处readFile是它只会根据需要读取尽可能多的文件，并且可以在您使用其内容时对文件进行垃圾收集。（嗯，大致如此。这取决于您如何设置缓冲。）

这是您的程序将如何执行的粗略草图：

t <- readFile "p8.log"

为t :: String. 可能检查文件是否存在，并以读取模式打开它。

 let digits = map digitToInt $concat $ lines t

为digits :: [Int]

 print $ problem_8 digits

一旦我们尝试执行此操作，所有工作实际上都会完成。我们需要充分评估problem_8 digits :: Int才能打印出来。所以我们创建一个thunk forproblem_8 digits并强制它。

maximum . map product . groupsOf 5 $ digits

此时，maximum需要前两个元素，map product . groupsOf 5 $ digits才能看两者哪个更大。因此map product需要查看前两个元素groupsOf 5 digits来传递。

现在，groupsOf 5将需要前 5 个元素digits来生成它的第一个元素。此时，可能会读取文件的第一行，并进行定义的转换。groupsOf可以构造它的第一个元素，并且可能构造它的第二个元素（假设该行上有超过 6 个字符）。groupsOf 5 digits将它的前两个元素传递到链上，我们映射product到这两个东西上，然后maximum检查两者中哪个更大。我们保留两者中较大的结果。

在这一点上（实际上比这一点更早）我们可以完全丢弃中间结果。的前两个元素groupOf 5 digits现在完全不需要了；我们永远不需要再次检查它们，垃圾收集器可以随时收集它们。该文件的前两个字符也不再使用，可以丢弃。

现在，这是非常随意的，可能有点不准确。但是你明白吗？Haskell 是惰性的（从技术上讲，Haskell 是“非严格的”，通常通过惰性实现），这使得它的执行风格与任何严格的语言都有很大不同。这使我们能够使用看似大量的中间表示和数据结构，而实际上并不占用大量内存。好的编译器，比如 GHC，可以优化内存使用，就像你不会相信的那样。

于 2011-11-26T07:46:19.913 回答
3

我不确定您在这里所说的“中间结果”是什么意思……但是您的代码对我来说看起来不错。具体来说，您的实现groupsOf是尾递归模 cons，所以我认为您不必担心堆栈溢出，如果这是您所关心的。

不过，我可能误解了你的问题。你能澄清一下吗？

于 2011-11-26T00:04:58.643 回答