在python中运行列表的子集

Question

是否可以在python列表中运行子集？

我有以下问题,我有两个列表,list1很长list2很短.现在,我想检查哪些元素list2也在list1.我当前的版本如下所示:

for item in list1:
    if item in list2:
        # do something

这需要很长时间.是否有可能获得一个子集然后运行列表？

我需要多次这样做.

Answer 1

如果列表元素是可清除的,则可以使用集合找到交集:

>>> for x in set(list2).intersection(list1):
        print x

如果它们不可清除,您至少可以通过对较短列表进行排序并进行二分查找来加速搜索:

>>> from bisect import bisect_left
>>> list2.sort()
>>> n = len(list2)
>>> for x in list1:
        i = bisect_left(list2, x)
        if i != n and list2[i] == x:
            print x

如果您的数据元素既不可播放也不可排序,那么您将无法加速原始代码:

>>> for x in list1:
        if x in list2:
            print x

集合交叉方法的运行时间与两个列表的长度之和成正比O(n1 + n2).二分搜索方法的运行时间是O((n1 + n2) * log(n2)).原始蛮力方法的运行时间是O(n1 * n2).