列表推导式占用过多内存

Question

我是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内部的处理速度太慢，以至于我必须等到看到内存消耗爆炸才能发现问题吗？还是其他原因？

请不要透露任何剧透。我只想知道极端内存消耗来自哪里以及如何解决它。

- Johannes P

---

minimalsolution 函数中取出的列表是否始终包含元素？ - Daniel Wagner

如果d参数是非平方数，则应该在main内的filter中提供。但是我的算法完全可能是错误的。请注意，有时需要一段时间才能找到实际解决方案，因为数字很快变得非常大。 - Johannes P

根据您所拥有的 GHC 版本，有时使用 ghc -threaded 选项可能会给您带来惊喜。 - Jonke

Answer 1

我以前没有做过性能分析，所以欢迎大家指正。

Haskell 确定 [2..] 是一个常量，并且为列表的每个元素重复使用，尽管 take 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。

- Sassa NF

---

谢谢你的回答！有没有办法告诉编译器改变这种行为，丢弃除了_y_当前值以外的所有内容。这基本上是一个while循环。在这个例子中使用列表推导不好吗？ - Johannes P

哇，这是个好发现！我没想到 Haskell 会表现出这种行为。我们是否遭遇了这个？我按照那里推荐的方法尝试了一下 makeXs，但无法摆脱问题。 - Johannes P

如果您没有指定 y :: Int，那么我猜它会默认为 Integer。假设使用 Int，GHC 能够进行更积极的优化。 - Tom Ellis

另外，你确定你的平方根没有引入错误吗？ - Tom Ellis

@TomEllis 是的，我也怀疑是溢出了，但没有检查:) 一个简单的检查告诉我们确实是这样。 (5983,20568,61) 不是丢番图方程的解 - 5983^2 远远不及 61*20568^2。 - Sassa NF

Answer 2

在理解中，对于每个值的 y 创建不必要的 Double 实例。

我无法找到使用列表理解的解决方案，而没有空间扩大。但是，使用递归重写可以产生稳定的内存配置文件。

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)

- Stephen Diehl

---

确实好多了！顺便说一句：我不得不在(d0*y^2+1)附近插入一个fromIntegral来平息我的编译器。现在是时候调整算法了，我想。 - Johannes P

Answer 3

就我所知，经过6年的测试后，这个问题已经不再出现了。使用GHC 8.6.5时，内存消耗非常低。我认为这确实是编译器中的一个问题，在某个时候已经得到了修复。

- Johannes P