Prueba si las listas comparten algún elemento en Python

131

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
   ....: 
fmark
fuente
Las únicas optimizaciones que se me ocurren son las caídas, len(...) > 0ya que bool(set([]))producen False. Y, por supuesto, si mantuviste tus listas como conjuntos para empezar, guardarías la sobrecarga de creación de conjuntos.
msw
Relevante: stackoverflow.com/a/44786707/1959808
Ioannis Filippidis
1
Tenga en cuenta que no puede distinguir Truede 1y Falsede 0. not set([1]).isdisjoint([True])consigue True, lo mismo con otras soluciones.
Dimali

Respuestas:

313

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:

Tiempo de ejecución de prueba para compartir elementos cuando se comparte al principio

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

Tiempo de ejecución de prueba para compartir elementos cuando se comparte al final

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):

Tiempo de ejecución de prueba para compartir elementos para datos generados aleatoriamente con alta probabilidad de compartir Tiempo de ejecución de prueba para compartir elementos para datos generados aleatoriamente con alta probabilidad de compartir

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:

Tiempo de ejecución de prueba para compartir elementos en dos listas de diferentes tamaños cuando se comparte al principio Tiempo de ejecución de prueba para compartir elementos en dos listas de diferentes tamaños cuando se comparte al final

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.

Soravux
fuente
8
Esa es una información útil allí, muestra que el análisis big-O no es el todo y termina todo el razonamiento sobre el tiempo de ejecución.
Steve Allison
¿Qué pasa con el peor de los casos? anysale en el primer valor no falso. Usando una lista donde el único valor coincidente está al final, obtenemos esto: 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 ... y es solo con 1000 iteraciones.
RobM
2
Gracias @RobM por la información. He actualizado mi respuesta para reflejar esto y tener en cuenta las otras técnicas propuestas en este hilo.
Soravux
Debe ser not set(a).isdisjoint(b)para probar si dos listas comparten un miembro. set(a).isdisjoint(b)devuelve Truesi las dos listas no comparten un miembro. La respuesta debe ser editada?
Guillochon
1
Gracias por el aviso, @Guillochon, está arreglado.
Soravux
25
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):

John Machin
fuente
55
Este es el peor de los casos O (n + m). Sin embargo, el inconveniente es que crea un nuevo conjunto y no se rescata cuando un elemento común se encuentra temprano.
Matthew Flaschen
1
Tengo curiosidad de por qué es esto O(n + m). Supongo que los conjuntos se implementan utilizando tablas hash y, por lo tanto, el inoperador puede trabajar a O(1)tiempo (excepto en casos degenerados). ¿Es esto correcto? Si es así, dado que las tablas hash tienen un rendimiento de búsqueda en el peor de los casos O(n), ¿significa esto que en el peor de los casos tendrá O(n * m)rendimiento?
fmark
1
@fmark: Teóricamente, tienes razón. Prácticamente a nadie le importa; lea los comentarios en Objects / dictobject.c en la fuente de CPython (los conjuntos son solo dicts con solo claves, sin valores) y vea si puede generar una lista de claves que causará el rendimiento de búsqueda de O (n).
John Machin
Bien, gracias por aclarar, me preguntaba si estaba ocurriendo algo de magia :). Si bien estoy de acuerdo en que prácticamente no necesito preocuparme, es trivial generar una lista de claves que causará el O(n)rendimiento de búsqueda;), consulte pastebin.com/Kn3kAW7u Solo para ver lafs.
fmark
2
Si lo se. Además, acabo de leer la fuente a la que me apuntaste, que documenta aún más magia en el caso de funciones hash no aleatorias (como la incorporada). Supuse que requería aleatoriedad, como la de Java, lo que resulta en monstruosidades como esta stackoverflow.com/questions/2634690/… . Necesito seguir recordándome a mí mismo que Python no es Java (¡gracias a Dios!).
fmark
10
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.

Matthew Flaschen
fuente
1
Los bucles en el enfoque de intersección están todos en código C; Hay un bucle en su enfoque que incluye el código Python. La gran incógnita es si una intersección vacía es probable o improbable.
John Machin
2
También puede usar el any(itertools.imap(sb.__contains__, a))que debería ser más rápido, ya que evita usar una función lambda.
Dave Kirby el
Gracias, @Dave. :) Estoy de acuerdo en eliminar el lambda es una victoria.
Matthew Flaschen
4

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

any([item in a for item in b])
Ioachim
fuente
66
Podría, pero el tiempo es O (n * m) mientras que el tiempo para el enfoque de intersección establecido es O (n + m). También podría hacerlo SIN la comprensión de la lista (perder []) y se ejecutaría más rápido y usaría menos memoria, pero el tiempo aún sería O (n * m).
John Machin
1
Si bien su gran análisis de O es cierto, sospecho que para valores pequeños de n y m el tiempo necesario para construir las tablas hash subyacentes entrará en juego. Big O ignora el tiempo que lleva calcular los hashes.
Anthony Conyers
2
La construcción de una "tabla hash" se amortiza O (n).
John Machin
1
Lo entiendo, pero la constante que estás tirando es bastante grande. No importa para valores grandes de n, pero sí para valores pequeños.
Anthony Conyers
3

En python 2.6 o posterior puedes hacer:

return not frozenset(a).isdisjoint(frozenset(b))
Resistente
fuente
1
Parece que uno no tiene que proporcionar un conjunto o conjunto congelado como primer argumento. Intenté con una cadena y funcionó (es decir, cualquier iterable funcionará).
Aktau
2

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)
Anthony Conyers
fuente
1
Amplificando el comentario de Lie Ryan: dará un resultado incorrecto para cualquier elemento x que esté en la intersección donde bool(x)es False. En el ejemplo de Lie Ryan, x es 0. La única solución es la any(True for i in a if i in b)que está mejor escrita como la que ya se vio any(i in b for i in a).
John Machin
1
Corrección: dará un resultado erróneo cuando todos los elementos xen la intersección son tales que bool(x)es False.
John Machin
1

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 .

binoche9
fuente
1
Usar el isdisjoint()método en un conjunto (congelado) como lo indica @Toughy es aún mejor: 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.00913715362548828
Aktau
1

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.

domoarigato
fuente
Si el primer valor se superpone, seguirá convirtiendo la lista completa en un conjunto, sin importar cuán grande sea.
Peter Wood
1

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.

cs01
fuente