list - una - tuplas python




Prueba si las listas comparten cualquier elemento en python (6)

En Python 2.6 o posterior puedes hacer:

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

Quiero verificar si alguno 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
   ....: 

Esta pregunta es bastante antigua, pero me di cuenta de que mientras las personas estaban discutiendo conjuntos contra listas, nadie pensaba en usarlas juntas. 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

Por lo tanto, 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 cual tiene sentido, ya que verificar si un número está en un conjunto requiere tiempo constante mientras que verificar iterando a través de una lista toma tiempo proporcional a la duración de la lista.

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


Puede usar cualquier expresión incorporada de generador de función / 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)

Si no le importa cuál puede ser el elemento superpuesto, simplemente puede verificar la len de la lista combinada contra 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.


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

Hay cuatro formas comunes de probar si dos listas a y b comparten algún elemento. La primera opción es convertir ambos en 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, su búsqueda es O(1) (consulte here para obtener más información sobre la complejidad de los operadores en Python). Teóricamente, esto es O(n+m) en promedio para los objetos n 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 forma de hacerlo es usar una expresión generadora que realiza la iteración en las listas, como por ejemplo:

any(i in a for i in b)

Esto permite buscar in situ, por lo que no se asigna memoria nueva para las variables intermedias. También rescata en el primer hallazgo. Pero el operador in siempre es O(n) en las listas (ver here ).

Otra opción propuesta es una iteración híbrida a través de una de la lista, convertir la otra en un conjunto y probar la membresía en este conjunto, de esta manera:

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

Un cuarto enfoque es aprovechar el método isdisjoint() de los conjuntos (congelados) (ver here ), 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 los conjuntos tiene 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í 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 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 de la expresión híbrida y generadora, si el elemento compartido se encuentra sistemáticamente al final de la matriz (o ambas listas no comparten ningún valor), los enfoques de intersección disjuntos y conjuntos 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 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 que usan números aleatorios (en lugar de manipular la configuración para favorecer una u otra técnica):

Alta posibilidad de compartir: los elementos se toman aleatoriamente de [1, 2*len(a)] . Poca posibilidad de compartir: los elementos se toman al azar de [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, a es mucho más pequeño, isdisjoint() siempre es más rápido:

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

En resumen:

  • Si las listas son muy pequeñas (<10 elementos), not set(a).isdisjoint(b) siempre es 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 tamaños de listas 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, prueba en el conjunto" a = set(a); any(i in a for i in b) 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 método isdisjoint() 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_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 cortocircuito.

P.ej:

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

devolverá True tan pronto como llegue a 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 el iterador de imap , que se implementa en C, en lugar de en la 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á.





intersection