gpt4 book ai didi

performance - Scala递归与循环: performance and runtime considerations

转载 作者:行者123 更新时间:2023-12-03 09:45:57 30 4
gpt4 key购买 nike

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

Surprisingly to me the worst performant was the loop ones («while» was expected to be more efficient so I provided both) that costalmost twice than the tail recursive alternative.


*答案:修复循环实现,避免=运算符因其内部“循环”变得比预期更快而在BigInt上表现最差

Another «woodoo» behavior I've experienced was the StackOverflowexception which wasn't thrown systematically for the same input in thecase of non-tail recursive implementation. I can circumvent theStackOverlow by progressively call the function with larger and largervalues… I feel crazy :) Answer: JVM require to converge during startup, then behavior is coherent and systematic


这是代码:
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控制台的一些输出(在«upward»尾递归实现之后),世界恢复了健全的:
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
接下来是在«loops»中修复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上的一个类”

最佳答案

for循环实际上并不是完全的循环。他们是对范围的理解。如果您实际上想要循环,则需要使用while。 (实际上,我认为这里的BigInt乘法足够重,因此没有关系。但是您会注意到是否要乘Int。)

另外,您还使用BigInt混淆了自己。 BigInt越大,乘法就越慢。因此,您的非尾循环递增,而尾递归循环递减,这意味着后者有更多的数字可乘。

如果解决了这两个问题,您会发现恢复了理智性:循环和尾部递归的速度相同,常规递归和for的速度都更慢。 (如果JVM优化使常规递归等效,则递归可能不会慢一些)

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

最后,for和while会导致结果不佳,因为您是在右边而不是左边乘以较小的数字。事实证明,Java的BigInt与左侧的较小数字相乘更快。

关于performance - Scala递归与循环: performance and runtime considerations,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15138624/

30 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com