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