在 Scala 中编写斐波那契函数的最快方法是什么？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/7388416/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the fastest way to write Fibonacci function in Scala?
提问by Enrico Susatyo
I've looked over a few implementations of Fibonacci function in Scala starting from a very simple one, to the more complicated ones.
我查看了 Scala 中斐波那契函数的一些实现，从一个非常简单的实现到更复杂的实现。
I'm not entirely sure which one is the fastest. I'm leaning towards the impression that the ones that uses memoization is faster, however I wonder why Scala doesn't have a native memoization.
我不完全确定哪个是最快的。我倾向于使用 memoization 的印象更快，但是我想知道为什么 Scala 没有本地 memoization。
Can anyone enlighten me toward the best and fastest (and cleanest) way to write a fibonacci function?
任何人都可以启发我编写斐波那契函数的最佳和最快（和最干净）的方法吗？
回答by Landei
The fastest versions are the ones that deviate from the usual addition scheme in some way. Very fast is the calculation somehow similar to a fast binary exponentiation based on these formulas:
最快的版本是在某种程度上偏离通常的加法方案的版本。计算速度非常快，有点类似于基于这些公式的快速二进制取幂：
F(2n-1) = F(n)2 + F(n-1)2
F(2n) = (2F(n-1) + F(n))*F(n)
Here is some code using it:
这是一些使用它的代码：
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
}
Even though this is not very optimized (e.g. the inner loop is not tail recursive), it will beat the usual additive implementations.
即使这不是非常优化（例如，内循环不是尾递归），它也会击败通常的附加实现。
回答by Jed Wesley-Smith
for me the simplest defines a recursive inner tail function:
对我来说，最简单的定义一个递归内尾函数：
def fib: Stream[Long] = {
def tail(h: Long, n: Long): Stream[Long] = h #:: tail(n, h + n)
tail(0, 1)
}
This doesn't need to build any Tuple objects for the zip and is easy to understand syntactically.
这不需要为 zip 构建任何 Tuple 对象，并且在语法上很容易理解。
回答by Luigi Plinge
Scala does have memoization in the form of Streams.
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 ...
Streamis a LinearSeqso you might like to convert it to an IndexedSeqif you're doing a lot of fib(42)type calls.
Stream是 aLinearSeq所以IndexedSeq如果您要进行大量fib(42)类型调用，您可能希望将其转换为 an 。
However I would question what your use-case is for a fibbonaci function. It will overflow Long in less than 100 terms so larger terms aren't much use for anything. The smaller terms you can just stick in a table and look them up if speed is paramount. So the details of the computation probably don't matter much since for the smaller terms they're all quick.
但是，我会质疑您的斐波那契函数的用例是什么。它会在少于 100 个条件下溢出 Long，因此较大的条件没有多大用处。如果速度至上，您可以将较小的术语放在表格中并查找它们。因此，计算的细节可能并不重要，因为对于较小的项，它们都很快。
If you really want to know the results for very big terms, then it depends on whether you just want one-off values (use Landei's solution) or, if you're making a sufficient number of calls, you may want to pre-compute the whole lot. The problem here is that, for example, the 100,000th element is over 20,000 digits long. So we're talking gigabytes of BigInt values which will crash your JVM if you try to hold them in memory. You could sacrifice accuracy and make things more manageable. You could have a partial-memoization strategy (say, memoize every 100th term) which makes a suitable memory / speed trade-off. There is no clear anwser for what is the fastest: it depends on your usage and resources.
如果您真的想知道非常大的结果，那么这取决于您是否只想要一次性值（使用 Landei 的解决方案），或者，如果您进行了足够数量的调用，您可能需要预先计算整个地段。这里的问题是，例如，第 100,000 个元素的长度超过 20,000 位。所以我们谈论的是 GB 的 BigInt 值，如果您尝试将它们保存在内存中，它们会导致您的 JVM 崩溃。您可以牺牲准确性并使事情更易于管理。您可以采用部分记忆策略（例如，每 100 项记忆一次），以进行适当的记忆/速度权衡。对于最快的速度没有明确的答案：这取决于您的使用情况和资源。
回答by user1559897
This could work. it takes O(1) space O(n) time to calculate a number, but has no caching.
这可以工作。计算一个数字需要 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) + " "))
}
}
回答by michau
The answers using Stream(including the accepted answer) are very short and idiomatic, but they aren't the fastest. Streams memoize their values (which isn't necessary in iterative solutions), and even if you don't keep the reference to the stream, a lot of memory may be allocated and then immediately garbage-collected. A good alternative is to use an Iterator: it doesn't cause memory allocations, is functional in style, short and readable.
使用的答案Stream（包括接受的答案）非常简短和惯用，但它们并不是最快的。流记住它们的值（这在迭代解决方案中不是必需的），即使您不保留对流的引用，也可能会分配大量内存，然后立即进行垃圾收集。一个很好的替代方法是使用Iterator：它不会导致内存分配，在样式上具有功能性，简短且可读。
def fib(n: Int) = Iterator.iterate(BigInt(0), BigInt(1)) { case (a, b) => (b, a+b) }.
map(_._1).drop(n).next
回答by firephil
A little simpler tail Recursive solution that can calculate Fibonacci for large values of n. The Int version is faster but is limited, when n > 46integer overflow occurs
一个更简单的尾递归解决方案，可以为 n 的大值计算斐波纳契。Int 版本更快但有限，当n > 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)
}
回答by Chris Bedford
This has already been answered, but hopefully you will find my experience helpful. I had a lot of trouble getting my mind around scala infinite streams. Then, I watched Paul Agron's presentationwhere he gave very good suggestions: (1) implement your solution with basic Lists first, then if you are going to generify your solution with parameterized types, create a solution with simple types like Int's first.
这已经得到了回答，但希望你会发现我的经验有帮助。我在理解 Scala 无限流时遇到了很多麻烦。然后，我观看了Paul Agron 的演讲，他给出了非常好的建议：(1) 首先使用基本列表实现您的解决方案，然后如果您打算使用参数化类型来泛化您的解决方案，请首先创建一个具有简单类型的解决方案，例如 Int。
using that approach I came up with a real simple (and for me, easy to understand solution):
使用这种方法，我想出了一个真正简单的（对我来说，易于理解的解决方案）：
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}")
To get to the above solution I first created, as per Paul's advice, the "for-dummy's" version, based on simple lists:
为了获得上述解决方案，我首先根据 Paul 的建议创建了基于简单列表的“for-dummy”版本：
def fib(h: Int, n: Int) : List[Int] = {
if (h > 100) {
Nil
} else {
h :: fib(n, h + n)
}
}
Notice that I short circuited the list version, because if i didn't it would run forever.. But.. who cares? ;^) since it is just an exploratory bit of code.
请注意，我短路了列表版本，因为如果我不这样做，它将永远运行.. 但是.. 谁在乎？;^) 因为它只是一段探索性的代码。
回答by August Elm
The code below is both fast and able to compute with high input indices. On my computer it returns the 10^6:th Fibonacci number in less than two seconds. The algorithm is in a functional style but does not use lists or streams. Rather, it is based on the equality \phi^n = F_{n-1} + F_n*\phi, for \phi the golden ratio. (This is a version of "Binet's formula".) The problem with using this equality is that \phi is irrational (involving the square root of five) so it will diverge due to finite-precision arithmetics if interpreted naively using Float-numbers. However, since \phi^2 = 1 + \phi it is easy to implement exact computations with numbers of the form a + b\phi for a and b integers, and this is what the algorithm below does. (The "power" function has a bit of optimization in it but is really just iteration of the "mult"-multiplication on such numbers.)
下面的代码既快速又能够以高输入索引进行计算。在我的电脑上，它会在不到两秒的时间内返回第 10^6:th 个斐波那契数。该算法采用函数式风格，但不使用列表或流。相反，它基于等式 \phi^n = F_{n-1} + F_n*\phi，对于 \phi 黄金比例。（这是“比奈公式”的一个版本。）使用此等式的问题在于 \phi 是无理数（涉及 5 的平方根），因此如果使用浮点数天真地解释它会因有限精度算术而发散。然而，由于 \phi^2 = 1 + \phi 很容易用 a + b\phi 形式的数字实现 a 和 b 整数的精确计算，这就是下面的算法所做的。（“power”函数有一些优化，但实际上只是“
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
}
EDIT: An implementation which is more efficient and in a sense also more idiomatic is based on Typelevel's Spire library for numeric computations and abstract algebra. One can then paraphrase the above code in a way much closer to the mathematical argument (We do not need the whole ring-structure but I think it's "morally correct" to include it). Try running the following code:
编辑：一种更高效且在某种意义上也更惯用的实现基于 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) )
}
}
