Предположим, у меня есть два списка: L и M. Теперь я хочу знать, имеют ли они общий элемент. Какой был бы самый быстрый способ спросить (в python), если они разделяют элемент? Мне все равно, какие элементы они разделяют, или сколько, просто, если они разделяют или нет.
Например, в этом случае
L = [1,2,3,4,5,6]
M = [8,9,10]
Я должен получить False, и здесь:
L = [1,2,3,4,5,6]
M = [5,6,7]
Я должен получить правду.
Я надеюсь, что вопрос будет ясен. Спасибо!
Мануэль
Или более лаконично
if set(L) & set(M):
# there is an intersection
else:
# no intersection
Если вам действительно нужны True или False
bool(set(L) & set(M))
После запуска некоторых таймингов это кажется хорошим вариантом попробовать
m_set=set(M)
any(x in m_set for x in L)
Если элементы в M или L не являются хешируемыми, вы должны использовать менее эффективный подход, подобный этому
any(x in M for x in L)
Вот несколько таймингов для 100 списков элементов. Использование множеств значительно быстрее, когда нет пересечения, и немного медленнее, когда имеется значительное пересечение.
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
Чтобы избежать работы по построению пересечения и дать ответ, как только мы узнаем, что они пересекаются:
m_set = frozenset(M)
return any(x in m_set for x in L)
Обновление: gnibbler попробовал это и нашел, что он работает быстрее с помощью set() вместо frozenset(). Whaddayaknow.
Прежде всего, если они вам не понадобятся, перейдите к типу set.
Если вам все еще нужен тип списка, сделайте так: 0 == False
len(set.intersection(set(L), set(M)))
Это самый общий и эффективный сбалансированный способ, которым я мог бы придумать (комментарии должны сделать код понятным):
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 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
НТН.