执行持续时间与暂停功能的巨大差异

Question

我仍在试图将我的头缠绕在悬挂功能上，以及io-bound和cpu结合的暂停功能之间的差异(如果有的话(以及其他方面。

我正在主线程中启动Coroutine，并以不同的方式运行CPU密集型功能以查看发生的情况。

class TestActivity : AppCompatActivity(), CoroutineScope {
    private val job = Job()
    override val coroutineContext: CoroutineContext
        get() = job + Dispatchers.Main
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)
        launch {
            val start = System.currentTimeMillis()
            Log.d("test", "start: $start")
            fib(24)
            val finish = System.currentTimeMillis()
            Log.d("test", "finish: $finish")
            Log.d("test", "duration: ${finish - start}")
        }
    }

我尝试了fib函数的这三个变体：

private fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

常规方式：XML不会立即膨胀，并且该功能需要0.1秒才能运行。

private suspend fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

常规方式 suspend关键字：XML不会立即夸大，并且该功能需要1.3秒才能运行。

private suspend fun fib(x: Int): Int =
    withContext(Dispatchers.Default) { if (x <= 1) x else fib(x - 1) + fib(x - 2) }

常规方式 suspend关键字 用withContext(Dispatchers.Default)包装它：XML立即夸大，并且该功能需要25秒才能运行。

任何人都可以阐明为什么三个函数之间的持续时间有如此不同？

Answer 1

private fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

这是您的基本情况，是斐波那契的极其效率的递归实施。它与fib(x - 2)完全独立地计算fib(x - 1)，这导致函数调用的指数爆炸。要计算 fib(24)，它可以制作约(黄金比率( ²⁴ = 103,682调用。

private suspend fun fib(x: Int): Int =
    if (x <= 1) x else fib(x - 1) + fib(x - 2)

语义上这与上述完全相同。一个声明为暂停的函数，但悬架点为零。由于CPS转换的开销固有固定的功能。

private suspend fun fib(x: Int): Int =
    withContext(Dispatchers.Default) { if (x <= 1) x else fib(x - 1) + fib(x - 2) }

在这里，您实际上实现了一些并行性，但是平行的加速与派遣非常小的工作的开销相形见war。另外，由于要计算fibonacci序列的第n个成员，您需要(n -1(和(n -2(已经计算出来，创建一系列数据依赖关系，一直到基本情况，您无法真正真正并行化斐波那契。在您的情况下，您可以对同一成员进行大量重新计算，因此可以通过并行性进行改进，但仍然无法正确实现的单线读取解决方案。