python - ¿Cómo encontrar intersección de lista?

arrays intersection

Question

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

producción real: [1,3,5,6] resultado esperado: [1,3,5]

¿Cómo podemos lograr una operación booleana AND (intersección de lista) en dos listas?

Answer 1

Aquí hay un código de Python 2 / Python 3 que genera información de tiempo para los métodos basados ​​en listas y en conjuntos para encontrar la intersección de dos listas.

Los algoritmos de comprensión de lista pura son O (n ^ 2), ya que in una lista hay una búsqueda lineal. Los algoritmos basados ​​en conjuntos son O (n), ya que la búsqueda establecida es O (1) y la creación del conjunto es O (n) (y la conversión de un conjunto a una lista también es O (n)). Por lo tanto, para un tamaño suficientemente grande, los algoritmos basados ​​en conjuntos son más rápidos, pero para pequeños, los gastos generales de creación de los conjuntos los vuelven más lentos que los algoritmos de compilación de listas puras.

#!/usr/bin/env python
'''''' Time list- vs set-based list intersection
See http://stackoverflow.com/q/3697432/4014959
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)

salida

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

Generado utilizando una máquina de un solo núcleo de 2 GHz con 2 GB de RAM ejecutando Python 2.6.6 en un estilo Debian de Linux (con Firefox ejecutándose en segundo plano).

Estas cifras son solo una guía aproximada, ya que las velocidades reales de los diversos algoritmos se ven afectadas de manera diferente por la proporción de elementos que están en ambas listas de fuentes.

Answer 2

Haga un conjunto del más grande:

_auxset = set(a)

Entonces,

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

Hará lo que quiera (preservar el orden de b , no es a ''s'' - no necesariamente puede preservar ambos ) y hacerlo rápido . (Usar if x in a como condición en la lista de comprensión también funcionaría, y evitaría la necesidad de compilar _auxset , pero desafortunadamente para las listas de longitud sustancial sería mucho más lento).

Si desea que se ordene el resultado, en lugar de conservar el orden de una lista, una forma aún más clara podría ser:

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

Answer 3

Se puede lograr una forma funcional usando lambda operador de filter y lambda .

list1 = [1,2,3,4,5,6]
list2 = [2,4,6,9,10]
>>> filter(lambda x:x in list1, list2)
[2, 4, 6]

Editar: Filtra x que existe tanto en list1 como en list, la diferencia establecida también se puede lograr usando:

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

Answer 4

Si convierte la lista más grande de las dos en un conjunto, puede obtener la intersección de ese conjunto con cualquier intersection() use iterable intersection() :

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

Answer 5

Si el orden no es importante y no necesita preocuparse por los duplicados, puede usar establecer intersección:

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

Answer 6

Si, por Y booleano, te refieres a elementos que aparecen en ambas listas, por ejemplo, intersección, entonces deberías ver los tipos set y set Python.

Answer 7

Usar listas de comprensión es bastante obvio para mí. No estoy seguro sobre el rendimiento, pero al menos las cosas se quedan listas.

[x for x in a if x in b]

O "todos los valores x que están en A, si el valor X está en B".

Answer 8

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

Debería funcionar como un sueño. Y, si puede, ¡use conjuntos en lugar de listas para evitar que todo este tipo cambie!