performance - 列表程序中的空间泄漏

Question

我正在解决 Haskell 中 Project Euler 的一些问题。我为其中的一个谜题编写了一个程序，但它并没有像我预期的那样工作。

当我在运行程序时查看任务管理器时，我看到它在 ghc 上使用了 > 1 GB 的 RAM。我的一个 friend 用Java写了一个同义的程序，7秒就成功了。

import Data.List

opl = find vw $ map (\x-> fromDigits (x++[0,0,9]) ) 
        $ sequence [[1],re,[2],re,[3],re,[4],re,[5],re,[6],re,[7],re,[8],re]

vw x = hh^2 == x
    where hh = (round.sqrt.fromIntegral) x

re = [0..9]

fromDigits x = foldl1 (\n m->10*n+m) x

我知道如果有足够的 RAM 和时间，这个程序会输出我想要的数字，但必须有一个性能更好的方法。

Answer 1

这里的主要问题是序列有空间泄漏。它是这样定义的:

sequence [] = [[]]
sequence (xs:xss) = [ y:ys | y <- xs, ys <- sequence xss ]

所以问题是递归调用产生的列表 sequence xss为 xs 的每个元素重复使用，所以直到最后都不能丢弃。没有空间泄漏的版本是

myseq :: [[a]] -> [[a]]
myseq xs = go (reverse xs) []
 where
  go [] acc = [acc]
  go (xs:xss) acc = concat [ go xss (x:acc) | x <- xs ]

PS。答案似乎是 Just 1229314359627783009
编辑 避免连接的版本:

seqlists :: [[a]] -> [[a]]
seqlists xss = go (reverse xss) [] []
 where
   go []       acc rest = acc : rest
   go (xs:xss) acc rest = foldr (\y r -> go xss (y:acc) r) rest xs

请注意，这两个版本都以与标准 sequence 不同的顺序生成结果。 ，所以虽然它们可以解决这个问题，但我们不能将它们用作 sequence 的专用版本.