performance - 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

有一个计算斐波那契数列的标准技巧，可以很容易地适应您的问题。斐波那契数的天真定义是:

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开头的s当然是基本情况。有 other good questions here on SO更详细地解释这项技术，你应该研究这段代码和那些答案，直到你觉得你明白它是如何工作的以及为什么它非常快。

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

让我们尝试将此技术应用于您的函数。与计算斐波那契数一样，您需要前一个和倒数第二个值；并且还需要当前索引。这可以通过包含 [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)