提高特定 Scala 代码段的性能

Question

我需要使以下代码更有效率。运行时间有点太长。

def aFib(n: Int): BigInt = {
var nn:   Int = n
var sign: Int = 0
if (nn < 0) {
nn = -nn
sign = 2 * (nn % 2) - 1
} else {
sign = 1
}
var a: BigInt = 1
var b: BigInt = 0
var p: BigInt = 0
var q: BigInt = 1
while (nn != 0) {
if (nn % 2 == 1) {
var t  = (b + a) * q + a * p 
b = b * p + a * q 
a = t
}
var t = p * p + q * q
q =(2 * p * q) + q * q
p = t
nn /= 2
}
sign * b
}

我已经尝试了不同的方法(迭代、递归等(，并确定了代码中体现的算法。Cognoscenti会认为它是计算正数和负斐波那契数的众所周知的方法。我自己编写了代码并放入了BigInt。似乎没有现成的快速实施。 由于 Scala 是一种复杂的语言，而且我的经验有限，我的直觉是有一些方法可以使代码更好 - 减少经过的时间。欢迎所有建议。

Answer 1

首先，查看此分析： https://developer.lightbend.com/blog/2018-04-09-profiling-JVM-applications/; 其次，BigInt 包装 java.math.BigInteger： https://github.com/scala/scala/blob/v2.12.3/src/library/scala/math/BigInt.scala#L1 这是一个任意精度的整数： https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html

因此，在 Scala 中，您可能能做的最好的事情就是切换到本机整数类型，并且仅在数字对于长篇来说太大时才使用此特定代码。

在此代码中，nn /= 2可能更好地表示为位移。

你能做的最好的事情可能是使用数值计算库，并尽可能多地表达这些是矩阵计算，可以在 GPU 上并行执行： https://github.com/scalanlp/breeze

更新2：看起来Breeze实际上并没有以任何方式使用GPU，:(

更新：可能最大的单次胜利是记住您的结果，因此您可以从前置值(如果已经计算(计算斐波那契。存储这些结果，在表中查找它们，并按照@tim的建议，用前几千个数字为表播种。

Answer 2

BigInt操作将主导此代码的性能，因此进行实质性改进的唯一方法是减少这些操作的数量。您可以避免计算两次q*q以获得轻微的性能提升，但否则您将不得不找到更好的算法或更好的BigInt实现。

但是，您可以通过使代码更惯用的 Scala 不使用任何可变值来使您的代码更好。使用 JVM 很难进行性能测量，这取决于您感兴趣的n值，但这似乎与原始值大致相同。

def aFib(n: Int): BigInt = {
@tailrec
def loop(nn: Int, a: BigInt, b: BigInt, p: BigInt, q: BigInt): BigInt =
if (nn == 0) {
b
} else {
val newP = p * p + q * q
val newQ = (2 * p * q) + q * q
if (nn % 2 == 1) {
val newA = (b + a) * q + a * p
val newB = b * p + a * q
loop(nn / 2, newA, newB, newP, newQ)
} else {
loop(nn / 2, a, b, newP, newQ)
}
}
val (nn, sign) =
if (n <  0) {
(-n, 2 * (n % 2) - 1)
} else {
(n, 1)
}
sign * loop(nn, 1, 0, 0, 1)
}

Answer 3

使用惰性实现

import scala.math.BigInt
lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }
fibs.take(5).last

@Fred 此外，您可以将这样的东西用于负值和正值

def fib(value: Int): BigInt = {
@tailrec
def helper(cur: BigInt, prev: BigInt, n: BigInt): BigInt = {
val zero = BigInt(0)
if (n == zero) cur
else if (n > 0) helper(cur + prev, cur, n - 1)
else helper(prev, cur - prev, n + 1)
}
helper(0, 1, value)
}