两个列表之间的共同元素比较

问题描述：

给定两个输入列表，如何创建两个输入所共有元素的列表？

例如：对于输入[1,2,3,4,5,6]和[3,5,7,9]，结果应该是[3, 5]；对于输入['this','this','n','that']和['this','not','that','that']，结果应该是['this', 'that']。

参见：

• 在 Python 中，如何从两个列表中找到常用词同时保留词序？（保持顺序）

• Python-多个列表的交集？（用于计算> ​​= 3个列表之间的交集）

• 两个列表的交集包括重复项吗？（保留重复的元素）

解决方案 1：

使用 Python 的集合交集：

>>> list1 = [1,2,3,4,5,6]
>>> list2 = [3, 5, 7, 9]
>>> list(set(list1).intersection(list2))
[3, 5]

解决方案 2：

S.Mark和SilentGhost建议的解决方案通常会告诉您应该如何以 Pythonic 方式完成此操作，但我认为了解您的解决方案为何不起作用可能也会对您有所帮助。问题是，一旦您在两个列表中找到第一个公共元素，您只会返回该单个元素。您的解决方案可以通过创建一个result列表并收集该列表中的公共元素来解决：

def common_elements(list1, list2):
    result = []
    for element in list1:
        if element in list2:
            result.append(element)
    return result

使用列表推导的更短版本：

def common_elements(list1, list2):
    return [element for element in list1 if element in list2]

但是，正如我所说，这是一种非常低效的方法——Python 的内置集合类型效率更高，因为它们是在 C 内部实现的。

解决方案 3：

您还可以使用集合并在一行中获取共同点：从其中一个集合中减去包含差异的集合。

A = [1,2,3,4]
B = [2,4,7,8]
commonalities = set(A) - (set(A) - set(B))

解决方案 4：

您可以使用以下方法解决这个问题numpy：

import numpy as np

list1 = [1, 2, 3, 4, 5, 6]
list2 = [3, 5, 7, 9]

common_elements = np.intersect1d(list1, list2)
print(common_elements)

common_elements将是 numpy 数组：[3 5]。

解决方案 5：

使用集合交集，set(list1) & set(list2)

>>> def common_elements(list1, list2):
...     return list(set(list1) & set(list2))
...
>>>
>>> common_elements([1,2,3,4,5,6], [3,5,7,9])
[3, 5]
>>>
>>> common_elements(['this','this','n','that'],['this','not','that','that'])
['this', 'that']
>>>
>>>

请注意，结果列表的顺序可能与原始列表不同。

解决方案 6：

设置是解决这个问题的另一种方法

a = [3,2,4]
b = [2,3,5]
set(a)&set(b)
{2, 3}

解决方案 7：

我比较了每个答案提到的每种方法。目前，我使用 python 3.6.3 来实现此目的。这是我使用的代码：

import time
import random
from decimal import Decimal


def method1():
    common_elements = [x for x in li1_temp if x in li2_temp]
     print(len(common_elements))


def method2():
    common_elements = (x for x in li1_temp if x in li2_temp)
    print(len(list(common_elements)))


def method3():
    common_elements = set(li1_temp) & set(li2_temp)
    print(len(common_elements))


def method4():
    common_elements = set(li1_temp).intersection(li2_temp)
    print(len(common_elements))


if __name__ == "__main__":
    li1 = []
    li2 = []
    for i in range(100000):
        li1.append(random.randint(0, 10000))
        li2.append(random.randint(0, 10000))

    li1_temp = list(set(li1))
    li2_temp = list(set(li2))

    methods = [method1, method2, method3, method4]
    for m in methods:
        start = time.perf_counter()
        m()
        end = time.perf_counter()
        print(Decimal((end - start)))

如果您运行此代码，您会发现，如果您使用列表或生成器（如果您迭代生成器，而不仅仅是使用它。当我强制生成器打印其长度时，我这样做了），您将获得几乎相同的性能。但是如果您使用集合，您将获得更好的性能。此外，如果您使用交集方法，您将获得更好的性能。我的电脑中每种方法的结果如下所列：

1. 方法1：0.8150673999999999974619413478649221360683441

2. 方法2：0.8329545000000001531148541289439890533685684

3. 方法3：0.0016547000000000089414697868051007390022277

4. 方法4：0.001026299999999244948867271887138485908508

解决方案 8：

前面的答案都适用于查找唯一的公共元素，但无法解释列表中的重复项。如果您希望公共元素以与列表中相同的数量出现，则可以使用以下一行代码：

l2, common = l2[:], [ e for e in l1 if e in l2 and (l2.pop(l2.index(e)) or True)]

or True仅当您希望任何元素的计算结果为 时，该部分才是必要的False。

解决方案 9：

1）方法 1 保存 list1 为字典，然后迭代 list2 中的每个元素

def findarrayhash(a,b):
    h1={k:1 for k in a}
    for val in b:
        if val in h1:
            print("common found",val)
            del h1[val]
        else:
            print("different found",val)
    for key in h1.iterkeys():
        print ("different found",key)

寻找共同点和不同点：

2）方法2使用set

def findarrayset(a,b):
    common = set(a)&set(b)
    diff=set(a)^set(b)
    print list(common)
    print list(diff) 

解决方案 10：

这里有一些在 O(l1+l2) 中执行但不计算重复项的解决方案，还有一些考虑重复项的慢速解决方案（至少是 O(l1*l2)，但可能更昂贵）。

所以我认为我应该添加一个 O(l1log(l1)+l2(log(l2)) 解决方案。如果列表已经排序，这尤其有用。

def common_elems_with_repeats(first_list, second_list):
    first_list = sorted(first_list)
    second_list = sorted(second_list)
    marker_first = 0
    marker_second = 0
    common = []
    while marker_first < len(first_list) and marker_second < len(second_list):
        if(first_list[marker_first] == second_list[marker_second]):
            common.append(first_list[marker_first])
            marker_first +=1
            marker_second +=1
        elif first_list[marker_first] > second_list[marker_second]:
            marker_second += 1
        else:
            marker_first += 1
    return common

另一个更快的解决方案是，从 list1 创建一个 item->count 映射，然后迭代 list2，同时更新映射并计算重复项。不需要排序。需要额外的一点内存，但从技术上讲是 O(l1+l2)。

解决方案 11：

如果 list1 和 list2 未排序：

使用交集：

print((set(list1)).intersection(set(list2)))

合并列表并检查元素的出现次数是否多于 1：

combined_list = list1 + list2
set([num for num in combined_list if combined_list.count(num) > 1])

与上面类似，但不使用设置：

for num in combined_list:
    if combined_list.count(num) > 1:
        print(num)
        combined_list.remove(num)

对于排序列表，没有 python 特殊内置函数，O(n) 解决方案

p1 = 0
p2 = 0
result = []
while p1 < len(list1) and p2 < len(list2):
    if list1[p1] == list2[p2]:
        result.append(list1[p1])
        p1 += 1
        p2 += 2
    elif list1[p1] > list2[p2]:
        p2 += 1
    else:
        p1 += 1
print(result)

解决方案 12：

如果您不需要同时获得整个输出，则可以使用生成器，实际上它会更快：

common = (x for x in list1 if x in list2)

这里的优点是，即使使用巨大的列表或其他巨大的可迭代对象，它也会在恒定时间内（几乎即时）返回生成器。

例如，

list1 =  list(range(0,10000000))
list2=list(range(1000,20000000))
common = (x for x in list1 if x in list2)

使用 list1 和 list2 的这些值来回答这里的所有其他问题都需要很长时间。

然后你可以用以下方法迭代答案

for i in common: print(i)

解决方案 13：

我已经制定了深度交叉的完整解决方案

def common_items_dict(d1, d2, use_set_for_list_commons=True, use_set_for_dict_key_commons=True, append_empty=False):
    result = {}
    if use_set_for_dict_key_commons:
        shared_keys=list(set(d1.keys()).intersection(d2.keys())) # faster, order not preserved
    else:
        shared_keys=common_items_list(d1.keys(), d2.keys(), use_set_for_list_commons=False)

    for k in  shared_keys:
        v1 = d1[k]
        v2 = d2[k]
        if isinstance(v1, dict) and isinstance(v2, dict):
            result_dict=common_items_dict(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
            if len(result_dict)>0 or append_empty:
                result[k] = result_dict 
        elif isinstance(v1, list) and isinstance(v2, list):
            result_list=common_items_list(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
            if len(result_list)>0 or append_empty:
                result[k] = result_list 
        elif v1 == v2:
            result[k] = v1
    return result

def common_items_list(d1, d2, use_set_for_list_commons=True, use_set_for_dict_key_commons=True, append_empty=False):
    if use_set_for_list_commons: 
        result_list= list(set(d2).intersection(d1)) # faster, order not preserved, support only simple data types in list values
        return result_list

    result = []
    for v1 in d1: 
        for v2 in d2:
            if isinstance(v1, dict) and isinstance(v2, dict):
                result_dict=common_items_dict(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
                if len(result_dict)>0 or append_empty:
                    result.append(result_dict)
            elif isinstance(v1, list) and isinstance(v2, list):
                result_list=common_items_list(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
                if len(result_list)>0 or append_empty:
                    result.append(result_list)
            elif v1 == v2:
                result.append(v1)
    return result


def deep_commons(v1,v2, use_set_for_list_commons=True, use_set_for_dict_key_commons=True, append_empty=False):
    """
    deep_commons
     returns intersection of items of dict and list combinations recursively

    this function is a starter function, 
    i.e. if you know that the initial input is always dict then you can use common_items_dict directly
    or if it is a list you can use common_items_list directly

    v1 - dict/list/simple_value
    v2 - dict/list/simple_value
    use_set_for_dict_key_commons - bool - using set is faster, dict key order is not preserved 
    use_set_for_list_commons - bool - using set is faster, list values order not preserved, support only simple data types in list values
    append_empty - bool - if there is a common key, but no common items in value of key , if True it keeps the key with an empty list of dict

    """

    if isinstance(v1, dict) and isinstance(v2, dict):
        return common_items_dict(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
    elif isinstance(v1, list) and isinstance(v2, list):
        return common_items_list(v1, v2, use_set_for_list_commons, use_set_for_dict_key_commons, append_empty)
    elif v1 == v2:
        return v1
    else:
        return None


needed_services={'group1':['item1','item2'],'group3':['item1','item2']}
needed_services2={'group1':['item1','item2'],'group3':['item1','item2']}

result=deep_commons(needed_services,needed_services2)

print(result)

解决方案 14：

list1=[123,324523,5432,311,23]
list2=[2343254,34234,234,322123,123,234,23]
common=[]
def common_elements(list1,list2):
    for x in range(0,len(list1)):
        if list1[x] in list2:
            common.append(list1[x])
            
common_elements(list1,list2)
print(common)