问题描述
我编写了一个简单的测试平台来衡量三种阶乘实现的性能:基于循环、非尾递归和尾递归.
I've wrote a naïve test-bed to measure the performance of three kinds of factorial implementation: loop based, non tail-recursive and tail-recursive.
令我惊讶的是最差的性能是循环(预计«while»效率更高，所以我提供了两者)几乎是尾递归替代方案的两倍.
*ANSWER: 修复循环实现，避免 = 操作符，由于其内部结构，BigInt 的表现优于 BigInt 最差的操作符 «loops» 达到预期的速度
我遇到的另一个woodoo"行为是 StackOverflow没有为相同的输入系统地抛出异常非尾递归实现的情况.我可以绕过StackOverlow 通过逐步调用越来越大的函数values…我觉得很疯狂:) 答案:JVM 需要在启动时收敛，然后行为是连贯的和系统的
这是代码:
final object Factorial {
type Out = BigInt
def calculateByRecursion(n: Int): Out = {
require(n>0, "n must be positive")
n match {
case _ if n == 1 => return 1
case _ => return n * calculateByRecursion(n-1)
}
}
def calculateByForLoop(n: Int): Out = {
require(n>0, "n must be positive")
var accumulator: Out = 1
for (i <- 1 to n)
accumulator = i * accumulator
accumulator
}
def calculateByWhileLoop(n: Int): Out = {
require(n>0, "n must be positive")
var accumulator: Out = 1
var i = 1
while (i <= n) {
accumulator = i * accumulator
i += 1
}
accumulator
}
def calculateByTailRecursion(n: Int): Out = {
require(n>0, "n must be positive")
@tailrec def fac(n: Int, acc: Out): Out = n match {
case _ if n == 1 => acc
case _ => fac(n-1, n * acc)
}
fac(n, 1)
}
def calculateByTailRecursionUpward(n: Int): Out = {
require(n>0, "n must be positive")
@tailrec def fac(i: Int, acc: Out): Out = n match {
case _ if i == n => n * acc
case _ => fac(i+1, i * acc)
}
fac(1, 1)
}
def comparePerformance(n: Int) {
def showOutput[A](msg: String, data: (Long, A), showOutput:Boolean = false) =
showOutput match {
case true => printf("%s returned %s in %d ms\n", msg, data._2.toString, data._1)
case false => printf("%s in %d ms\n", msg, data._1)
}
def measure[A](f:()=>A): (Long, A) = {
val start = System.currentTimeMillis
val o = f()
(System.currentTimeMillis - start, o)
}
showOutput ("By for loop", measure(()=>calculateByForLoop(n)))
showOutput ("By while loop", measure(()=>calculateByWhileLoop(n)))
showOutput ("By non-tail recursion", measure(()=>calculateByRecursion(n)))
showOutput ("By tail recursion", measure(()=>calculateByTailRecursion(n)))
showOutput ("By tail recursion upward", measure(()=>calculateByTailRecursionUpward(n)))
}
}
以下是 sbt 控制台的一些输出(在 «while» 实现之前):
scala> example.Factorial.comparePerformance(10000)
By loop in 3 ns
By non-tail recursion in >>>>> StackOverflow!!!!!… see later!!!
........
scala> example.Factorial.comparePerformance(1000)
By loop in 3 ms
By non-tail recursion in 1 ms
By tail recursion in 4 ms
scala> example.Factorial.comparePerformance(5000)
By loop in 105 ms
By non-tail recursion in 27 ms
By tail recursion in 34 ms
scala> example.Factorial.comparePerformance(10000)
By loop in 236 ms
By non-tail recursion in 106 ms >>>> Now works!!!
By tail recursion in 127 ms
scala> example.Factorial.comparePerformance(20000)
By loop in 977 ms
By non-tail recursion in 495 ms
By tail recursion in 564 ms
scala> example.Factorial.comparePerformance(30000)
By loop in 2285 ms
By non-tail recursion in 1183 ms
By tail recursion in 1281 ms
以下是 sbt 控制台的一些输出(在 «while» 实现之后):
scala> example.Factorial.comparePerformance(10000)
By for loop in 252 ms
By while loop in 246 ms
By non-tail recursion in 130 ms
By tail recursion in 136 ns
scala> example.Factorial.comparePerformance(20000)
By for loop in 984 ms
By while loop in 1091 ms
By non-tail recursion in 508 ms
By tail recursion in 560 ms
接下来是 sbt 控制台的一些输出(在向上"尾递归实现之后)世界恢复正常:
scala> example.Factorial.comparePerformance(10000)
By for loop in 259 ms
By while loop in 229 ms
By non-tail recursion in 114 ms
By tail recursion in 119 ms
By tail recursion upward in 105 ms
scala> example.Factorial.comparePerformance(20000)
By for loop in 1053 ms
By while loop in 957 ms
By non-tail recursion in 513 ms
By tail recursion in 565 ms
By tail recursion upward in 470 ms
以下是在循环"中修复 BigInt 乘法后 sbt 控制台的一些输出:世界完全正常:
scala> example.Factorial.comparePerformance(20000)
By for loop in 498 ms
By while loop in 502 ms
By non-tail recursion in 521 ms
By tail recursion in 611 ms
By tail recursion upward in 503 ms
BigInt 开销和我的愚蠢实现掩盖了预期的行为.
BigInt overhead and a stupid implementation by me masked the expected behavior.
PS.:最后我应该将这篇文章重新命名为关于 BigInts 的学习课程"
推荐答案
For 循环实际上并不完全是循环；他们是为了理解范围.如果你真的想要一个循环，你需要使用while.(实际上，我认为这里的 BigInt 乘法已经足够重量级了，所以应该没有关系.但是如果您乘以 Int ，您会注意到.)
For loops are not actually quite loops; they're for comprehensions on a range. If you actually want a loop, you need to use while. (Actually, I think the BigInt multiplication here is heavyweight enough so it shouldn't matter. But you'll notice if you're multiplying Ints.)
此外，您还使用 BigInt 混淆了自己.BigInt 越大，乘法越慢.所以你的非尾循环向上计数，而你的尾递归循环向下计数，这意味着后者有更多的大数可以相乘.
Also, you have confused yourself by using BigInt. The bigger your BigInt is, the slower your multiplication. So your non-tail loop counts up while your tail recursion loop counds down which means that the latter has more big numbers to multiply.
如果你解决了这两个问题，你会发现理智恢复了:循环和尾递归的速度相同，常规递归和for都更慢.(如果JVM优化使其等效，正则递归可能不会更慢)
If you fix these two issues you will find that sanity is restored: loops and tail recursion are the same speed, with both regular recursion and for slower. (Regular recursion may not be slower if the JVM optimization makes it equivalent)
(另外，堆栈溢出修复可能是因为 JVM 开始内联并且可能使调用本身进行尾递归，或者将循环展开足够远以便您不再溢出.)
(Also, the stack overflow fix is probably because the JVM starts inlining and may either make the call tail-recursive itself, or unrolls the loop far enough so that you don't overflow any longer.)
最后，使用 for 和 while 的结果很差，因为您在右边乘以小数而不是左边.事实证明，Java 的 BigInt 乘法更快，左边的数字越小.
Finally, you're getting poor results with for and while because you're multiplying on the right rather than the left with the small number. It turns out that the Java's BigInt multiplies faster with the smaller number on the left.
这篇关于Scala 递归与循环:性能和运行时注意事项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！