在 Scala 中编写斐波那契函数的最快方法是什么？

Question

我从 非常简单，到更复杂的。

我不完全确定哪一个最快。我倾向于认为使用记忆化的速度更快，但我想知道为什么 Scala 没有原生记忆化。

谁能启发我编写斐波那契函数的最佳、最快（也是最干净）的方法？

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 形式的记忆。

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，因此如果您执行大量 fib(42)，您可能希望将其转换为 IndexedSeq 类型调用。

不过，我会质疑您的斐波那契函数的用例是什么。少于 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) + " "))
   }
}

Answer 5

使用 Stream 的答案（包括接受的答案）非常简短且惯用，但它们不是最快的。流会记住它们的值（这在迭代解决方案中不是必需的），即使您不保留对流的引用，也可能会分配大量内存，然后立即进行垃圾收集。一个好的替代方案是使用迭代器：它不会导致内存分配，功能强大，简短且可读。

def fib(n: Int) = Iterator.iterate(BigInt(0), BigInt(1)) { case (a, b) => (b, a+b) }.
                           map(_._1).drop(n).next

Answer 6

一个更简单的尾递归解决方案，可以计算大 n 值的斐波那契数。当 n > 时，Int 版本速度更快，但受到限制。 46 发生整数溢出

def tailRecursiveBig(n :Int) : BigInt = {

      @tailrec
       def aux(n : Int, next :BigInt, acc :BigInt) :BigInt ={

         if(n == 0) acc
          else aux(n-1, acc + next,next)
       }

      aux(n,1,0)
    }

Answer 7

这个问题已经得到了回答，但希望我的经验对您有所帮助。我很难理解 scala 无限流。然后，我观看了 Paul Agron 的演讲，他给出了非常好的建议：（1）实施你的首先使用基本列表创建解决方案，然后如果您要使用参数化类型泛化您的解决方案，请首先使用 Int 等简单类型创建解决方案。

使用这种方法，我想出了一个真正简单的（对我来说，易于理解的解决方案）：

  def fib(h: Int, n: Int) : Stream[Int] = { h  #:: fib(n, h + n) }
  var x = fib(0,1)
  println (s"results: ${(x take 10).toList}")

为了达到我首先创建的上述解决方案，根据保罗的建议，基于简单列表的“for-dummy's”版本

  def fib(h: Int, n: Int) : List[Int] = {
    if (h > 100) {
      Nil
    } else {
      h :: fib(n, h + n)
    }
  }

：我短路了列表版本，因为如果我不这样做，它将永远运行..但是..谁在乎呢？ ;^) 因为它只是一段探索性的代码。

Answer 8

下面的代码既快速又能够以高输入索引进行计算。在我的计算机上，它会在不到两秒的时间内返回第 10^6 个斐波那契数。该算法采用函数式风格，但不使用列表或流。相反，它基于等式 \phi^n = F_{n-1} + F_n*\phi，其中 \phi 是黄金比例。 （这是“比奈公式”的一个版本。）使用这个等式的问题是 \phi 是无理数（涉及五的平方根），因此如果简单地使用浮点数解释，它会由于有限精度算术而发散。然而，由于 \phi^2 = 1 + \phi，对于 a 和 b 整数，使用 a + b\phi 形式的数字很容易实现精确计算，这就是下面的算法所做的。 （“power”函数有一些优化，但实际上只是这些数字的“mult”乘法的迭代。）

    type Zphi = (BigInt, BigInt)

    val phi = (0, 1): Zphi

    val mult: (Zphi, Zphi) => Zphi = {
            (z, w) => (z._1*w._1 + z._2*w._2, z._1*w._2 + z._2*w._1 + z._2*w._2)
    }

    val power: (Zphi, Int) => Zphi = {
            case (base, ex) if (ex >= 0) => _power((1, 0), base, ex)
            case _                       => sys.error("no negative power plz")
    }

    val _power: (Zphi, Zphi, Int) => Zphi = {
            case (t, b, e) if (e == 0)       => t
            case (t, b, e) if ((e & 1) == 1) => _power(mult(t, b), mult(b, b), e >> 1)
            case (t, b, e)                   => _power(t, mult(b, b), e >> 1)
    }

    val fib: Int => BigInt = {
            case n if (n < 0) => 0
            case n            => power(phi, n)._2
    }

编辑：一个更高效并且在某种意义上也更惯用的实现是基于 Typelevel 的 Spire用于数值计算和抽象代数的库。然后，我们可以用一种更接近数学论证的方式解释上面的代码（我们不需要整个环结构，但我认为包含它在道德上是正确的）。尝试运行以下代码：

import spire.implicits._
import spire.algebra._

case class S(fst: BigInt, snd: BigInt) {
  override def toString = s"$fst + $snd"++"φ"
}

object S {
  implicit object SRing extends Ring[S] {
    def zero = S(0, 0): S
    def one = S(1, 0): S
    def plus(z: S, w: S) = S(z.fst + w.fst, z.snd + w.snd): S
    def negate(z: S) = S(-z.fst, -z.snd): S
    def times(z: S, w: S) = S(z.fst * w.fst + z.snd * w.snd
                            , z.fst * w.snd + z.snd * w.fst + z.snd * w.snd)
  }
}

object Fibo {

  val phi = S(0, 1) 
  val fib: Int => BigInt = n => (phi pow n).snd

  def main(arg: Array[String]) {
    println( fib(1000000) )
  }

}