检查序列是否包含非连续子序列的最快方法？

Question

检查序列是否包含非连续子序列的最快方法？

pythonpython-3.xalgorithmtime-complexity

3

假设有两个元素列表A和B。我想检查A是否包含了B的所有元素。具体来说，这些元素必须按照相同的顺序出现，它们不需要是连续的。如果是这种情况，我们称B是A的一个子序列。

以下是一些例子：

A = [4, 2, 8, 2, 7, 0, 1, 5, 3]
B = [2, 2, 1, 3]
is_subsequence(A, B) # True

A = [4, 2, 8, 2, 7, 0, 1, 5, 3]
B = [2, 8, 2]
is_subsequence(A, B) # True

A = [4, 2, 8, 2, 7, 0, 1, 5, 3]
B = [2, 1, 6]
is_subsequence(A, B) # False

A = [4, 2, 8, 2, 7, 0, 1, 5, 3]
B = [2, 7, 2]
is_subsequence(A, B) # False

我发现一种很优雅的方法来解决这个问题（参见这个答案）：

def is_subsequence(A, B):
    it = iter(A)
    return all(x in it for x in B)

我现在想知道这个解决方案在可能有非常非常大的输入时的表现。比方说，我的列表包含数十亿个数字。

上述代码的复杂度是什么？它的最坏情况是什么？我已经试过用非常大的随机输入进行测试，但它的速度大多取决于自动生成的输入。
更重要的是，是否有更有效的解决方案？这些解决方案为什么比这个更有效？

- Riccardo Bucco

2

@Austin 这并不能保留顺序要求。我相信这个问题已经有答案了（虽然不是关于Python的）：https://stackoverflow.com/questions/33174985/how-do-you-check-if-one-array-is-a-subsequence-of-another - sshashank124

@sshashank124 我已经阅读了那个答案，并且正在尝试在Python中实现这些算法，以检查它们是否比这种方法更快。但我仍然不确定这种方法的复杂度（特别是最坏情况下的复杂度）。 - Riccardo Bucco

@sshashank124：all(x in it for x in B)方法本质上是Blinkenlight算法的更紧凑形式。 - Martijn Pieters

如果较大的列表是固定的并且需要重复搜索，则我会将其制作成一个映射表，并进行查找。 - Salim

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martijn Pieters · Accepted Answer

您找到的代码为A创建了一个迭代器；您可以将其视为指向A中下一个位置的简单指针，而in则在A上向前移动该指针，直到找到匹配项。它可被多次使用，但仅会向前移动；当使用in包含性测试多次针对单个迭代器时，该迭代器不能后退，因此只能测试尚未访问值是否等于左操作数。

给出您的最后一个示例，即B = [2, 7, 2]，以下是发生的情况：

it = iter(A) 创建一个迭代器对象来遍历 A 列表，并将下一个要查看的位置设为 0。
all() 函数会测试可迭代对象中的每个元素，如果找到 False 结果，则提前返回。否则它会继续测试每个元素。这里的测试是通过重复调用 x in it 来进行的，其中 x 依次设置为 B 中的每个值。
首先将 x 设置为 2，因此测试 2 in it。
- it 被设置为下一个查看的位置是 A[0]。那是 4，不等于 2，所以内部位置计数器递增为 1。
- A[1] 是 2，是相等的，所以此时 2 in it 返回 True，但在递增“下一个查看的位置”的计数器到 2 之前不返回任何内容。
由于 2 in it 是真的，因此 all() 继续往下执行。
B 中的下一个值是 7，因此测试 7 in it。
- it 被设置为下一个查看的位置是 A[2]。那是 8，不是 7，所以位置计数器递增到 3。
- it 被设置为下一个查看的位置是 A[3]。那是 2，不是 7，所以位置计数器递增到 4。
- it 被设置为下一个查看的位置是 A[4]。那是 7，等于 7。位置计数器递增到 5 并返回 True。
由于 7 in it 是真的，因此 all() 继续往下执行。
B 中的下一个值是 2，因此测试 2 in it。
- it 被设置为下一个查看的位置是 A[5]。那是 0，不是 2，所以位置计数器递增到 6。
- it 被设置为下一个查看的位置是 A[6]。那是 1，不是 2，所以位置计数器递增到 7。
- it 被设置为下一个查看的位置是 A[7]。那是 5，不是 2，所以位置计数器递增到 8。
- it 被设置为下一个查看的位置是 A[8]。那是 3，不是 2，所以位置计数器递增到 < 你可以通过带有可观察的副作用的迭代器来验证这一点；在这里，我使用print()来输出给定输入的下一个值：
```
>>> A = [4, 2, 8, 2, 7, 0, 1, 5, 3]
>>> B = [2, 7, 2]
>>> with_sideeffect = lambda name, iterable: (
    print(f"{name}[{idx}] = {value}") or value
    for idx, value in enumerate(iterable)
)
>>> is_sublist(with_sideeffect("  > A", A), with_sideeffect("< B", B))
< B[0] = 2
  > A[0] = 4
  > A[1] = 2
< B[1] = 7
  > A[2] = 8
  > A[3] = 2
  > A[4] = 7
< B[2] = 2
  > A[5] = 0
  > A[6] = 1
  > A[7] = 5
  > A[8] = 3
False
```
  您的问题要求您连续测试B的每个元素，这里没有捷径。您还必须扫描A以测试B的元素是否存在且顺序正确。只有当找到B的所有元素（部分扫描）时，才能宣布胜利；当扫描完A的所有元素且未发现您正在测试的B中的当前值时，才能宣布失败。
  因此，假设B的大小始终小于A，则最好的情况是B中的所有K个元素都等于A的前K个元素。最坏的情况是A中不包含B的所有元素，并且需要完全扫描A。无论B中有多少个元素，如果您正在测试第K个元素，则您已经部分扫描了A，必须完成对A的扫描才能发现缺少的最后一个元素。
  因此，在相同的N和K定义下，最佳情况下需要O(K)时间，最坏情况下需要O(N)时间。
  没有更快的算法来测试此条件，因此您能够做的就是降低常数时间（完成每个N步所需的时间）。在这里，更快的扫描A的方法是搜索B中的元素。我不知道比使用您已经发现的方法更好的方法。