Prueba si las listas comparten algún elemento en Python

Quiero verificar si alguno de los elementos de una lista está presente en otra lista. Puedo hacerlo simplemente con el código a continuación, pero sospecho que podría haber una función de biblioteca para hacer esto. Si no, ¿existe un método más pitónico para lograr el mismo resultado?

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....: 

Respuesta corta : uso not set(a).isdisjoint(b), generalmente es el más rápido.

Hay cuatro formas comunes de probar si dos listas ay bcompartir algún elemento. La primera opción es convertir ambos a conjuntos y verificar su intersección, como tal:

bool(set(a) & set(b))

Debido a que los conjuntos se almacenan utilizando una tabla hash en Python, buscarlos esO(1) (consulte aquí para obtener más información sobre la complejidad de los operadores en Python). Teóricamente, esto es O(n+m)en promedio para ny mobjetos en listas ay b. Pero 1) primero debe crear conjuntos de las listas, lo que puede llevar una cantidad de tiempo no despreciable, y 2) supone que las colisiones de hash son escasas entre sus datos.

La segunda forma de hacerlo es usar una expresión generadora que realiza iteraciones en las listas, como:

any(i in a for i in b)

Esto permite buscar en el lugar, por lo que no se asigna memoria nueva para variables intermedias. También se rescata en el primer hallazgo. Pero el inoperador siempre está O(n)en las listas (ver aquí ).

Otra opción propuesta es un híbrido para iterar a través de una de la lista, convertir la otra en un conjunto y probar la membresía en este conjunto, así:

a = set(a); any(i in a for i in b)

Un cuarto enfoque es aprovechar el isdisjoint()método de los conjuntos (congelados) (ver aquí ), por ejemplo:

not set(a).isdisjoint(b)

Si los elementos que busca están cerca del comienzo de una matriz (por ejemplo, está ordenada), se favorece la expresión del generador, ya que el método de intersección de conjuntos debe asignar nueva memoria para las variables intermedias:

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

Aquí hay un gráfico del tiempo de ejecución para este ejemplo en función del tamaño de la lista:

Tenga en cuenta que ambos ejes son logarítmicos. Esto representa el mejor caso para la expresión del generador. Como se puede ver, el isdisjoint()método es mejor para tamaños de lista muy pequeños, mientras que la expresión del generador es mejor para tamaños de lista más grandes.

Por otro lado, como la búsqueda comienza con el comienzo de la expresión híbrida y generadora, si el elemento compartido está sistemáticamente al final de la matriz (o ambas listas no comparten ningún valor), los enfoques de intersección disjuntos y establecidos son entonces mucho más rápido que la expresión del generador y el enfoque híbrido.

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668

Es interesante observar que la expresión del generador es mucho más lenta para tamaños de lista más grandes. Esto es solo para 1000 repeticiones, en lugar de las 100000 para la figura anterior. Esta configuración también se aproxima bien cuando no se comparten elementos, y es el mejor caso para los enfoques de intersección disjuntos y establecidos.

Aquí hay dos análisis utilizando números aleatorios (en lugar de manipular la configuración para favorecer una técnica u otra):

Alta probabilidad de compartir: los elementos se toman aleatoriamente [1, 2*len(a)]. Baja posibilidad de compartir: los elementos se toman aleatoriamente [1, 1000*len(a)].

Hasta ahora, este análisis suponía que ambas listas son del mismo tamaño. En el caso de dos listas de diferentes tamaños, por ejemplo, aes mucho más pequeño, isdisjoint()siempre es más rápido:

Asegúrese de que la alista sea más pequeña, de lo contrario el rendimiento disminuye. En este experimento, el atamaño de la lista se estableció constante en 5.

En resumen:

• Si las listas son muy pequeñas (<10 elementos), not set(a).isdisjoint(b)siempre es la más rápida.
• Si los elementos en las listas están ordenados o tienen una estructura regular que puede aprovechar, la expresión del generador any(i in a for i in b)es la más rápida en tamaños de lista grandes;
• Pruebe la intersección establecida con not set(a).isdisjoint(b), que siempre es más rápida que bool(set(a) & set(b)).
• El híbrido "iterar a través de la lista, probar en conjunto" a = set(a); any(i in a for i in b)es generalmente más lento que otros métodos.
• La expresión del generador y el híbrido son mucho más lentos que los otros dos enfoques cuando se trata de listas sin compartir elementos.

En la mayoría de los casos, usar el isdisjoint()método es el mejor enfoque, ya que la expresión del generador tardará mucho más en ejecutarse, ya que es muy ineficiente cuando no se comparten elementos.

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

Nota: lo anterior supone que desea un booleano como respuesta. Si todo lo que necesita es una expresión para usar en una ifdeclaración, simplemente useif set(a) & set(b):

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

Esto es asintóticamente óptimo (peor caso O (n + m)), y podría ser mejor que el enfoque de intersección debido al anycortocircuito.

P.ej:

lists_overlap([3,4,5], [1,2,3])

devolverá True tan pronto como llegue 3 in sb

EDITAR: Otra variación (con agradecimiento a Dave Kirby):

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

Esto se basa en imapel iterador, que se implementa en C, en lugar de una comprensión del generador. También se usa sb.__contains__como la función de mapeo. No sé cuánta diferencia de rendimiento hace esto. Seguirá en cortocircuito.

También podría usar anycon la comprensión de la lista:

any([item in a for item in b])

En python 2.6 o posterior puedes hacer:

return not frozenset(a).isdisjoint(frozenset(b))

Puede usar cualquier expresión incorporada de función / generador de wa:

def list_overlap(a,b): 
     return any(i for i in a if i in b)

Como John y Lie han señalado, esto da resultados incorrectos cuando por cada i compartido por las dos listas bool (i) == False. Debería ser:

return any(i in b for i in a)

Esta pregunta es bastante antigua, pero me di cuenta de que mientras la gente discutía conjuntos versus listas, nadie pensaba en usarlos juntos. Siguiendo el ejemplo de Soravux,

El peor caso para las listas:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

Y el mejor caso para las listas:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707

Entonces, incluso más rápido que iterar a través de dos listas es iterar a través de una lista para ver si está en un conjunto, lo que tiene sentido ya que verificar si un número está en un conjunto toma tiempo constante, mientras que la verificación iterando a través de una lista toma tiempo proporcional a la longitud de la lista.

Por lo tanto, mi conclusión es que recorre una lista y verifica si está en un conjunto .

Si no le importa cuál sea el elemento superpuesto, simplemente puede verificar la lenlista combinada frente a las listas combinadas como un conjunto. Si hay elementos superpuestos, el conjunto será más corto:

len(set(a+b+c))==len(a+b+c) devuelve True, si no hay superposición.

Lanzaré otro con un estilo de programación funcional:

any(map(lambda x: x in a, b))

Explicación:

map(lambda x: x in a, b)

devuelve una lista de booleanos donde bse encuentran elementos de a. Esa lista se pasa a any, que simplemente devuelve Truesi hay algún elemento True.