sabiendo eficientemente si la intersección de dos listas está vacía o no, en python

Question

Supongamos que tengo dos listas, L y M. Ahora quiero saber si comparten un elemento. ¿Cuál sería la forma más rápida de preguntar (en python) si comparten un elemento? No me importa qué elementos comparten, o cuántos, solo si comparten o no.

Por ejemplo, en este caso

L = [1,2,3,4,5,6] 
M = [8,9,10] 

que debería obtener Falso, y aquí:

L = [1,2,3,4,5,6] 
M = [5,6,7] 

que debería obtener verdadera.

Espero que la pregunta sea clara. Gracias!

Manuel

Answer 1

O de manera más concisa

if set(L) & set(M): 
    # there is an intersection 
else: 
    # no intersection 

Si realmente necesita True o False

bool(set(L) & set(M)) 

Después de ejecutar algunos tiempos, esta parece ser una buena opción para probar también

m_set=set(M) 
any(x in m_set for x in L) 

Si los elementos de M o L no se hashable usted tiene que utilizar un método menos eficiente como esto

any(x in M for x in L) 

Aquí están algunos instantes de 100 listas de artículos. Usar juegos es considerablemente más rápido cuando no hay intersección, y un poco más lento cuando hay una intersección considerable.

M=range(100) 
L=range(100,200) 

timeit set(L) & set(M) 
10000 loops, best of 3: 32.3 µs per loop 

timeit any(x in M for x in L) 
1000 loops, best of 3: 374 µs per loop 

timeit m_set=frozenset(M);any(x in m_set for x in L) 
10000 loops, best of 3: 31 µs per loop 

L=range(50,150) 

timeit set(L) & set(M) 
10000 loops, best of 3: 18 µs per loop 

timeit any(x in M for x in L) 
100000 loops, best of 3: 4.88 µs per loop 

timeit m_set=frozenset(M);any(x in m_set for x in L) 
100000 loops, best of 3: 9.39 µs per loop 


# Now for some random lists 
import random 
L=[random.randrange(200000) for x in xrange(1000)] 
M=[random.randrange(200000) for x in xrange(1000)] 

timeit set(L) & set(M) 
1000 loops, best of 3: 420 µs per loop 

timeit any(x in M for x in L) 
10 loops, best of 3: 21.2 ms per loop 

timeit m_set=set(M);any(x in m_set for x in L) 
1000 loops, best of 3: 168 µs per loop 

timeit m_set=frozenset(M);any(x in m_set for x in L) 
1000 loops, best of 3: 371 µs per loop 

Answer 2

En primer lugar, si usted no necesita les ordenó, a continuación, cambiar el tipo set.

Si aún necesita el tipo de lista, a continuación, hacerlo de esta manera: 0 == false

len(set.intersection(set(L), set(M))) 

Answer 3

Para evitar el trabajo de construcción de la intersección, y producen una respuesta tan pronto como sabemos que se cruzan:

m_set = frozenset(M) 
return any(x in m_set for x in L) 

Actualización: gnibbler intentado hacer esto y lo encontró a correr más rápido con set() en lugar de frozenset(). Whaddayaknow.

Answer 4

eso es lo más genérico y eficiente de una manera equilibrada que podía llegar a (Los comentarios deben hacer el código fácil de entender):

import itertools, operator 

def _compare_product(list1, list2): 
    "Return if any item in list1 equals any item in list2 exhaustively" 
    return any(
     itertools.starmap(
      operator.eq, 
      itertools.product(list1, list2))) 

def do_they_intersect(list1, list2): 
    "Return if any item is common between list1 and list2" 

    # do not try to optimize for small list sizes 
    if len(list1) * len(list2) <= 100: # pick a small number 
     return _compare_product(list1, list2) 

    # first try to make a set from one of the lists 
    try: a_set= set(list1) 
    except TypeError: 
     try: a_set= set(list2) 
     except TypeError: 
      a_set= None 
     else: 
      a_list= list1 
    else: 
     a_list= list2 

    # here either a_set is None, or we have a_set and a_list 

    if a_set: 
     return any(itertools.imap(a_set.__contains__, a_list)) 

    # try to sort the lists 
    try: 
     a_list1= sorted(list1) 
     a_list2= sorted(list2) 
    except TypeError: # sorry, not sortable 
     return _compare_product(list1, list2) 

    # they could be sorted, so let's take the N+M road, 
    # not the N*M 

    iter1= iter(a_list1) 
    iter2= iter(a_list2) 
    try: 
     item1= next(iter1) 
     item2= next(iter2) 
    except StopIteration: # one of the lists is empty 
     return False # ie no common items 

    while 1: 
     if item1 == item2: 
      return True 
     while item1 < item2: 
      try: item1= next(iter1) 
      except StopIteration: return False 
     while item2 < item1: 
      try: item2= next(iter2) 
      except StopIteration: return False 

HTH.