3

我的一个朋友在他参加的 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 中实现比愚蠢的算法更好的算法?(另外,我很高兴收到关于我的编码风格的一般反馈)

4

2 回答 2

3

当然有。我们有:

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

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

a*x + b*y = n

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

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

我们只保留积分 zs。

于 2013-06-26T20:33:43.687 回答
1

值得注意的是,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)。

于 2013-06-26T21:48:29.950 回答