sprawnie wiedząc, czy przecięcie dwóch list jest puste czy nie, w pythonie

Question

Załóżmy, że mam dwie listy, L i M. Teraz chcę wiedzieć, czy mają wspólny element. Jaki byłby najszybszy sposób zadawania pytania (w python), jeśli współużytkują element? Nie obchodzi mnie, które elementy udostępniają, a ile, po prostu, czy je udostępniają, czy nie.

Na przykład, w tym przypadku

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

powinienem dostać False, a tu:

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

powinienem dostać True.

Mam nadzieję, że pytanie jest jasne. Dzięki!

Manuel

Answer 1

lub więcej zwięźle

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

Jeśli naprawdę potrzebujesz True lub False

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

Po uruchomieniu niektórych ustawień czasowych wydaje się, że jest to dobra opcja, aby spróbować również

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

Jeśli elementy w M lub L nie są hashable trzeba użyć mniej efektywne podejście jak to

any(x in M for x in L) 

Oto niektóre czasy na 100 listach poz. Używanie zestawów jest znacznie szybsze, gdy nie ma skrzyżowania, a nieco wolniejsze, gdy występuje znaczne przecięcie.

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

Przede wszystkim, jeśli nie trzeba ich zamawiać, a następnie przełączyć się do typu set.

Jeśli trzeba jeszcze typ listy, a następnie zrobić to w następujący sposób: 0 == false

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

Answer 3

Aby uniknąć dzieło budowy skrzyżowania i wytwarzają odpowiedź tak szybko, jak wiemy, że przecinają:

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

Aktualizacja: gnibbler próbowałem się i okazało się, że działa szybciej z set() zamiast zamrożonego zestawu(). Whaddayaknow.

Answer 4

To najbardziej ogólny i skuteczny w wyważony sposób mogłem wymyślić (komentarze powinny uczynić kod łatwy do zrozumienia):

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.