是否可以使用协程加速动态规划问题？

Question

我有以下最长公共子序列问题的实现：递归+记忆表。 我的问题是：是否可以使用协同程序，以便以使用异步函数为代价提高代码的性能？ 有人可以提出一个想法（链接到指南/文章等），如何实施它？ 基准在这里.

提前谢谢你;-)

Answer 1

协程是编写异步代码的强大工具，但它们不一定最适合加速动态编程问题，例如您提供的最长公共子序列 (LCS) 问题。协程的主要好处是它们使您能够在处理非阻塞 IO 操作或其他可以并行运行的任务时有效地管理并发性。然而，在 LCS 问题的情况下，主要瓶颈可能是计算本身，而不是等待 IO 操作。

为了加速您的动态编程解决方案，您可以考虑使用并行或多线程将工作分配给多个 CPU 内核。在 Kotlin 中，您可以使用

kotlinx.coroutines

库来利用其

async

和

await

结构的并行性。下面是一个示例，说明如何修改

lcs

函数以利用并行性：

import kotlinx.coroutines.async
import kotlinx.coroutines.awaitAll
import kotlinx.coroutines.coroutineScope

suspend fun lcs(index1: Int, index2: Int): String = coroutineScope {
    if (index1 == s1.length || index2 == s2.length) {
        return@coroutineScope ""
    }
    if (s1[index1] == s2[index2]) {
        if (memoization[index1][index2] == "") {
            memoization[index1][index2] =
                s1[index1] + lcs(index1 + 1, index2 + 1)
        }
        memoization[index1][index2]
    } else {
        if (memoization[index1][index2] == "") {
            val op1 = async { lcs(index1, index2 + 1) }
            val op2 = async { lcs(index1 + 1, index2) }
            val results = awaitAll(op1, op2)
            memoization[index1][index2] = if (results[0].length > results[1].length) results[0] else results[1]
        }
        memoization[index1][index2]
    }
}