如何查找列表交集？

Question

a = [1,2,3,4,5]
b = [1,3,5,6]
c = a and b
print c

实际输出：[1,3,5,6] 期望输出：[1,3,5]

如何在两个列表上执行布尔AND操作（列表交集）？

- csguy11

---

这里的问题在于a and b的工作方式如文档中提到的那样：“表达式x and y首先评估x；如果x为false，则返回其值；否则，评估y并返回其结果值。” - Tadeck

这个回答解决了你的问题吗？如何在Python中比较两个列表并返回匹配项 - Tomerikoo

Answer 1

如果顺序不重要且您不需要担心重复项，则可以使用集合交集：

>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> list(set(a) & set(b))
[1, 3, 5]

- Mark Byers

---

如果 a = [1,1,2,3,4,5] 且 b = [1,1,3,5,6]，则它们的交集是 [1,1,3,5]，但是使用上述方法只会得到一个 1，即 [1, 3, 5]。那么正确的做法是什么呢？ - Nitish Kumar Pal

intersection通常被理解为基于集合的操作。您需要找一个稍微不同的操作-您可能需要通过对每个列表进行排序并合并结果来手动完成操作-在合并中保留重复项。 - WestCoastProjects

@MarkByers 我认为这不会有重复。 - WestCoastProjects

我认为这个回答是不正确的。问题明确提到了列表，而不是集合。列表可以多次拥有相同的项，因此它们确实是一种不同的东西，在这个回答中没有得到解决。 - forcefsck

同时，列表是有序的，而集合则不是，因此您会失去这些信息（我认为结果是不可预测的）。 - Vincenzooo

Answer 2

对于我来说，使用列表推导式是相当明显的选择。不确定性能如何，但至少这些东西保持为列表。

[x for x in a if x in b]

或者说，“如果X的值在B中，则所有在A中的X值”。

- Lodewijk

---

这似乎是最符合Python风格且能保持顺序的方法。不确定为什么没有得到更高的投票！感谢您提供的绝佳解决方案！ - Bill D

这是一个O(n^2)的解决方案，而上面的解决方案是O(n)。 - nareddyt

将 b 设为一个集合，就能达到 O(n) 的时间复杂度。 - jcchuks

这种解决方案的优点是可以保留重复项。如果您能确保独特性，则O(n)集合解决方案会更好。但是，如果不可能存在重复项，那么为什么OP要谈论列表呢？列表交集的概念在数学上是荒谬的。 - demongolem

因为检查一个元素是否在列表b中的时间复杂度是O(n)，而不是O(1)。您需要对a中的每个元素执行这个操作n次。因此时间复杂度是O(n^2)。 - nareddyt

Answer 3

如果您将两个列表中较大的那个转换为集合，您可以使用intersection()函数获取该集合与任何可迭代对象的交集：

a = [1,2,3,4,5]
b = [1,3,5,6]
set(a).intersection(b)

- Brian R. Bondy

---

这跟 list(set(a) & set(b)) 有什么不同吗？ - user1767754

为什么转换哪个列表为集合很重要（假设n≠m）？只转换一个列表有什么优势？ - 3pitt

似乎这样会更快 - Nathan majicvr.com

与最被接受的答案相同的问题：重复项删除，顺序丢失。 - Vincenzooo

Answer 4

将较大的集合转换为集合：

_auxset = set(a)

那么，

c = [x for x in b if x in _auxset]

以下代码可以实现你的需求（保留b列表的顺序，但不能同时保留a的顺序），而且速度非常快。在列表推导式中使用条件if x in a也可以实现此目的，并避免构建_auxset，但对于长度较长的列表，这样的做法会明显变慢。

如果你希望结果按照顺序排序，而不是保留任何一个列表的顺序，一种更简洁的方法可能是：

c = sorted(set(a).intersection(b))

- Alex Martelli

---

这几乎肯定比被接受的答案慢，但它的优点是不会丢失重复项。 - tripleee

这是正确的答案，我相信在一般情况下（其中可能存在重复项并且希望保留顺序）它是尽可能快的。 - Vincenzooo

Answer 5

这是一些Python 2/Python 3代码，用于生成基于列表和集合的两个列表交集查找的时间信息。

纯列表推导算法的时间复杂度为O(n^2)，因为列表上的in操作是线性搜索。而基于集合的算法的时间复杂度为O(n)，因为集合搜索是O(1)，集合创建是O(n)（将集合转换为列表也是O(n)）。因此，对于足够大的n，基于集合的算法更快，但对于小的n，创建集合的开销使它们比纯列表算法更慢。

#!/usr/bin/env python

''' Time list- vs set-based list intersection
    See https://dev59.com/B3A65IYBdhLWcg3wqQg8
    Written by PM 2Ring 2015.10.16
'''

from __future__ import print_function, division
from timeit import Timer

setup = 'from __main__ import a, b'
cmd_lista = '[u for u in a if u in b]'
cmd_listb = '[u for u in b if u in a]'

cmd_lcsa = 'sa=set(a);[u for u in b if u in sa]'

cmd_seta = 'list(set(a).intersection(b))'
cmd_setb = 'list(set(b).intersection(a))'

reps = 3
loops = 50000

def do_timing(heading, cmd, setup):
    t = Timer(cmd, setup)
    r = t.repeat(reps, loops)
    r.sort()
    print(heading, r)
    return r[0]

m = 10
nums = list(range(6 * m))

for n in range(1, m + 1):
    a = nums[:6*n:2]
    b = nums[:6*n:3]
    print('\nn =', n, len(a), len(b))
    #print('\nn = %d\n%s %d\n%s %d' % (n, a, len(a), b, len(b)))
    la = do_timing('lista', cmd_lista, setup) 
    lb = do_timing('listb', cmd_listb, setup) 
    lc = do_timing('lcsa ', cmd_lcsa, setup)
    sa = do_timing('seta ', cmd_seta, setup)
    sb = do_timing('setb ', cmd_setb, setup)
    print(la/sa, lb/sa, lc/sa, la/sb, lb/sb, lc/sb)

输出

n = 1 3 2
lista [0.082171916961669922, 0.082588911056518555, 0.0898590087890625]
listb [0.069530963897705078, 0.070394992828369141, 0.075379848480224609]
lcsa  [0.11858987808227539, 0.1188349723815918, 0.12825107574462891]
seta  [0.26900982856750488, 0.26902294158935547, 0.27298116683959961]
setb  [0.27218389511108398, 0.27459001541137695, 0.34307217597961426]
0.305460649521 0.258469975867 0.440838458259 0.301898526833 0.255455833892 0.435697630214

n = 2 6 4
lista [0.15915989875793457, 0.16000485420227051, 0.16551494598388672]
listb [0.13000702857971191, 0.13060092926025391, 0.13543915748596191]
lcsa  [0.18650484085083008, 0.18742108345031738, 0.19513416290283203]
seta  [0.33592700958251953, 0.34001994132995605, 0.34146714210510254]
setb  [0.29436492919921875, 0.2953648567199707, 0.30039691925048828]
0.473793098554 0.387009751735 0.555194537893 0.540689066428 0.441652573672 0.633583767462

n = 3 9 6
lista [0.27657914161682129, 0.28098297119140625, 0.28311991691589355]
listb [0.21585917472839355, 0.21679902076721191, 0.22272896766662598]
lcsa  [0.22559309005737305, 0.2271728515625, 0.2323150634765625]
seta  [0.36382699012756348, 0.36453008651733398, 0.36750602722167969]
setb  [0.34979605674743652, 0.35533690452575684, 0.36164689064025879]
0.760194128313 0.59330170819 0.62005595016 0.790686848184 0.61710008036 0.644927481902

n = 4 12 8
lista [0.39616990089416504, 0.39746403694152832, 0.41129183769226074]
listb [0.33485794067382812, 0.33914685249328613, 0.37850618362426758]
lcsa  [0.27405810356140137, 0.2745978832244873, 0.28249192237854004]
seta  [0.39211201667785645, 0.39234519004821777, 0.39317893981933594]
setb  [0.36988520622253418, 0.37011313438415527, 0.37571001052856445]
1.01034878821 0.85398540833 0.698928091731 1.07106176249 0.905302334456 0.740927452493

n = 5 15 10
lista [0.56792402267456055, 0.57422614097595215, 0.57740211486816406]
listb [0.47309303283691406, 0.47619009017944336, 0.47628307342529297]
lcsa  [0.32805585861206055, 0.32813096046447754, 0.3349759578704834]
seta  [0.40036201477050781, 0.40322518348693848, 0.40548801422119141]
setb  [0.39103078842163086, 0.39722800254821777, 0.43811702728271484]
1.41852623806 1.18166313332 0.819398061028 1.45237674242 1.20986133789 0.838951479847

n = 6 18 12
lista [0.77897095680236816, 0.78187918663024902, 0.78467702865600586]
listb [0.629547119140625, 0.63210701942443848, 0.63321495056152344]
lcsa  [0.36563992500305176, 0.36638498306274414, 0.38175487518310547]
seta  [0.46695613861083984, 0.46992206573486328, 0.47583580017089844]
setb  [0.47616910934448242, 0.47661614418029785, 0.4850609302520752]
1.66818870637 1.34819326075 0.783028414812 1.63591241329 1.32210827369 0.767878297495

n = 7 21 14
lista [0.9703209400177002, 0.9734041690826416, 1.0182771682739258]
listb [0.82394003868103027, 0.82625699043273926, 0.82796716690063477]
lcsa  [0.40975093841552734, 0.41210508346557617, 0.42286920547485352]
seta  [0.5086359977722168, 0.50968098640441895, 0.51014018058776855]
setb  [0.48688101768493652, 0.4879908561706543, 0.49204087257385254]
1.90769222837 1.61990115188 0.805587768483 1.99293236904 1.69228211566 0.841583309951

n = 8 24 16
lista [1.204819917678833, 1.2206029891967773, 1.258256196975708]
listb [1.014998197555542, 1.0206191539764404, 1.0343101024627686]
lcsa  [0.50966787338256836, 0.51018595695495605, 0.51319599151611328]
seta  [0.50310111045837402, 0.50556015968322754, 0.51335406303405762]
setb  [0.51472997665405273, 0.51948785781860352, 0.52113485336303711]
2.39478683834 2.01748351664 1.01305257092 2.34068341135 1.97190418975 0.990165516871

n = 9 27 18
lista [1.511646032333374, 1.5133969783782959, 1.5639569759368896]
listb [1.2461750507354736, 1.254518985748291, 1.2613379955291748]
lcsa  [0.5565330982208252, 0.56119203567504883, 0.56451296806335449]
seta  [0.5966339111328125, 0.60275578498840332, 0.64791703224182129]
setb  [0.54694414138793945, 0.5508568286895752, 0.55375313758850098]
2.53362406013 2.08867620074 0.932788243907 2.76380331728 2.27843203069 1.01753187594

n = 10 30 20
lista [1.7777848243713379, 2.1453688144683838, 2.4085969924926758]
listb [1.5070111751556396, 1.5202279090881348, 1.5779800415039062]
lcsa  [0.5954139232635498, 0.59703707695007324, 0.60746097564697266]
seta  [0.61563014984130859, 0.62125110626220703, 0.62354087829589844]
setb  [0.56723213195800781, 0.57257509231567383, 0.57460403442382812]
2.88774814689 2.44791645689 0.967161734066 3.13413984189 2.6567803378 1.04968299523

这段文本是在一台2GHz单核机器上使用2GB内存运行Python 2.6.6，运行的Linux系统是Debian（同时Firefox在后台运行）生成的。

这些数字只是一个大概指南，因为各种算法的实际速度受源列表中两个列表重复元素比例的影响是不同的。

- PM 2Ring

Answer 6

可以使用filter和lambda运算符实现一种函数式的方法。

list1 = [1,2,3,4,5,6]

list2 = [2,4,6,9,10]

>>> list(filter(lambda x:x in list1, list2))

[2, 4, 6]

编辑：它过滤掉了在list1和list中都存在的x，使用set difference也可以实现：

>>> list(filter(lambda x:x not in list1, list2))
[9,10]

编辑2：python3的filter函数返回一个过滤器对象，使用list封装该对象可以得到输出列表。

- Saftography

---

请使用[编辑]链接来解释这段代码是如何工作的，而不仅仅提供代码，因为解释更有可能帮助未来的读者。另请参见[答案]。来源 - Jed Fox

使用Python3，这将返回一个过滤器对象。您需要说list(filter(lambda x:x in list1, list2))将其作为列表获取。 - Adrian W

当列表是不可哈希的时，这非常好！ - dirac3000

Answer 7

a = [1,2,3,4,5]
b = [1,3,5,6]
c = list(set(a).intersection(set(b)))

应该可以很好地工作。如果可能的话，使用集合而不是列表以避免所有这些类型转换！

- Alex Hart

---

如果 a 和 b 很大，那么这比其他答案更快。 - WestCoastProjects

Answer 8

您还可以使用numpy.intersect1d(ar1, ar2)函数。
该函数返回两个数组中都存在的唯一且已排序的值。

- hamidreza zarrabi

Answer 9

这种方法可以获取两个列表的交集，并获取它们共有的重复元素。

>>> from collections import Counter
>>> a = Counter([1,2,3,4,5])
>>> b = Counter([1,3,5,6])
>>> a &= b
>>> list(a.elements())
[1, 3, 5]

- Saisankar Gochhayat

---

这个应该获得更多的投票，因为它是对称的（得分最高的答案不是）。对称是指当intersect(list_a, list_b) == intersect(list_b, list_a)时。 - Brian Risk

Answer 10

如果你有一个列表的列表，map 很方便：

>>> lists = [[1, 2, 3], [2, 3, 4], [2, 3, 5]]
>>> set(lists.pop()).intersection(*map(set, lists))
{2, 3}

可以适用于类似的可迭代对象：

>>> lists = ['ash', 'nazg']
>>> set(lists.pop()).intersection(*map(set, lists))
{'a'}

pop会在列表为空时引发错误，因此您可能需要将其封装在函数中：

def intersect_lists(lists):
    try:
        return set(lists.pop()).intersection(*map(set, lists))
    except IndexError: # pop from empty list
        return set()

- Mr_and_Mrs_D