递归比while循环更快？
下面是在Cay Horstmann的Scala中为Impatient实践4.9的两个解决方案：“编写一个函数lteqgt（values：Array [Int]，v：Int），返回一个包含小于v的值的计数的三元组，等于v，并且大于v“。 一个使用尾递归，另一个使用while循环。 我认为两者都会编译成相似的字节码，但while循环比尾递归要慢2倍。这表明我的while方法写得不好。
import scala.annotation.tailrec
import scala.util.Random
object PerformanceTest {
def main(args: Array[String]): Unit = {
val bigArray:Array[Int] = fillArray(new Array[Int](100000000))
println(time(lteqgt(bigArray, 25)))
println(time(lteqgt2(bigArray, 25)))
}
def time[T](block : => T):T = {
val start = System.nanoTime : Double
val result = block
val end = System.nanoTime : Double
println("Time = " + (end - start) / 1000000.0 + " millis")
result
}
@tailrec def fillArray(a:Array[Int], pos:Int=0):Array[Int] = {
if (pos == a.length)
a
else {
a(pos) = Random.nextInt(50)
fillArray(a, pos+1)
}
}
@tailrec def lteqgt(values: Array[Int], v:Int, lt:Int=0, eq:Int=0, gt:Int=0, pos:Int=0):(Int, Int, Int) = {
if (pos == values.length)
(lt, eq, gt)
else
lteqgt(values, v, lt + (if (values(pos) < v) 1 else 0), eq + (if (values(pos) == v) 1 else 0), gt + (if (values(pos) > v) 1 else 0), pos+1)
}
def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
var lt = 0
var eq = 0
var gt = 0
var pos = 0
val limit = values.length
while (pos < limit) {
if (values(pos) > v)
gt += 1
else if (values(pos) < v)
lt += 1
else
eq += 1
pos += 1
}
(lt, eq, gt)
}
}
根据堆大小调整bigArray的大小。 以下是一些示例输出：
Time = 245.110899 millis
(50004367,2003090,47992543)
Time = 465.836894 millis
(50004367,2003090,47992543)
为什么while方法比tailrec慢得多？ 天真的tailrec版本看起来有点不利，因为它必须始终执行3次“if”检查每次迭代，而while版本通常只会执行1次或2次测试，这是由于else结构。 （NB逆转我执行这两种方法的顺序不会影响结果）。
测试结果 （将阵列大小减少到20000000之后）
在Java 1.6.22我分别获得了尾递归和while循环的151 and 122 ms 。
在Java 1.7.0我得到55 and 101 ms
所以在Java 6下，你的while循环实际上更快; 在Java 7下性能都有所提高，但是尾递归版本已经超越了循环。
说明
性能的差异是因为在你的循环中，你有条件地给总数加1，而对于递归你总是添加1或0.所以它们是不等价的。 递归方法的等效while循环是：
def lteqgt2(values:Array[Int], v:Int):(Int, Int, Int) = {
var lt = 0
var eq = 0
var gt = 0
var pos = 0
val limit = values.length
while (pos < limit) {
gt += (if (values(pos) > v) 1 else 0)
lt += (if (values(pos) < v) 1 else 0)
eq += (if (values(pos) == v) 1 else 0)
pos += 1
}
(lt, eq, gt)
}
这与递归方法的执行时间完全相同（无论Java版本如何）。
讨论
我不是专家，为什么Java 7 VM（HotSpot）可以比你的第一个版本更好地优化它，但我想这是因为它每次都通过代码采用相同的路径（而不是沿着if / else if分支else if路径），所以字节码可以更有效地内联。
但请记住，在Java 6中情况并非如此。为什么一个while循环胜过另一个是JVM内部问题。 令人高兴的是，对于Scala程序员来说，从惯用尾递归产生的版本是JVM最新版本中速度更快的版本。
这种差异也可能发生在处理器级别。 看到这个问题，它解释了如果代码包含不可预知的分支，代码变慢。
这两个结构不完全相同。 特别是，在第一种情况下，你不需要任何跳转（在x86上，你可以使用cmp和setle并添加，而不必使用cmp和jb和（如果你不跳转）添加。比几乎每一个现代建筑都要跳跃。
所以，如果你的代码看起来像
if (a < b) x += 1
你可以添加或者你可以跳转，而不是
x += (a < b)
（这只在C / C ++中有意义，其中1 = true且0 = false），后者趋于更快，因为它可以变成更紧凑的汇编代码。 在Scala / Java中，你不能做到这一点，但你可以做到
x += if (a < b) 1 else 0
一个智能JVM应该识别的是与x + =（a <b）相同，它具有无跳转的机器码转换，这通常比跳转更快。 一个更聪明的JVM会认识到这一点
if (a < b) x += 1
也是一样的（因为加零不会做任何事情）。
C / C ++编译器经常执行像这样的优化。 无法应用任何这些优化在JIT编译器中并不是一个标志; 显然它可以是1.7，但只有部分（即它不认识到，加零与条件加1是一样的，但它至少将x += if (a<b) 1 else 0转换为快速机器码）。
现在，这些与尾递归或while循环本身没有任何关系。 使用尾递归更自然地写if (a < b) 1 else 0形式，但你可以做; 和while循环，你也可以做。 恰巧，你选择了一个表单来进行尾递归，另一个用于while循环，使得它看起来像递归与循环是变化，而不是两种不同的方式来执行条件。