performance - 概括斐波那契类型序列(性能)

Question

今天我找到了 Haskell Fibonacci 定义:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

探索，我将“tribonacci”数字写为:

tribs = 0 : 0 : 1 : zipWith (+) (zipWith (+) tribs (tail tribs)) (drop 2 tribs)

这很好用，所以我尝试使用相同的基本思想推广到任何“斐波那契类型”序列:

nbonacci n   = (take n (repeat 0)) ++ [1] ++ (z n) 
   where z 1 = zipWith (+) (nbonacci n) (drop 1 (nbonacci n))
         z x = zipWith (+) (z (x-1)) (drop x (nbonacci n))

这也有效:它正确地给出了我想要的序列。不幸的是，它也非常慢，甚至在生成相同的斐波那契数列和三角数列时也要慢很多倍。我怎样才能以获得更好性能的方式表达相同的想法？

Answer 1

您可以使用 worker-wrapper transform :

nbonacci n = go where
    go = take n (repeat 0) ++ [1] ++ z n
    z 1 = zipWith (+) go (drop 1 go)
    z x = zipWith (+) (z (x-1)) (drop x go)