Prueba si las listas comparten elementos en python

Question

Quiero comprobar si cualquier de los elementos en una lista están presentes en otra lista. Puedo hacerlo simplemente con el siguiente código, pero sospecho que podría haber una función de biblioteca para hacer esto. Si no, hay 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 
    ....: 

Answer 1

Respuesta corta: not set(a).isdisjoint(b) utilizar, por lo general es el más rápido.

Existen cuatro formas comunes de probar si dos listas a y b comparten algún elemento. La primera opción es convertir tanto a los conjuntos y comprobar su intersección, como tal:

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

Debido conjuntos se almacenan utilizando una tabla hash en Python, buscando ellos es O(1) (ver here para obtener más información acerca de la complejidad de operadores en Python). Teóricamente, esto es O(n+m) en promedio para los objetos n y m en las listas a y b. Pero 1) primero debe crear conjuntos de las listas, lo que puede tomar una cantidad de tiempo no despreciable, y 2) supone que las colisiones hash son escasas entre sus datos.

La segunda manera de hacerlo es usando una expresión generadora realizar iteración en las listas, como por ejemplo:

any(i in a for i in b) 

Esto permite buscar en el lugar, así que no hay nueva se asigna memoria para las variables intermedias. También rescata en el primer hallazgo. Pero el operador es siempre inO(n) en las listas (ver here).

Otra opción propuesta es un iterate hybridto través de uno de la lista, convertir el otro en un conjunto y la prueba para formar parte de este conjunto, así:

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

Un cuarto enfoque es aprovechar el método isdisjoint() de los conjuntos (congelados) (véase here), por ejemplo:

not set(a).isdisjoint(b) 

Si los elementos que realizan búsquedas están cerca del comienzo de una matriz (por ejemplo, se ordena), la expresión del generador se ve favorecida, como se los conjuntos me intersecan DTO tienen que 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í es un gráfico del tiempo de ejecución para este ejemplo en función del tamaño de la lista:

Tenga en cuenta que los dos ejes son logarítmicas. Esto representa el mejor caso para la expresión del generador. Como se puede ver, el método isdisjoint() 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 para 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), la combinación y el conjunto los enfoques de intersección son mucho más rápidos 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 notar que la expresión generadora es mucho más lento para grandes tamaños de la lista. Esto es solo para 1000 repeticiones, en lugar de 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 conjuntos.

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

alta posibilidad de compartir: los elementos se toman al azar de [1, 2*len(a)]. Poca posibilidad de compartir: los elementos se toman aleatoriamente del [1, 1000*len(a)].

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

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

En resumen:

• Si las listas son muy pequeñas (< 10 elementos), not set(a).isdisjoint(b) es siempre el más rápido.
• 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 los tamaños de lista grandes;
• Pruebe la intersección del conjunto con not set(a).isdisjoint(b), que siempre es más rápido que bool(set(a) & set(b)).
• El híbrido "iterar a través de la lista, prueba en el 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 elementos compartidos.

En la mayoría de los casos, utilizando el método isdisjoint() es el mejor enfoque como la expresión generador se necesita mucho más tiempo para ejecutar, ya que es muy ineficiente cuando se comparten ningún elemento.

Answer 2

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

Nota: lo anterior supone que desea un booleano como la respuesta. Si todo lo que necesita es una expresión para utilizar en un comunicado por if, sólo tiene que utilizar if set(a) & set(b):

Answer 3

Usted podría también utilizar any con la lista de comprensión:

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

Answer 4

Se puede utilizar el cualquier incorporado en la expresión generador de funciones/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 para cada i compartida por los dos bool listas (i) == false. Que debe ser:

return any(i in b for i in a) 

Answer 5

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 a any 's cortocircuitos.

Ej:

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

devolverá true tan pronto como se pone a 3 in sb

EDIT: Otra variación (con gracias a David Kirby):

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

Esto se basa en imap El iterador, que se implementa en C, en lugar de una comprensión del generador. También usa sb.__contains__ como la función de mapeo. No sé cuánta diferencia de rendimiento hace esto. Todavía se cortocircuitará.

Answer 6

en Python 2.6 o posterior que puede hacer:

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

Answer 7

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

peor de los casos 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 de los casos 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 

lo tanto, incluso más rápido que la iteración 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 comprobar si un número está en un conjunto lleva tiempo constante, mientras que verificar iterando a través de una lista lleva tiempo proporcional a la longitud de la lista.

Por lo tanto, mi conclusión es que iterar a través de una lista, y comprobar si se encuentra en un conjunto.

Answer 8

si no le importa el elemento superpuesto, simplemente puede verificar el len de la lista 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 solapamiento.

Answer 9

Voy a tirar otra en 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 elementos de b se encuentran en a. Esa lista se pasa luego al any, que simplemente devuelve True si algún elemento es True.