haskell - Haskell 中的线性递推关系实现太慢

Question

我已经实现了一个代码，它在给定基本情况和线性递推关系的系数的情况下生成无限序列。

import Data.List
linearRecurrence coef base | n /= (length base) = []
                           | otherwise = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
  where a     = linearRecurrence coef base
        n     = (length coef)

这是斐波那契数列的实现。
fibs = 0 : 1 : (zipWith (+) fibs (tail fibs))

很容易看出

linearRecurrence [1,1] [0,1] = fibs

然而计算时间 fibs!!2000是 0.001 秒， (linearRecurrence [1,1] [0,1])!!2000 大约是 1 秒.速度的巨大差异从何而来？我已经使一些功能变得严格。例如， (sum . (zipWith (*) coef))被 (id $! (sum . (zipWith (*) coef))) 取代，并没有帮助。

Answer 1

您正在计算 linearRecurrence coef base反复。利用共享，例如:

linearRecurrence coef base | n /= (length base) = []
                           | otherwise = a
  where a = base ++ map (sum . (zipWith (*) coef)) (map (take n) (tails a))
        n = (length coef)

注意 a的分享.

现在你得到:

*Main> :set +s
*Main> fibs!!2000
422469...
(0.02 secs, 2203424 bytes)
*Main> (linearRecurrence [1,1] [0,1])!!2000
422469...
(0.02 secs, 5879684 bytes)