以下是Cay Horstmann的《Scala快速入门》中练习4.9的两个解决方案：“编写一个函数lteqgt（values：Array [Int]，v：Int），返回一个三元组，其中包含小于v的值的计数，等于v的值的计数和大于v的值的计数。” 其中一个使用尾递归，另一个使用while循环。我以为两者都会编译成类似的字节码，但while循环比尾递归慢近2倍。这让我觉得我的while方法写得很糟糕。
为什么while方法比tailrec方法慢很多？表面上看，tailrec版本似乎处于劣势，因为它必须在每次迭代中始终执行3个“if”检查，而while版本由于else结构的存在通常只需要执行1或2个测试。（注意，反转我执行这两种方法的顺序不会影响结果）。
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版本由于else结构的存在通常只需要执行1或2个测试。（注意，反转我执行这两种方法的顺序不会影响结果）。