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

Question

我的一个朋友向我展示了他在参加的C++课程中的家庭练习。由于我已经知道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中实现比愚蠢算法更好的算法呢？

（此外，我很乐意听取关于我的编码风格的一般反馈）

- reish

---

测试某个东西的唯一可靠方法是运行一个由使用 -O2 开关编译而成的独立可执行文件。 应用工人/包装器转换：将“nextCall”定义为内部定义，局限于“solutions”，这样您就不必传递不变的参数-嵌套定义将可以访问外部定义的参数。 - Will Ness

你的程序是否需要支持任意大的数字？因为这就是 Integer 所做的。如果你想要效率，并且 Int 的范围对你来说足够，那么请使用 Int！另外，确保使用 -O2 进行构建。这应该能够提高你的性能，作为一个开始。 - Alp Mestanogullari

你正在使用ghci进行评估——那是一个比ghc -O2慢大约30倍的字节码解释器。 - Don Stewart

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。

- Ingo

---

谢谢，这就可以了。我很尴尬，没有自己想到它。我猜这就是在思考“编码”时尝试解决数学问题的结果。不过，我仍然希望知道为什么triSolve'比triSolve表现更差。 - reish

如果这是弗雷格（Frege）而不是 Haskell，我会说将函数作为参数传递还是使用编译器知道一些信息的函数（例如，它需要三个严格的整数参数）在性能方面会有很大的差别。但是，请把这个评论视为一个猜测，我真的没有资格谈论 Haskell 优化... - Ingo

请问您能否澄清一下 ax + by = n 这个公式的含义？ - Dwilson

他的意思是，给定x和y的值，你知道a*x + b*y的值。将该值命名为n。然后，你只需要解决n + c*z = d，其中你已知n、c和z。正如Ingo所说，这可以得出z = (d - n) / c。 - Alp Mestanogullari

Answer 2

值得注意的是，GHC 对列表推导式进行了特殊处理，通常速度非常快。这可能解释了为什么使用列表推导式的 triSolve 比不使用列表推导式的 triSolve' 更快。

例如，解决方案：

solve :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
-- "Buffalo buffalo buffalo buffalo Buffalo buffalo buffalo..."
solve a b c d n =
    [(x,y,z) | x <- vals, y <- vals
             , let p = a*x +b*y
             , let z = (d - p) `div` c
             , z >= minN, z <= maxN, c * z == d - p ]
    where
        minN = negate (n `div` 2)
        maxN = (n `div` 2)
        vals = [minN..maxN]

在我的机器上运行速度很快：

> length $ solve 2 (-3) (-1) 5 100
3398
(0.03 secs, 4111220 bytes)

相应的代码使用do符号写成：

solveM :: Integer -> Integer -> Integer -> Integer -> Integer -> [(Integer,Integer,Integer)]
solveM a b c d n = do
    x <- vals
    y <- vals
    let p = a * x + b * y
        z = (d - p) `div` c
    guard $ z >= minN
    guard $ z <= maxN
    guard $ z * c == d - p
    return (x,y,z)
    where
        minN = negate (n `div` 2)
        maxN = (n `div` 2)
        vals = [minN..maxN]

运行时间是原来的两倍，内存使用量也是原来的两倍：

> length $ solveM 2 (-3) (-1) 5 100
3398
(0.06 secs, 6639244 bytes) 

通常在GHCI中进行测试时需要注意一些事项--如果您真的想看到差异，您需要使用-O2编译代码并使用一个像Criterion这样的良好基准库。

- Chris Taylor

---

我无法复制这些时间结果。对我来说，列表推导式运行得更慢。 - Benjamin Hodgson

很有趣。你使用的 GHC 版本是什么？我用的是 7.4.1。 - Chris Taylor

由 ghc --version 报告，版本为 7.6.3。 - Benjamin Hodgson