savoir efficacement si l'intersection de deux listes est vide ou non, en python [dupliquer]
cette question a déjà une réponse ici:
Supposons que j'ai deux listes, L et M. Maintenant, je veux savoir s'ils partagent un élément. Quelle serait la manière la plus rapide de demander (en python) s'ils partagent un élément? Je n'ai pas soins de quels éléments ils partagent, ou combien, juste s'ils partagent ou non.
par exemple, dans ce cas
L = [1,2,3,4,5,6]
M = [8,9,10]
je devrais obtenir de Faux, et ici:
L = [1,2,3,4,5,6]
M = [5,6,7]
je devrais être sincère.
j'espère que la question est claire. Merci!
Manuel
4 réponses
ou plus concisément
if set(L) & set(M):
# there is an intersection
else:
# no intersection
si vous avez vraiment besoin de True ou False
bool(set(L) & set(M))
après quelques chronométrages, cela semble être une bonne option pour essayer aussi
m_set=set(M)
any(x in m_set for x in L)
si les éléments en M ou L ne sont pas hachables, vous devez utiliser une approche moins efficace comme celle-ci
any(x in M for x in L)
voici quelques horaires pour 100 listes d'articles. Utiliser des ensembles est considérablement plus rapide quand il est pas d'intersection, et un peu plus lent quand il y a une grande intersection.
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
Pour éviter le travail de construction de l'intersection, et de produire une réponse dès que nous savons qu'ils se croisent:
m_set = frozenset(M)
return any(x in m_set for x in L)
mise à jour: gnibbler a essayé et l'a trouvé pour courir plus vite avec set() à la place de frozenset(). Whaddayaknow.
tout d'abord, si vous n'avez pas besoin de les commander, passez au type set .
si vous avez encore besoin du type de liste, faites-le de cette façon: 0 == False
len(set.intersection(set(L), set(M)))
C'est le plus générique et le plus efficace d'une manière équilibrée que j'ai pu trouver (les commentaires devraient rendre le code facile à comprendre):
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.