Kotlin挂起函数递归调用 [英] Kotlin suspend function recursive call
本文介绍了Kotlin挂起函数递归调用的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
突然发现,在没有suspend
修饰符的情况下,递归调用Suspend函数比调用相同的函数需要更多的时间,所以请考虑下面的代码片段(基本斐波那契级数计算):
suspend fun asyncFibonacci(n: Int): Long = when {
n <= -2 -> asyncFibonacci(n + 2) - asyncFibonacci(n + 1)
n == -1 -> 1
n == 0 -> 0
n == 1 -> 1
n >= 2 -> asyncFibonacci(n - 1) + asyncFibonacci(n - 2)
else -> throw IllegalArgumentException()
}
如果我调用此函数并使用以下代码测量其执行时间:
fun main(args: Array<String>) {
val totalElapsedTime = measureTimeMillis {
val nFibonacci = 40
val deferredFirstResult: Deferred<Long> = async {
asyncProfile("fibonacci") { asyncFibonacci(nFibonacci) } as Long
}
val deferredSecondResult: Deferred<Long> = async {
asyncProfile("fibonacci") { asyncFibonacci(nFibonacci) } as Long
}
val firstResult: Long = runBlocking { deferredFirstResult.await() }
val secondResult: Long = runBlocking { deferredSecondResult.await() }
val superSum = secondResult + firstResult
println("${thread()} - Sum of two $nFibonacci'th fibonacci numbers: $superSum")
}
println("${thread()} - Total elapsed time: $totalElapsedTime millis")
}
我观察到进一步的结果:
commonPool-worker-2:fibonacci - Start calculation...
commonPool-worker-1:fibonacci - Start calculation...
commonPool-worker-2:fibonacci - Finish calculation...
commonPool-worker-2:fibonacci - Elapsed time: 7704 millis
commonPool-worker-1:fibonacci - Finish calculation...
commonPool-worker-1:fibonacci - Elapsed time: 7741 millis
main - Sum of two 40'th fibonacci numbers: 204668310
main - Total elapsed time: 7816 millis
但如果我从asyncFibonacci
函数中删除suspend
修饰符,我将得到以下结果:
commonPool-worker-2:fibonacci - Start calculation...
commonPool-worker-1:fibonacci - Start calculation...
commonPool-worker-1:fibonacci - Finish calculation...
commonPool-worker-1:fibonacci - Elapsed time: 1179 millis
commonPool-worker-2:fibonacci - Finish calculation...
commonPool-worker-2:fibonacci - Elapsed time: 1201 millis
main - Sum of two 40'th fibonacci numbers: 204668310
main - Total elapsed time: 1250 millis
我知道用tailrec
重写这样的函数会增加它的执行时间APX。几乎是100次,但无论如何,这个suspend
关键字会将执行速度从1秒降低到8秒吗?
用suspend
标记递归函数是不是很愚蠢?
推荐答案
作为介绍性注释,您的测试代码设置太复杂。这段简单得多的代码在强调suspend fun
递归:
fun main(args: Array<String>) {
launch(Unconfined) {
val nFibonacci = 37
var sum = 0L
(1..1_000).forEach {
val took = measureTimeMillis {
sum += suspendFibonacci(nFibonacci)
}
println("Sum is $sum, took $took ms")
}
}
}
suspend fun suspendFibonacci(n: Int): Long {
return when {
n >= 2 -> suspendFibonacci(n - 1) + suspendFibonacci(n - 2)
n == 0 -> 0
n == 1 -> 1
else -> throw IllegalArgumentException()
}
}
我试图通过编写一个普通函数来再现其性能,该函数近似于suspend
函数为实现可挂起而必须执行的操作类型:
val COROUTINE_SUSPENDED = Any()
fun fakeSuspendFibonacci(n: Int, inCont: Continuation<Unit>): Any? {
val cont = if (inCont is MyCont && inCont.label and Integer.MIN_VALUE != 0) {
inCont.label -= Integer.MIN_VALUE
inCont
} else MyCont(inCont)
val suspended = COROUTINE_SUSPENDED
loop@ while (true) {
when (cont.label) {
0 -> {
when {
n >= 2 -> {
cont.n = n
cont.label = 1
val f1 = fakeSuspendFibonacci(n - 1, cont)!!
if (f1 === suspended) {
return f1
}
cont.data = f1
continue@loop
}
n == 1 || n == 0 -> return n.toLong()
else -> throw IllegalArgumentException("Negative input not allowed")
}
}
1 -> {
cont.label = 2
cont.f1 = cont.data as Long
val f2 = fakeSuspendFibonacci(cont.n - 2, cont)!!
if (f2 === suspended) {
return f2
}
cont.data = f2
continue@loop
}
2 -> {
val f2 = cont.data as Long
return cont.f1 + f2
}
else -> throw AssertionError("Invalid continuation label ${cont.label}")
}
}
}
class MyCont(val completion: Continuation<Unit>) : Continuation<Unit> {
var label = 0
var data: Any? = null
var n: Int = 0
var f1: Long = 0
override val context: CoroutineContext get() = TODO("not implemented")
override fun resumeWithException(exception: Throwable) = TODO("not implemented")
override fun resume(value: Unit) = TODO("not implemented")
}
您必须用
调用此函数sum += fakeSuspendFibonacci(nFibonacci, InitialCont()) as Long
其中InitialCont
是
class InitialCont : Continuation<Unit> {
override val context: CoroutineContext get() = TODO("not implemented")
override fun resumeWithException(exception: Throwable) = TODO("not implemented")
override fun resume(value: Unit) = TODO("not implemented")
}
基本上,要编译suspend fun
,编译器必须将其主体转换为状态机。每次调用还必须创建一个对象来保存机器的状态。当您恢复时,State对象告诉您要转到哪个状态处理程序。以上内容仍然不是全部,真正的代码甚至更复杂。
在解释模式(java -Xint
)中,我获得的性能几乎与实际的suspend fun
相同,并且比启用JIT的实际模式快不到两倍。相比之下,"直接"函数实现的速度大约是它的10倍。这意味着显示的代码解释了可挂起开销的很大一部分。
这篇关于Kotlin挂起函数递归调用的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文