测试列表是否包含另一个Python列表

Question

如何测试列表是否包含另一个列表(即,它是一个连续的子序列).假设有一个名为contains的函数:

contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]

编辑:

contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]

Answer 1

如果所有项目都是唯一的,则可以使用集合.

>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False

Answer 2

这是我的版本:

def contains(small, big):
    for i in xrange(len(big)-len(small)+1):
        for j in xrange(len(small)):
            if big[i+j] != small[j]:
                break
        else:
            return i, i+len(small)
    return False

它返回一个(开始,结束+ 1)的元组,因为我认为这更像是pythonic,正如Andrew Jaffe在他的评论中指出的那样.它没有对任何子列表进行切片,因此应该合理有效.

对于新手感兴趣的一点是,它使用了else子句for语句 -这是不是我用的很频繁,但能在这样的情况是非常宝贵的.

这与在字符串中查找子字符串相同,因此对于大型列表,实现类似Boyer-Moore算法的方法可能更有效.

Answer 3

有一个all()和any()功能来做到这一点.检查list1是否包含list2中的所有元素

result = all(elem in list1 for elem in list2)

检查list1是否包含list2中的任何元素

result = any(elem in list1 for elem in list2)

变量result将是boolean(TRUE/FALSE).

Answer 4

这有效并且相当快，因为​​它使用内置list.index()方法和==运算符进行线性搜索：

def contains(sub, pri):
    M, N = len(pri), len(sub)
    i, LAST = 0, M-N+1
    while True:
        try:
            found = pri.index(sub[0], i, LAST) # find first elem in sub
        except ValueError:
            return False
        if pri[found:found+N] == sub:
            return [found, found+N-1]
        else:
            i = found+1

Answer 5

如果列表真的很大，我可以谦虚地建议Rabin-Karp 算法big。该链接甚至包含几乎可用的 Python 代码。

Answer 6

我总结并评估了不同技术所花费的时间

使用的方法有：

def containsUsingStr(sequence, element:list):
    return str(element)[1:-1] in str(sequence)[1:-1]


def containsUsingIndexing(sequence, element:list):
    lS, lE = len(sequence), len(element)
    for i in range(lS - lE + 1):
        for j in range(lE):
            if sequence[i+j] != element[j]: break
        else: return True
    return False


def containsUsingSlicing(sequence, element:list):
    lS, lE = len(sequence), len(element)
    for i in range(lS - lE + 1):
        if sequence[i : i+lE] == element: return True
    return False


def containsUsingAny(sequence:list, element:list):
    lE = len(element)
    return any(element == sequence[i:i+lE] for i in range(len(sequence)-lE+1))

时间分析代码（平均超过 1000 次迭代）：

from time import perf_counter

functions = (containsUsingStr, containsUsingIndexing, containsUsingSlicing, containsUsingAny)
fCount = len(functions)


for func in functions:
    print(str.ljust(f'Function : {func.__name__}', 32), end='   ::   Return Values: ')
    print(func([1,2,3,4,5,5], [3,4,5,5]) , end=', ')
    print(func([1,2,3,4,5,5], [1,3,4,5]))



avg_times = [0]*fCount
for _ in range(1000):
    perf_times = []
    for func in functions:
        startTime = perf_counter()
        func([1,2,3,4,5,5], [3,4,5,5])
        timeTaken = perf_counter()-startTime
        perf_times.append(timeTaken)
        

    for t in range(fCount): avg_times[t] += perf_times[t]

minTime = min(avg_times)
print("\n\n Ratio of Time of Executions : ", ' : '.join(map(lambda x: str(round(x/minTime, 4)), avg_times)))

输出：

结论：在这种情况下，切片操作被证明是最快的