项目Euler 23:需要了解此堆栈流程计划

Question

嗨哈斯克尔研究员.我目前正在研究Project Euler的第23个问题.我在atm的地方是我的代码对我来说似乎是正确的 - 不是在"好的算法"意义上,而是在"应该工作"的含义中 - 但会产生堆栈内存溢出.

我知道我的算法并不完美(特别是我当然可以避免在我的worker函数中的每个递归步骤中计算这么大的中间结果).

虽然,在学习Haskell的过程中,我想了解为什么这段代码失败如此悲惨,以便下次避免这种错误.

任何有关此计划错误原因的见解将不胜感激.

import qualified Data.List as Set ((\\))

main = print $ sum $ worker abundants [1..28123]

-- Limited list of abundant numbers
abundants :: [Int]
abundants = filter (\x -> (sum (divisors x)) - x > x) [1..28123]

-- Given a positive number, returns its divisors unordered.
divisors :: Int -> [Int]
divisors x  | x > 0     =   [1..squareRoot x] >>=
                            (\y ->  if      mod x y == 0
                                    then    let d = div x y in
                                            if y == d
                                            then [y]
                                            else [y, d]
                                    else    [])
            | otherwise = []


worker :: [Int] -> [Int] -> [Int]
worker (a:[]) prev = prev Set.\\ [a + a]
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as)))


-- http://www.haskell.org/haskellwiki/Generic_number_type#squareRoot
(^!) :: Num a => a -> Int -> a
(^!) x n = x^n

squareRoot :: Int -> Int
squareRoot 0 = 0
squareRoot 1 = 1
squareRoot n =
   let twopows = iterate (^!2) 2
       (lowerRoot, lowerN) =
          last $ takeWhile ((n>=) . snd) $ zip (1:twopows) twopows
       newtonStep x = div (x + div n x) 2
       iters = iterate newtonStep (squareRoot (div n lowerN) * lowerRoot)
       isRoot r  =  r^!2 <= n && n < (r+1)^!2
   in  head $ dropWhile (not . isRoot) iters

编辑:确切的错误是Stack space overflow: current size 8388608 bytes..增加堆栈内存限制+RTS -K...并不能解决问题.

Edit2:关于sqrt的事情,我只是从评论中的链接复制粘贴它.为了避免必须将整数转换为双打并面对舍入问题等...

Answer 1

在将来,你自己尝试一些最小化是礼貌的.例如,通过一些播放,我能够发现以下程序也堆栈溢出(使用8M堆栈):

main = print (worker [1..1000] [1..1000])

......真正指出了什么功能让你失意.我们来看看worker:

worker (a:[]) prev = prev Set.\\ [a + a]
worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as)))

即使在我第一次阅读时,这个函数在我的脑海中被标记为红色,因为它是尾递归的.Haskell中的尾递归通常不像其他语言那样好主意; 保护递归(在递归之前生成至少一个构造函数,或者在生成构造函数之前递减少量次数)通常更适合于惰性求值.事实上,在这里,正在发生的事情是每次递归调用worker都是在prev参数中构建一个更深入,更深层次的嵌套thunk .当时间到了最后回归时prev,我们必须深入研究一系列长期的Set.\\调用,以确定我们最终拥有的是什么.

明显的严格注释没有帮助,这个问题稍微模糊了.让它按摩worker直到它起作用.第一个观察是第一个子句完全归入第二个子句.这是风格; 它不应该影响行为(空列表除外).

worker []     prev = prev
worker (a:as) prev = worker as (prev Set.\\ map (a+) (a:as))

现在,明显严格的注释:

worker []     prev = prev
worker (a:as) prev = prev `seq` worker as (prev Set.\\ map (a+) (a:as))

我惊讶地发现这仍然堆栈溢出!偷偷摸摸的事情是,seq在仅列出评估远远不够了解列表是否匹配任何[]或_:_.以下不会堆栈溢出:

import Control.DeepSeq

worker []     prev = prev
worker (a:as) prev = prev `deepseq` worker as (prev Set.\\ map (a+) (a:as))

我没有将最终版本插回到原始代码中,但它至少适用于main上面的最小化.顺便说一下,您可能会喜欢以下实现方法,它也会堆栈溢出:

import Control.Monad

worker as bs = bs Set.\\ liftM2 (+) as as

但是可以通过使用Data.Set而不是Data.List严格的注释来修复:

import Control.Monad
import Data.Set as Set

worker as bs = toList (fromList bs Set.\\ fromList (liftM2 (+) as as))

Answer 2

正如丹尼尔瓦格纳所说,问题在于

worker (a:as) prev = worker as (prev Set.\\ (map ((+) a) (a:as)))

构建一个严重嵌套的thunk.你可以避免这种情况,并且deepseq通过利用两个参数worker在这个应用程序中排序的事实来获得更好的性能.因此,您可以通过注意在任何步骤中的所有内容都prev小于2*a不能是两个丰富数字的总和来获得增量输出

worker (a:as) prev = small ++ worker as (large Set.\\ map (+ a) (a:as))
  where
    (small,large) = span (< a+a) prev

做得更好 但是,它仍然很糟糕,因为(\\)无法使用两个列表的排序.如果你用它替换它

minus xxs@(x:xs) yys@(y:ys)
    = case compare x y of
        LT -> x : minus xs yys
        EQ -> minus xs ys
        GT -> minus xxs ys
minus xs _ = xs             -- originally forgot the case for one empty list

(或使用data-ordlist软件包的版本),计算集合差异是O(长度)而不是O(长度^ 2).