判断一个列表中的所有元素是否在另一个列表中且顺序相同

Question

我想创建一个叫做 sublist() 的函数，这个函数需要接收两个列表，list1 和 list2。如果 list1 是 list2 的子列表，就返回 True；如果不是，就返回 False。这里说的“子列表”是指 list1 中的数字在 list2 中出现的顺序和 list1 中的顺序是一样的，但不一定要是连续的。例如，

>>> sublist([1, 12, 3],[25, 1, 30, 12, 3, 40])
True

>>> sublist([5, 90, 2],[90, 20, 5, 2, 17])
False

Answer 1

这里有一个迭代的解决方案，它的效率应该是最优的：

def sublist(x, y):
    if x and not y:
        return False
    i, lim = 0, len(y)
    for e in x:
        while e != y[i]:
            i += 1
            if i == lim:
                return False
        i += 1
    return True

@sshashank124 的解决方案复杂度是一样的，但它的处理方式会有些不同：他的版本会多次遍历第二个参数，不过因为它把更多的工作交给了 C 语言层，所以在处理小数据时可能会快很多。

编辑：@hetman 的解决方案基本上逻辑相同，但更符合 Python 的风格，尽管出乎我的意料，它似乎稍微慢了一点。（我之前对 @sshashank124 的解决方案的性能判断也不对；递归调用的开销似乎超过了在 C 中做更多工作的好处。）

Answer 2

恭喜你提出了一个看似简单但其实很难的问题。我觉得这个方法可能有效，但如果我漏掉了某些特殊情况，尤其是重复元素的情况，我也不会感到惊讶。下面是受Hgu Nguyen的递归解法启发的改进版本：

def sublist(a, b):
    index_a = 0
    index_b = 0
    len_a = len(a)
    len_b = len(b)
    while index_a < len_a and index_b < len_b:
        if a[index_a] == b[index_b]:
            index_a += 1
            index_b += 1
        else:
            index_b += 1
    return index_a == len_a

这里有一些粗略的性能测试：

当需要遍历大部分或全部的b列表时，我的算法表现不佳：

a = [1, 3, 999999]
b = list(range(1000000))

在我的电脑上，Huu Nguyen或Hetman的算法运行100次检查大约需要10秒，而我的算法则需要20秒。

在之前的成功案例中，Huu的算法表现明显落后：

a = [1, 3, 5]

Hetman的算法或我的算法可以在不到一秒的时间内完成10万次检查——在我的电脑上，Hetman的算法用时0.13秒，我的用时0.19秒。而Huu的算法完成1000次检查则需要16秒。我对这种差距感到非常震惊——我知道递归如果没有经过编译器优化会很慢，但这种差距比我预期的要大得多。

当给定一个失败的列表a时，性能又回到了我在需要遍历整个第二个列表时看到的情况——这很容易理解，因为我们无法知道在最后是否会有一个与其他无法匹配的列表相匹配的序列。

a = [3, 1, 5]

再次提到，Huu Nguyen或Hetman的算法在100次测试中大约需要10秒，而我的则需要20秒。

更长的有序列表保持了我在早期成功时看到的模式。例如：

a = range(0, 1000, 20)

使用Hetman的算法完成10万次测试需要10.99秒，而我的算法则需要24.08秒。Huu的算法完成100次测试则需要28.88秒。

这些测试确实不是你可以运行的全部范围，但在所有情况下，Hetman的算法表现最好。

Answer 3

这里是一个简化版：

def sublist(a,b):
    try:
        return a[0] in b and sublist(a[1:],b[1+b.index(a[0]):])
    except IndexError:
        return True

>>> print sublist([1, 12, 3],[25, 1, 30, 12, 3, 40])
True

>>> print sublist([5, 90, 2],[90, 20, 5, 2, 17])
False

Answer 4

这是一个非常粗略的解决方案：

def sublist(a, b):
    if not a:
        return True
    for k in range(len(b)):
        if a[0] == b[k]:
            return sublist(a[1:], b[k+1:])
    return False

print sublist([1, 12, 3], [25, 1, 30, 12, 3, 40]) # True
print sublist([12, 1, 3], [25, 1, 30, 12, 3, 40]) # False

编辑：速度提升

Answer 5

这里有一种方法可以在时间上做到线性（也就是随着数据量增加，处理时间只增加一点点），而且只用固定的空间，使用迭代器来实现：

def sublist(a, b):
    seq = iter(b)
    try:
        for x in a:
            while next(seq) != x: pass
        else:
            return True
    except StopIteration:
        pass
    return False

基本上，它会逐个检查子列表中的每个元素，看看能不能在还没检查过的完整列表部分找到相同的元素。如果子列表的所有元素都能找到对应的，那就说明匹配成功（所以在for循环中的else语句就是这个意思）。如果完整列表的元素都检查完了还没找到匹配，那就说明没有匹配。

补充说明：我更新了我的解决方案，现在可以在Python 3中使用。如果你用的是Python 2.5或更早的版本，next(seq)需要换成seq.next()。