¿Cómo encontrar la intersección de la lista?

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

salida real: [1,3,5,6] salida esperada:[1,3,5]

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

csguy11
fuente
66
El problema aquí es que a and bfunciona como la siguiente declaración de la documentación lo menciona: " La expresión x and yprimero evalúa x; si xes falsa, se devuelve su valor; de lo contrario, yse evalúa y se devuelve el valor resultante " .
Tadeck

Respuestas:

348

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

>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> list(set(a) & set(b))
[1, 3, 5]
Mark Byers
fuente
9
¿Qué pasa si a = [1,1,2,3,4,5]y b = [1,1,3,5,6]luego la intersección es [1,1,3,5]pero por el método anterior dará como resultado una sola, 1es decir, [1, 3, 5]cuál será la forma de escribir para hacerlo entonces?
Nitish Kumar Pal
66
@NItishKumarPal intersectionse entiende comúnmente como basado en conjunto . Está buscando un animal ligeramente diferente, y es posible que deba hacerlo manualmente clasificando cada lista y fusionando los resultados, y manteniendo duplicados en la fusión.
javadba
1
@MarkByers Esto no tendrá duplicados de un hecho.
javadba
85

Usar las comprensiones de listas es bastante obvio para mí. No estoy seguro sobre el rendimiento, pero al menos las cosas permanecen en las listas.

[x for x in a if x in b]

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

Lodewijk
fuente
1
Esto parece el más pitónico que mantiene el orden. ¡No estoy seguro de por qué esto no es votado más alto! Gracias por la gran solución!
Bill D
15
Esta es una solución O (n ^ 2), mientras que las soluciones anteriores son O (n)
nareddyt
3
@nareddyt - haz bun set y tendrás O (n)
jcchuks
2
@jcchuks La ventaja de esta solución es si necesita conservar duplicados. Si puede estar seguro de la unicidad, una solución de conjunto O (n) sería mejor. Sin embargo, si los duplicados no son posibles, ¿por qué el OP incluso está hablando de listas para empezar? La noción de intersección de listas es un absurdo matemático
demongolem
63

Si convierte la mayor de las dos listas en un conjunto, puede obtener la intersección de ese conjunto con cualquier iterable usando intersection():

a = [1,2,3,4,5]
b = [1,3,5,6]
set(a).intersection(b)
Brian R. Bondy
fuente
9
¿Es esto diferente alist(set(a) & set(b))
user1767754
3
¿Por qué importa qué lista se convierte en conjunto (suponiendo n! = m)? ¿Cuál es la ventaja de convertir solo uno para configurar?
3pitt
1
Parece que esto sería más rápido
Nathan
29

Haz un set con el más grande:

_auxset = set(a)

Luego,

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

hará lo que quiera (preservar blos pedidos, no alos que no necesariamente pueden preservar ambos ) y lo hará rápidamente . (El uso if x in acomo la condición en la comprensión de la lista también funcionaría y evitaría la necesidad de construir _auxset, pero desafortunadamente para las listas de longitud considerable sería mucho más lento).

Si desea que se ordene el resultado, en lugar de preservar el orden de cualquiera de las listas, una forma aún más ordenada podría ser:

c = sorted(set(a).intersection(b))
Alex Martelli
fuente
Es casi seguro que es más lento que la respuesta aceptada, pero tiene la ventaja de que no se pierden los duplicados.
tripleee
18

Aquí hay un código de Python 2 / Python 3 que genera información de sincronización tanto para los métodos basados ​​en listas como para establecer la intersección de dos listas.

Los algoritmos de comprensión de la lista pura son O (n ^ 2), ya que inen una lista hay una búsqueda lineal. Los algoritmos basados ​​en conjuntos son O (n), ya que la búsqueda de conjuntos es O (1), y la creación de conjuntos es O (n) (y convertir un conjunto en una lista también es O (n)). Entonces, para n suficientemente grandes, los algoritmos basados ​​en conjuntos son más rápidos, pero para pequeños n los gastos generales de creación de los conjuntos los hacen 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 que ejecuta Python 2.6.6 en una versión 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 se encuentran en ambas listas de origen.

PM 2Ring
fuente
11
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 cambie todo este tipo!

Alex Hart
fuente
Si un y b son grandes, entonces esto es más rápido que otras respuestas
javadba
5

Se puede lograr una forma funcional usando filtery lambdaoperador.

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

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

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

[2, 4, 6]

Editar: filtra x que existe tanto en la lista1 como en la lista, la diferencia establecida también se puede lograr usando:

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

Edit2: python3 filterdevuelve un objeto de filtro, encapsulado con listdevuelve la lista de salida.

Saftophobia
fuente
Utilice el enlace de edición para explicar cómo funciona este código y no solo dé el código, ya que es más probable que una explicación ayude a los futuros lectores. Ver también Cómo responder . fuente
Jed Fox
1
Con Python3, esto devuelve un objeto de filtro. Tienes que decir list(filter(lambda x:x in list1, list2))para obtenerlo como una lista.
Adrian W
1

Este es un ejemplo cuando necesita Cada elemento en el resultado debe aparecer tantas veces como se muestra en ambas matrices.

def intersection(nums1, nums2):
    #example:
    #nums1 = [1,2,2,1]
    #nums2 = [2,2]
    #output = [2,2]
    #find first 2 and remove from target, continue iterating

    target, iterate = [nums1, nums2] if len(nums2) >= len(nums1) else [nums2, nums1] #iterate will look into target

    if len(target) == 0:
            return []

    i = 0
    store = []
    while i < len(iterate):

         element = iterate[i]

         if element in target:
               store.append(element)
               target.remove(element)

         i += 1


    return store
Arturo Morales Rangel
fuente
1

Puede que sea tarde, pero solo pensé que debería compartir el caso en el que se requiere que lo haga manualmente (mostrar trabajo - jaja) O cuando necesite que todos los elementos aparezcan tantas veces como sea posible o cuando también necesite que sea único .

Tenga en cuenta que también se han escrito pruebas para ello.



    from nose.tools import assert_equal

    '''
    Given two lists, print out the list of overlapping elements
    '''

    def overlap(l_a, l_b):
        '''
        compare the two lists l_a and l_b and return the overlapping
        elements (intersecting) between the two
        '''

        #edge case is when they are the same lists
        if l_a == l_b:
            return [] #no overlapping elements

        output = []

        if len(l_a) == len(l_b):
            for i in range(l_a): #same length so either one applies
                if l_a[i] in l_b:
                    output.append(l_a[i])

            #found all by now
            #return output #if repetition does not matter
            return list(set(output))

        else:
            #find the smallest and largest lists and go with that
            sm = l_a if len(l_a)  len(l_b) else l_b

            for i in range(len(sm)):
                if sm[i] in lg:
                    output.append(sm[i])

            #return output #if repetition does not matter
            return list(set(output))

    ## Test the Above Implementation

    a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
    b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
    exp = [1, 2, 3, 5, 8, 13]

    c = [4, 4, 5, 6]
    d = [5, 7, 4, 8 ,6 ] #assuming it is not ordered
    exp2 = [4, 5, 6]

    class TestOverlap(object):

        def test(self, sol):
            t = sol(a, b)
            assert_equal(t, exp)
            print('Comparing the two lists produces')
            print(t)

            t = sol(c, d)
            assert_equal(t, exp2)
            print('Comparing the two lists produces')
            print(t)

            print('All Tests Passed!!')

    t = TestOverlap()
    t.test(overlap)
anabeto93
fuente
0

Si, por AND booleano, quiere decir elementos que aparecen en ambas listas, por ejemplo, intersección, entonces debería mirar Python sety los frozensettipos.

Tim McNamara
fuente
0

¡También puedes usar un contador! No conserva el orden, pero considerará los duplicados:

>>> from collections import Counter
>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> d1, d2 = Counter(a), Counter(b)
>>> c = [n for n in d1.keys() & d2.keys() for _ in range(min(d1[n], d2[n]))]
>>> print(c)
[1,3,5]
Atonal
fuente