python - ¿Cómo encontrar intersección de lista?
arrays intersection (8)
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.
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?
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))
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]
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)
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]
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".
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!