efficiently knowing if intersection of two list is empty or not, in python [duplicate]

Or more concisely

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

If you really need True or False

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

After running some timings, this seems to be a good option to try too

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

If the items in M or L are not hashable you have to use a less efficient approach like this

any(x in M for x in L)

Here are some timings for 100 item lists. Using sets is considerably faster when there is no intersection, and a bit slower when there is a considerable intersection.

M=range(100)L=range(100,200)timeit set(L) & set(M)10000 loops, best of 3: 32.3 µs per looptimeit any(x in M for x in L)1000 loops, best of 3: 374 µs per looptimeit m_set=frozenset(M);any(x in m_set  for x in L)10000 loops, best of 3: 31 µs per loopL=range(50,150)timeit set(L) & set(M)10000 loops, best of 3: 18 µs per looptimeit any(x in M for x in L)100000 loops, best of 3: 4.88 µs per looptimeit 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 listsimport randomL=[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 looptimeit any(x in M for x in L)10 loops, best of 3: 21.2 ms per looptimeit m_set=set(M);any(x in m_set  for x in L)1000 loops, best of 3: 168 µs per looptimeit m_set=frozenset(M);any(x in m_set  for x in L)1000 loops, best of 3: 371 µs per loop

To avoid the work of constructing the intersection, and produce an answer as soon as we know that they intersect:

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

Update: gnibbler tried this out and found it to run faster with set() in place of frozenset(). Whaddayaknow.

First of all, if you do not need them ordered, then switch to the set type.

If you still need the list type, then do it this way: 0 == False

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