python: Find matching tuples in the list

Question

What is the quickest way to find matching 2-tuples in another list of 2-tuples?

The following codes looks extremely inefficient. loc1 and loc2 are list of tuples of (x,y) coordinates.

loc3=[]
for loc in loc1:
    if loc in loc2:
        loc3.append(loc)

I think hashing is the key but not sure how to do it on Python. Please teach me an elegant code. Thanks.

Answer 1

You can use sets and intersection:

loc3 = set(loc1).intersection(loc2)

This gives you a set which is unordered and won't contain duplicates (and enforces that the items are hashable). If that's a problem, see the other answer by Phil Frost. However, this should be significantly more efficient where order and duplicates are unnecessary.

A order preserving solution which can contain duplicates, but requires hashability of the items (in loc2) is as follows:

sloc2 = set(loc2)
loc3 = [ item for item in loc1 if item in sloc2 ]  #still O(m)

In python, a set is simply a hash table. Checking to see if an item is contained in that set is an (approximately) O(1) operation because the position of the item is found via hashing.