Haskell：代码运行太慢

Question

我有一段计算Motzkin数的代码：

module Main where

    -- Program execution begins here
    main :: IO ()
    main = interact (unlines . (map show) . map wave . (map read) . words)

    -- Compute Motzkin number
    wave :: Integer -> Integer
    wave 0 = 1
    wave 1 = 1
    wave n = ((3 * n - 3) * wave (n - 2) + (2 * n + 1) * wave (n - 1)) `div` (n + 2)

但是即使对于简单的数字如30，输出结果也需要一段时间。

有什么优化的想法吗？

- Zubin Kadva

---

备忘录技术可能会有所帮助。 - karakfa

https://wiki.haskell.org/Memoization - chepner

Answer 1

有一种计算斐波那契数列的标准技巧，可以轻松地适应你的问题。斐波那契数列的朴素定义是:

fibFunction :: Int -> Integer
fibFunction 0 = 1
fibFunction 1 = 1
fibFunction n = fibFunction (n-2) + fibFunction (n-1)

然而这非常昂贵：由于递归的所有叶子都是1，如果fib x = y，那么我们必须执行y次递归调用！由于斐波那契数呈指数增长，这是一个糟糕的状态。但是使用动态规划，我们可以共享两个递归调用中所需的计算。这个令人愉悦的一行代码看起来像这样：

fibList :: [Integer]
fibList = 1 : 1 : zipWith (+) fibList (tail fibList)

这一开始可能看起来有些令人困惑；在这里，fibList参数传递给zipWith函数作为回溯两个位置的递归，而tail fibList参数则作为回溯一个位置的递归，这样我们就得到了fib (n-2)和fib (n-1)的值。开头的两个1当然是基本案例。这里有其他好的SO问题对这个技巧进行了进一步的解释，你应该学习这段代码和那些答案，直到你理解它如何工作以及为什么这非常快。

如果需要，可以使用(!!)从中恢复Int -> Integer类型的签名。

让我们尝试将这一技巧应用到您的函数中。与计算斐波那契数列一样，您需要前面两个值；此外还需要当前索引。可以通过在调用zipWith时包含[2..]来实现。以下是代码的实现：

waves :: [Integer]
waves = 1 : 1 : zipWith3 thisWave [2..] waves (tail waves) where
    thisWave n back2 back1 = ((3 * n - 3) * back2 + (2 * n + 1) * back1) `div` (n + 2)

与之前一样，可以使用(!!)或genericIndex（如果确实需要Integer索引）来恢复函数版本。我们可以在ghci中确认它计算的是同一个函数（但速度更快，占用的内存更少）：

> :set +s
> map wave [0..30]
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(6.00 secs, 3,334,097,776 bytes)
> take 31 waves
[1,1,2,4,9,21,51,127,323,835,2188,5798,15511,41835,113634,310572,853467,2356779,6536382,18199284,50852019,142547559,400763223,1129760415,3192727797,9043402501,25669818476,73007772802,208023278209,593742784829,1697385471211]
(0.00 secs, 300,696 bytes)

- Daniel Wagner

Answer 2

使用n=30时，你需要计算wave 29和wave 28，而这又需要计算wave 28、wave 27两次以及wave 26等等，这很快就会增长到数十亿。

可以采用与计算斐波那契数列相同的技巧：

wave 0 = 1
wave 1 = 1
wave n = helper 1 1 2
    where
       helper x y k | k <n      = helper y z (k+1)
                    | otherwise = z
                    where z = ((3*k-3) * x + (2*k+1) * y) `div` (k+2)

这个程序在线性时间内运行，并且对于每一个k，助手已经准备好了wave(k-2)和wave(k-1)的值。

- Ingo

---

我认为你在最后一行缺少括号，应该在括号内加上所有项的和再进行除法运算。 - karakfa

Answer 3

这是一个记忆化版本。

wave = ((1:1:map waveCalc [2..]) !!)
    where waveCalc n = ( (2*n+1)*wave (n-1) + (3*n-3)*wave (n-2) ) `div` (n+2)

- karakfa

Answer 4

谢谢大家的回复。根据我对记忆化的理解，我已经重新编写了代码：

mwave :: Int -> Int
mwave = (map wave [0..] !!)
  where wave 0 = 1
        wave 1 = 1
        wave n = ((3 * n - 3) * mwave (n - 2) + (2 * n + 1) * mwave (n - 1)) `div` (n + 2)

digits :: Int -> Int
digits n = (mwave n) `mod` 10^(100::Int)

有没有想法如何将答案输出模10^100？

- Zubin Kadva

---

你需要在mwave函数中使用Integer类型。Int不支持100位数的数字。 - Bergi

你需要的是 Integer 类型；在这里使用 Int 类型不行（尝试使用 mwave !! 43）。请参见 https://www.haskell.org/hoogle/?hoogle=%5Ba%5D+-%3E+Integer+-%3E+a。 - Will Ness

@WillNess 当我改变 mwave 的签名时，它会报错：无法将期望类型 'Integer' 与实际类型 'Int' 匹配'。 - Zubin Kadva

是的，!! 是罪魁祸首，它的类型是：....（尝试 Prelude> :t (!!)）。而 genericIndex 的类型是：....。你尝试过我提供的链接了吗？ - Will Ness

@WillNess，除了Prelude中的包，我无法使用外部包。你能推荐一个替代方案吗？谢谢。 - Zubin Kadva

在这种情况下，为了保险起见，请使用fromIntegral函数在您的代码中进行大量转换。例如，将a !! n写成a !! (fromIntegral n)。或者更好的方法是给它一个Int -> Integer的签名，并写成(3 * fromIntegral n - 3) * mwave (n - 2) ...。其中n将是Int类型（而!!需要Int作为第二个参数），但mwave n的结果将是Integer类型，因此fromIntegral n将是Integer类型，计算将通过类型检查。 - Will Ness