How do you compare 2 lists to check if one of the list has one or more elements in the other list?

[lagingking]

What i meant was
lets's say we have
A=[0,1,2]
B=[2,3,4]
how do i check if all the elements in A and B are repeated or not?
i know i way is to check is to use for loops
like
for i in A:
if i in B:
print 'it has repeated'

but if A was a list with 10000 elements it can take a long time.

So my question is, is there any other way to compare?

Hopefully you guys get what i mean...

[Insectoid]

If A is sorted you can iterate over every B and use a binary search to find where that b is supposed to be, and if it isn't equal to b, it's not in the list.

if B is sorted as well you can optimize it even more, I think.

If neither is sorted I dunno what you can do.

[Tony]

if both lists are sorted, you can do a single linear pass, bringing your runtime complexity down to

O(AlogA + BlogB + A + B)

[DemonWasp]

If you insert all the elements in one list (generally, choose the longer: I will assume B) into a Hash-based Set in O ( B ) time, you can iterate over the elements of A in O ( A ) time, checking for membership in the hash set in O ( 1 ) time per element. Your total time complexity would therefore be only O ( A + B ), which is somewhat better than sorting. However, this approach does require additional memory, and that you have a decent hash function on the elements of A and B.

I don't know how that applies to Python as I have no experience. Sorry.

[102jon]

Demonwasp, why are you helping on a python thread if you have no experience?

[Tony]

Because this is not a Python specific question.

[DemonWasp]

What Tony said. Reading the Python documentation on sets ( http://docs.python.org/library/stdtypes.html#set-types-set-frozenset ), though I'm led to believe that the following would work:

Python:

def intersects ( a, b ):     s = set ( b )     for x in a:         if x in s:             return True     return False

It's not that I don't know Python at all, it's just that I didn't know whether Python's set implementation was hashed or tree-based. If it were tree-based, then the runtime would be O ( A + A * log ( B ) ), which isn't quite as good, though it's very close and still better than anything else in this thread. Of course, the people who implemented Python were pretty crafty people, so their implementation is, in fact, hashed (as it alludes to in the documentation for set, and the reason for the existence of frozenset).

Edit: Small correction to my previous post. Strictly speaking, it will be fastest to use the shorter of the two lists to create the set, then iterate over the other one, as this will consume less space for the set and spend less time creating the set.

[coolgod]

pretty sure python sets are implemented as hashes.