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需要一段时间才能返回.

任何优化的想法？

Answer 1

计算Fibonacci数字有一个标准技巧,可以很容易地适应您的问题.Fibonacci数字的天真定义是:

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

但是,这是非常昂贵的:因为递归的所有叶子都是1if fib x = y,那么我们必须执行y递归调用!由于斐波纳契数以指数方式增长,这是一个糟糕的事态.但是通过动态编程,我们可以共享两个递归调用所需的计算.令人愉悦的单行内容如下所示:

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

这可能看起来有点令人费解; 这里的fibList参数zipWith在两个索引之前用作递归,而tail fibList参数在一个索引之前用作递归,它给出了两个fib (n-2)和fib (n-1)值.1开头的两个当然是基本案例.有在这里上的其他好的问题,在进一步详细解释这项技术,直到你觉得你了解它是如何工作以及为什么它是非常快的,你应该研究这个代码和这些问题的答案.

如有必要,可以Int -> Integer使用此方法恢复类型签名(!!).

让我们尝试将此技术应用于您的功能.与计算Fibonacci数一样,您需要前一个和倒数第二个值; 另外还需要当前的指数.这可以通过[2..]在电话中加入来完成zipWith.这是它的样子:

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)

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)准备.