的Python：从<strong>两个</strong>的2所列出保持重复从两个列表

Question

我想有效地找到两个列表的交集，保持重复交汇，例如A = [1,1,2,3]，B = [1,1,2,4]应返回[1,1,1,1,2]

我知道一个类似的问题先前被问到（Python intersection of two lists keeping duplicates ） 但是这并不能帮助我，因为只保留一个列表中的重复项。

以下工作

def intersect(A,B): 
    C=[] 
    for a in A: 
     for b in B: 
      if a==b: 
       C.append(a) 
    return C 

但它不是我在做什么效率不够高！为了加快速度，我尝试了整理列表

def intersect(A,B): 
    A.sort() 
    B.sort() 
    C=[] 
    i=0 
    j=0 
    while i<len(A) and j<len(B): 
     if A[i]<=B[j]: 
      if A[i]==B[j]: 
       C.append(A[i]) 
      i+=1 
     else: 
      j=j+1 
    return C 

但是，这只能保留列表B中的重复项。任何建议？

Answer 1

这里是要求回答你的问题：

import collections 
for A,B,expected_output in (
    ([1,1,2,3], [1,1,2,4], [1,1,1,1,2]), 
    ([1,1,2,3], [1,2,4], [1,1,2])): 
    cntA = collections.Counter(A) 
    cntB = collections.Counter(B) 
    output = [ 
     x for x in sorted(set(A) & set(B)) for i in range(cntA[x]*cntB[x])] 
    assert output == expected_output 

这里的答案是最初由解释这个问题我和另外两个人：

import collections 
A=[1,1,2,3] 
B=[1,1,2,4] 
expected_output = [1,1,1,1,2,2] 
cntA = collections.Counter(A) 
cntB = collections.Counter(B) 
cnt_sum = collections.Counter(A) + collections.Counter(B) 
output = [x for x in sorted(set(A) & set(B)) for i in range(cnt_sum[x])] 
assert output == expected_output 

您可以找到collections.Counter()文档here。 collections是一个很好的模块，我强烈建议给整个模块上的文档进行阅读。

我意识到你实际上并不需要找到集合的交集，因为“缺少元素的计数为零”根据文档：

import collections 
for A,B,expected_output in (
    ([1,1,2,3], [1,1,2,4], [1,1,1,1,2]), 
    ([1,1,2,3], [1,2,4], [1,1,2])): 
    cntA = collections.Counter(A) 
    cntB = collections.Counter(B) 
    output = [ 
     x for x in sorted(set(A)) for i in range(cntA[x]*cntB[x])] 
    assert output == expected_output 

Answer 2

如何：

a_set = set(A) 
b_set = set(B) 
intersect = [i for i in A if i in b_set] + [j for j in B if j in a_set] 

两个列表内涵级联。有一点额外的时间和内存被用来创建A和B的集合，但是这会被集合vs列表中检查项目成员的效率所抵消。

您还可以美化它一点：

set_intersect = set(A) & set(B) 
list_intersect = [ele for ele in A+B if ele in set_intersect] 

强迫两个列表套，取它们的交集，然后用一个列表理解，如果他们出现在从两个列表A和B添加的所有元素设置交叉点。

Answer 3

我有一个困难时期加速你的代码，因为我不知道你在运行它。无论您是在小型还是大型列表上运行它，以及有多少不同的元素，它都会产生很大的差异。无论如何，这里有一些建议：

1.

def intersect(a, b): 
    count_a = Counter(a) 
    count_b = Counter(b) 
    count_mul = [] 
    for i in count_a: 
     count_mul.extend([i] * (count_a[i] * count_b[i])) 
    return count_mul 

2.

这将返回一个迭代器，你可以使用list(iterator)把它变成一个列表

def intersect(a, b): 
    count_a = Counter(a) 
    count_b = Counter(b) 
    count_mul = Counter() 
    for i in count_a: 
     count_mul[i] += count_a[i] * count_b[i] 
    return count_mul.elements() 

3。

与您的方式非常相似，但不会更改需要时间的列表大小。

def intersect(A, B): 
    return [a for a in A for b in B if a == b] 

我不知道这给任何改善你原来的方式，它真的取决于输入，但你的方式是O(n*m)和我是O(n+m)。

您可以使用该模块timeit检查的速度有多快它运行在您的输入：

from timeit import timeit 
timeit('test.intersect(A, B)', 'import test; A = [1,1,2,3]; B = [1,1,2,4]')