5

我是 Haskell 的初学者，用它解决了Project Euler的大约 50 个问题，但现在我被困在问题 66上。问题是编译后的代码 ( ghc -O2 --make problem66.hs) 在 10-20 秒后占用了我机器的所有空闲内存。我的代码如下所示：

-- Project Euler, problem 66

diophantine x y d = x^2 - d*y^2 == 1

minimalsolution d = take 1 [(x, y, d) | y <- [2..],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

issquare x = (round $ sqrt $ fromIntegral x)^2 == x

main = do
    print (map minimalsolution (filter (not . issquare) [1..1000]))

我有一种预感，问题出在列表理解中的无限列表中minimalsolution。

我实际上认为，由于懒惰，Haskell 只会评估列表，直到它找到一个元素（因为take 1）并在途中丢弃所有diophantine评估为的元素False。我错了吗？

有趣的是，我在 ghci 中没有看到这种行为。是因为 ghci 内部的处理速度太慢了，以至于我不得不等到我看到内存消耗爆炸 - 还是其他原因？

请不要剧透。我只想知道极端内存消耗的来源以及如何解决它。

4

3 回答 3

4

我之前没有介绍过，所以欢迎投石者。

Haskell 确定 [2..] 是一个常数，并被重复用于列表的每个元素，尽管仅使用该列表的一个元素取 1；因此它会记住列表以计算同一列表的未来元素。d=61 的计算值会卡住。

编辑：

有趣的是，这个终止于 [1..1000]：

minimalsolution d = take 1 [(x, y, d) | y <- [2..] :: [Int],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

刚刚添加:: [Int]。内存使用看起来稳定在 1MB。使用 Int64 会重现该问题。

minimalsolution d = take 1 [(x, y, d) | y <- [2..] :: [Int64],
                            let x = round $ sqrt $ fromIntegral (d*y^2+1),
                            diophantine x y d]

编辑：

好吧，正如已经建议的那样，差异是由溢出引起的。d=61 的解报告为 (5983,20568,61)，但 5983^2 远不及 61*20568^2。

于 2013-09-12T23:52:24.503 回答
1

在理解的内部，在 的每个值上创建不必要的 Double 实例y。

我找不到使用没有空间爆炸的列表推导的解决方案。但是使用递归重写会产生稳定的内存配置文件。

diophantine :: Int -> Int -> Int -> Bool
diophantine x y d = x^2 - d*y^2 == 1

minimalsolution ::  Int -> (Int, Int, Int)
minimalsolution d = go 2
  where
    d0 = fromIntegral d
    go a =
      let y = fromIntegral a
          x = round $ sqrt $ (d0*y^2+1) in
      if diophantine x y d then
        (x, y, d)
      else
        go (y+1)
于 2013-09-13T06:00:41.213 回答
1

对于它的价值，我在 6 年后现在已经对此进行了测试，并且这个问题不再出现。GHC 8.6.5 的内存消耗保持非常低。我认为这确实是编译器中的一个问题，该问题已在某个时候得到修复。

于 2019-09-25T12:12:06.693 回答