haskell - 有没有办法在 Haskell 中优化这个程序？

Question

我正在做项目 euler question 224 。并在 Haskell 中提出了这个列表理解:

prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)]

我用 GHC 编译它，它已经以高于平均内核优先级运行了一个多小时而没有返回结果。我可以做些什么来优化此解决方案？似乎我越来越擅长以天真的方式寻找蛮力解决方案。我能做些什么吗？

编辑:我也不清楚“积分长度”的定义，这是否只是意味着边长的大小落在正整数组中，即:1,2,3,4,5...？

Answer 1

我的 Haskell 并不神奇，但我认为这将是 n^5 写的。

看起来您是在说从 1 到 7500 万的每个 n，检查每个边界小于或等于 7500 万的“几乎不钝”的三角形，看看它是否有边界 n。

此外，我不确定列表推导式是否足够智能，一旦 c^2 -1 的当前值大于 a^2 + b^2 就停止查找。

一个简单的重构应该是

prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000]

你可以让它变得更好，但实际上应该快 7500 万倍。

对这种重构不太确定，但它也应该大大加快速度:

prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)]

那里的语法可能不是 100%。这个想法是 a 只能是 1 到 2500 万(因为 a <= b <= c 并且 a + b + c <= 75 百万)。 b 只能介于 a 到 7500 万之间(因为 b <= c)，c 只能介于 b 到 7500 万 - (a + b) 之间，否则周长将超过 7500 万。

编辑:更新的代码片段，其中有几个错误。

另一个快速建议，您可以将 c <- [b..(75000000 - a - b)] 替换为 c <- [b..min((75000000 - a - b), sqrt(aa + bb) ) + 1)]。无需费心检查任何大于 (a^2 + b^2) 平方根上限的 c 值。不记得这些是否是 haskell 中正确的 min/sqrt 函数名称。

在这个问题上获得强制症，我还有一些建议。

1) 你可以将b的上界设置为当前上界的最小值和a^2 * 2 + 1。这是基于(x+1)^2 - x^2 = 2x + 1的原则. b 不能比 a 大太多，我们可以保证 (a^2) + (b^2) < (b+1)^2。

2) 将 c 的下限设置为 b + 1 和 floor(sqrt(a^2 + b^2) - 1) 的最大值。就像 C 的上限一样，不需要测试不可能正确的值。