代码之家 › 专栏 › 技术社区 › Gabe Moothart

Haskell脚本空间不足

lazy-evaluation space haskell

Gabe Moothart · 技术社区 · 15 年前

我正在使用ProjectEuler自学haskell,我在解释haskell是如何执行代码方面遇到了一些困难。第二个问题是,我要计算所有偶数斐波那契数的和,达到400万。我的脚本如下:

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

hugs给出了错误“垃圾收集无法回收足够的空间”,我认为这意味着列表项在被消耗时不会被释放。 foldr .

我需要做什么来解决这个问题?我试着写一个使用累加器的尾部递归(我认为)版本,但也不能让它工作。

5 回复 | 直到 10 年前

MarkusQ 15 年前

一些观察/提示:

这个 x + sum 从偶数开始直到最后才被评估
你要先撒40万个小谎,而不是最多40万个小谎
有一种更简单的方法可以做到这一点

根据评论进行编辑

我不会告诉你更简单的方法是什么,因为这是项目欧拉问题的乐趣。但我会问你一大堆问题:

你能连续撒几个小谎吗?
你连个小谎还能坚持多久?
如果你把所有的偶数fib和所有的奇数fib加起来(用手做这个),你会注意到这些和是什么?

Don Stewart 15 年前

首先,你不应该拥抱。它只是一种教学用的玩具。

然而,ghc是一个快速的多核优化编译器。 Get it here . 特别是,它进行严格的分析,并编译为本机代码。

您的代码最突出的一点是在一个非常大的列表中使用folder。可能需要一个尾部递归循环。像这样:

import Data.List

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

除此之外,最初的4米甚至光纤将占用相当大的空间,因此需要一段时间。

这里是 the sum of the first 400k even fibs ,为您节省一些时间(21秒)。-)

newacct 15 年前

你误解了这个问题。这个 actual problem 希望您对所有偶数斐波那契数求和,使斐波那契数本身不超过400万(恰好是前33个斐波那契数)。

Norman Ramsey 15 年前

你正在评估 fibs . 这些数字呈指数增长。我不知道需要多少字节来表示第一百万个斐波那契数;只有千分之一的斐波那契数有211位十进制数字,所以这需要22个32位的字来保存这些数字,不用担心开销。 gmp 强加。它们呈指数增长。

练习:计算存储400万斐波那契数所需的内存量。

ja. 15 年前

看看前奏函数takewhile、filter、event和sum

TakeWhile(<40)[0..]
筛选偶数$takewhile(<40)[0..]

把它们放在一起:

ans=sum$filter偶数$takewhile(<4*10^6)fibs