更高效的算法使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中實現比啞巴更好的算法？ （另外，我很樂意收到關於我的編碼風格的一般反饋）

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。

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）。