在Scala中编写Fibonacci函数的最快方法是什么？

Question

我已经从Scala中看到了Scala中Fibonacci函数的一些实现,从一个非常简单的实现到更复杂的函数.

我不完全确定哪一个是最快的.我倾向于使用memoization的那些更快,但我想知道为什么Scala没有本机的memoization.

任何人都可以启发我最好,最快(最干净)的方法来编写斐波纳契函数吗？

Answer 1

最快的版本是以某种方式偏离通常的添加方案的版本.非常快的计算方式类似于基于这些公式的快速二进制求幂:

F(2n-1) = F(n)² + F(n-1)²
F(2n) = (2F(n-1) + F(n))*F(n)

这是使用它的一些代码:

def fib(n:Int):BigInt = {
   def fibs(n:Int):(BigInt,BigInt) = if (n == 1) (1,0) else {
     val (a,b) = fibs(n/2)
     val p = (2*b+a)*a
     val q = a*a + b*b
     if(n % 2 == 0) (p,q) else (p+q,p)
   }
   fibs(n)._1
}

即使这不是非常优化(例如内部循环不是尾递归),它将胜过通常的附加实现.

Answer 2

对我来说,最简单的定义了递归内尾函数:

def fib: Stream[Long] = {
  def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h + n)
  tail(0, 1)
}

这不需要为zip构建任何Tuple对象,并且在语法上易于理解.

Answer 3

Scala确实以Streams的形式进行了memoization.

val fib: Stream[BigInt] = 0 #:: 1 #:: fib.zip(fib.tail).map(p => p._1 + p._2)

scala> fib take 100 mkString " "
res22: String = 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 ...

Stream是LinearSeq这样,你可能希望将其转换为一个IndexedSeq,如果你做了很多的fib(42)呼叫类型.

但是,我会质疑你的用例是什么样的fibbonaci功能.它将在不到100个术语中溢出Long,因此更大的术语对任何东西都没有多大用处.如果速度至关重要,您可以将较小的术语放在表格中并查看它们.所以计算的细节可能并不重要,因为对于较小的术语,它们都很快.

如果你真的想知道非常大的术语的结果,那么这取决于你是否只需要一次性值(使用Landei的解决方案),或者,如果你正在进行足够数量的调用,你可能想要预先计算整个很多.这里的问题是,例如,第100,000个元素长度超过20,000个数字.所以我们正在谈论千兆字节的BigInt值,如果你试图将它们保存在内存中,它们会使你的JVM崩溃.你可以牺牲准确性并使事情更易于管理.你可以有一个部分记忆策略(比如每100个记忆一次),它可以进行合适的记忆/速度权衡.什么是最快的没有明确的因素:它取决于您的使用和资源.

Answer 4

这可行.它需要O(1)空间O(n)时间来计算一个数字,但没有缓存.

object Fibonacci {
    def fibonacci(i : Int) : Int = {      
        def h(last : Int, cur: Int, num : Int) : Int = {
            if ( num == 0) cur
            else h(cur, last + cur, num - 1)
        }

        if (i < 0) - 1
        else if (i == 0 || i == 1) 1
        else h(1,2,i - 2)
   }

   def main(args: Array[String]){
      (0 to 10).foreach( (x : Int) => print(fibonacci(x) + " "))
   }
}