Scala递归与循环:性能和运行时考虑因素

Question

我编写了一个天真的测试平台来测量三种阶乘实现的性能:基于循环,非尾递归和尾递归.

令我惊讶的是,最差的性能是循环的(«while»预计效率更高,所以我提供了两者) ,其成本几乎是尾部递归替代的两倍.

答案:修复循环实现,避免使用BigInt的*=运算符,因为其内部«循环»变得如预期的那样快

我遇到的另一个"woodoo"行为是StackOverflow异常,在非尾递归实现的情况下,对于相同的输入没有抛出异常.我可以通过逐步调用具有越来越大的值的函数来规避StackOverlow ...我感到很疯狂:) 答案: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控制台的一些输出(Before«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控制台的一些输出(After«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开销和我的愚蠢实现掩盖了预期的行为.

多谢你们

PS.:最后我应该将这篇文章重新命名为«关于BigInts的课程»

Answer 1

For循环实际上并不是完全循环; 他们是对范围的理解.如果你真的想要一个循环,你需要使用while.(实际上,我认为BigInt这里的乘法很重,所以它应该没关系.但你会注意到你是否乘以Ints.)

此外,你使用混淆了自己BigInt.你的越大BigInt,你的乘法越慢.因此,当你的尾递归循环减少时,你的非尾循环会计数,这意味着后者有更大的数字可以乘以.

如果你修复了这两个问题,你会发现恢复了理智:循环和尾递归速度相同,常规递归和for慢速.(如果JVM优化使其等效,则常规递归可能不会更慢)

(此外,堆栈溢出修复可能是因为JVM开始内联,并且可能使调用尾部递归,或者将循环展开得足够远,以便不再溢出.)

最后,你用for和while会得到糟糕的结果,因为你在右边而不是在左边乘以小数字.事实证明,Java的BigInt与左侧较小的数字相乘的速度更快.