algorithm - 组合:两个线程访问的变量

Question

线程 A 和 B 可以并发访问单个变量。每个线程对变量执行一系列访问(读取和写入)。每个线程将读取的结果存储到一个数组中。 session 的结果由两个数组定义。

给定线程执行的访问可能不会重新排序。但是，来自两个线程的访问可能会交错，因此结果将取决于这种交错。 在给定两个访问序列的情况下，我们如何有效地计算可能结果的数量？假设所有写入都产生不同的值。

    Example access sequences:
        Thread A: [write(71), read()]
        Thread B: [read(), write(72), write(73), read()]

    Example interleaving:
        [a_write(71), b_read(), b_write(72), a_read(), b_write(73), b_read()]

    Example outcome:
        a_results = [72]
        b_results = [71, 73]

附言这不是作业，这只是我自己构想的问题。

Answer 1

这看起来像是可以用动态规划解决的问题。

我建议寻找解决子问题的方法:

How many distinct outcomes are there given that we have done x accesses from thread 1, y accesses from thread 2, and the last access was a write that was done by thread z (either 1 or 2).

DP 数组将是 3 维的:DP[x][y][z]。

DP中总共会有2 * (线程1的访问次数) * (线程2的访问次数)个slot需要计算。

要填充数组中的每个条目，您需要对数组的前几个条目求和，因此我怀疑整体复杂度约为 O(n^3)，其中 n 是访问次数。