performance - 更高效的算法在 Haskell 中表现更差

Question

我的一个 friend 向我展示了他参加的 C++ 类(class)中的家庭练习。由于我已经了解 C++，但刚开始学习 Haskell，所以我尝试以“Haskell 方式”解决练习。

这些是练习说明(我是从我们的母语翻译的，所以如果说明不清楚，请评论):

编写一个程序，从用户那里读取非零系数(A、B、C、D)并将它们放入以下等式中: A*x + B*y + C*z = D 该程序还应该从用户 N 读取，它表示一个范围。该程序应在 -N/2 到 N/2 范围内找到方程的所有可能积分解。

例如:

Input: A = 2,B = -3,C = -1, D = 5, N = 4
Output: (-1,-2,-1), (0,-2, 1), (0,-1,-2), (1,-1, 0), (2,-1,2), (2,0, -1)

最直接的算法是通过蛮力尝试所有可能性。我通过以下方式在 Haskell 中实现了它:

triSolve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve a b c d n =
  let equation x y z = (a * x + b * y + c * z) == d
      minN = div (-n) 2
      maxN = div n 2
  in [(x,y,z) | x <- [minN..maxN], y <- [minN..maxN], z <- [minN..maxN], equation x y z]

到目前为止一切顺利，但练习说明指出可以实现更高效的算法，所以我想如何让它变得更好。由于方程是线性的，基于 Z 总是第一个递增的假设，一旦找到解决方案，就没有必要递增 Z。相反，我应该递增 Y，将 Z 设置为范围的最小值，然后继续。这样我就可以节省多余的执行。 由于 Haskell 中没有循环(至少以我的理解)，我意识到这种算法应该通过使用递归来实现。我通过以下方式实现了该算法:

solutions :: (Integer -> Integer -> Integer -> Bool) -> Integer -> Integer -> Integer -> Integer -> Integer ->     [(Integer,Integer,Integer)]
solutions f maxN minN x y z
  | solved = (x,y,z):nextCall x (y + 1) minN
  | x >= maxN && y >= maxN && z >= maxN = []
  | z >= maxN && y >= maxN = nextCall (x + 1) minN minN
  | z >= maxN = nextCall x (y + 1) minN
  | otherwise = nextCall x y (z + 1)
  where solved = f x y z
        nextCall = solutions f maxN minN

triSolve' :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
triSolve' a b c d n =
  let equation x y z = (a * x + b * y + c * z) == d
      minN = div (-n) 2
      maxN = div n 2
  in solutions equation maxN minN minN minN minN

两者产生相同的结果。然而，尝试测量执行时间产生了以下结果:

*Main> length $ triSolve' 2 (-3) (-1) 5 100
3398
(2.81 secs, 971648320 bytes)
*Main> length $ triSolve 2 (-3) (-1) 5 100
3398
(1.73 secs, 621862528 bytes)

这意味着愚蠢的算法实际上比更复杂的算法表现更好。基于我的算法是正确的假设(我希望它不会变成错误 :))，我假设第二种算法会受到递归产生的开销的影响，而第一种算法则不会，因为它是使用列表理解。 有没有办法在 Haskell 中实现比笨算法更好的算法？ (此外，我很高兴收到有关我的编码风格的一般反馈)

Answer 1

当然有。我们有:

a*x + b*y + c*z = d

一旦我们假设了 x 和 y 的值，我们就有了

a*x + b*y = n

其中 n 是我们知道的数字。 因此

c*z = d - n
z = (d - n) / c

我们只保留整数 zs。