是否可以提取包含重复值的交集列表？

Question

我想得到一个没有消除重复的列表的交集。我希望该方法是一种不使用循环的快速方法。下面是我的尝试，但是这个方法失败了，因为重复被删除了。

a = ['a','b','c','f']
b = ['a','b','b','o','k']

tmp = list(set(a) & set(b))
>>>tmp
>>>['b','a']

我希望结果是 ['a', 'b', 'b']。

该方法中，'a'为固定值，'b'为可变值。

以及从'b'中提取'a'值的概念。

有没有办法提取不去除重复值的交叉值列表？

Answer 1

>>a = ['a','b','c','f']
>>b = ['a','b','b','o','k']
>>items = set(a)
>>found = [i for i in b if i in items]
>>items
{'f', 'a', 'c', 'b'}
>>found
['a', 'b', 'b']

这应该可以完成您的工作。

Answer 2

在执行包含重复元素的列表的交集时，不清楚如何处理重复项，因为您只给出了一个测试用例及其预期结果，并且没有解释重复处理。

根据当前保持重复的工作方式，公共元素是 'a' 和 'b'，交集列表列出 'a' 的重数为 1 和 'b' 的重数2. 注意 'a' 在 a 和 b 上出现一次，但 'b' 在 [=42= 上出现两次]b。交集列表列出了具有多重性的公共元素等于该元素处于最大多重性的列表。

答案是是。但是，可以隐式调用循环 - 尽管您希望代码不显式使用任何循环语句。然而，该算法将始终是迭代的。

第 1 步： 创建不包含重复项的交集 Intersect（您已经完成了）。转换为列表以保持索引。

步骤 2： 创建第二个数组，IntersectD。使用 count 创建一个新变量 Freq 来计算该公共元素的最大出现次数。使用 Intersect 和 Freq 根据其对应的 Freq[k].

多次附加元素 Intersect[k]

包含 3 个列表的示例代码是

a = ['a','b','c','1','1','1','1','2','3','o']
b = ['a','b','b','o','1','o','1']
c = ['a','a','a','b','1','2']

intersect = list(set(a) & set(b) & set(c)) # 3-set case
intersectD = []

for k in range(len(intersect)):
  cmn = intersect[k]
  freq = max(a.count(cmn), b.count(cmn), c.count(cmn)) # 3-set case
  for i in range(freq): # Can be done with itertools
    intersectD.append(cmn)

>>> intersectD
>>> ['b', 'b', 'a', 'a', 'a', '1', '1', '1', '1']

对于涉及两个以上列表的情况，freq 可以使用更复杂的集合交集和最大表达式来计算此公共元素。如果使用列表的列表，可以使用内部循环计算 freq。您还可以用 How can I count the occurrences of a list item?.

中的 itertools 表达式替换内部 i-loop

Answer 3

一个解决方案可能是

good = set(a)
result = [x for x in b if x in good]

这里有两个循环；一个是 set 的集合构建循环（用 C 实现，比你在 Python 中做的任何事情都快一百倍）另一个是理解并在解释器中运行。第一个循环是为了避免在 a 中对 b 的每个元素进行线性搜索（如果 a 变大，这可能是一个严重的问题）。

请注意，使用 filter 可能不会获得太多（如果有的话），因为尽管 filter 循环在 C 中，但对于每个元素，它都必须返回给解释器调用过滤函数。

请注意，如果您关心速度，那么 Python 可能不是一个好的选择...例如，PyPy 在这里可能会更好，在这种情况下，只需显式编写最佳算法就可以了（避免重新搜索 a 重复项，当它们在 b 中连续时，就像在您的示例中发生的那样）

good = set(a)
res = []
i = 0
while i < len(b):
    x = b[i]
    if x in good:
        while i < len(b) and b[i] == x:  # is?
            res.append(x)
            i += 1
    else:
        i += 1

当然，在性能优化中，唯一真正的方法是尝试在真实系统上使用真实数据进行测量...随着技术的进步和变得越来越复杂，猜测的作用越来越小。

Answer 4

如果您坚持不使用 for 明确地 那么这将起作用：

>>> list(filter(a.__contains__, b))
['a', 'b', 'b']

但据我所知，直接调用像 __contains__ 这样的魔术方法并不是推荐的做法，因此请考虑以下做法：

>>> list(filter(lambda x: x in a, b))
['a', 'b', 'b']

如果您想将 a 中的查找从 O(n) 改进为 O(1) 那么首先创建一个 set：

>>> a_set = set(a)
>>> list(filter(lambda x: x in a_set, b))
['a', 'b', 'b']

Answer 5

我猜它并不比循环快，最后您可能仍然需要循环来提取结果。无论如何...

from collections import Counter

a = ['a','a','b','c','f']
b = ['a','b','b','o','k']

count_b = Counter(b)
count_ab = Counter(set(b)-set(a))
count_b - count_ab

#=> Counter({'a': 1, 'b': 2})

我的意思是，如果 res 保留结果，您需要：

[ val for sublist in [ [s] * n for s, n in res.items() ] for val in sublist ]
#=> ['a', 'b', 'b']

是否可以提取包含重复值的交集列表？

Is it possible to extract intersection list that contains duplicate values?

python

intersection

list

set