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

Question

假设给出了两个元素列表，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)

我现在想知道这个解决方案如何处理可能非常非常大的输入。假设我的列表包含数十亿个数字。

• 上面代码的复杂度是多少？它最坏的情况是什么？我试图用非常大的随机输入来测试它，但它的速度主要取决于自动生成的输入。
• 最重要的是，有没有更有效的解决方案？为什么这些解决方案比这个解决方案更有效？

Answer 1

您找到的代码创建了一个迭代器A；您可以将其视为指向要查看的下一个位置的简单指针A，并将in指针向前移动，A直到找到匹配项。它可以多次使用，但只能向前移动；当in多次对单个迭代器使用包含测试时，迭代器不能倒退，因此只能测试仍要访问的值是否等于左侧操作数。

鉴于您的最后一个示例，使用B = [2, 7, 2]，会发生以下情况：

• it = iter(A)为A列表创建一个迭代器对象，并将其存储0为下一个要查看的位置。
• 该all()函数测试可迭代对象中的每个元素，如果找到这样的结果，则返回False early。否则它会不断测试每个元素。这里的测试是重复x in it调用， where依次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。位置计数器增加到9。
  • 没有，A[9]因为 中没有那么多元素A，因此False返回。
• 2 in it是False，所以all()以返回结束False。

您可以使用具有副作用的迭代器来验证这一点；在这里，我曾经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，那么最好的情况是其中的所有K 个元素B都等于 的前K 个元素A。最坏的情况下，是任何其中不是所有的元件的情况下，B存在于A，和需要一个完整的扫描通过A。中存在多少个元素并不重要B；如果你正在测试元素ķ出ķ你已经被扫描部分的方式，通过A和必须完成的扫描，通过A找到的最后一个元素缺失。

所以最好的情况是N 个元素 inA和K 个元素 in B，需要 O(K) 时间。最坏的情况，使用N和K的相同定义，需要 O(N) 时间。

没有更快的算法来测试这种情况，因此您所能希望的只是降低您的常数时间（完成N步中的每一步所花费的时间）。在这里，A当您搜索B. 我不知道比使用您已经找到的方法更好的方法。