Efficient way to store and search coordinates in python

Question

I'm writing a simple game in python(2.7) in pygame. In this game, I have to store 2D coordinates. The number of these items will start from 0 and increase by 2 in each step. They will increase up to ~6000. In each step I have to check whether 9 specific coordinates are among them, or not. I've tried to store them simply in a list as (x,y), but it is not efficient to search in such a list.

How can I store these coordinates so it will be more efficient to search among them?

What I was trying to do in each step:

# Assuming:
myList = []
co1 = (12.3,20.2) # and so on..
valuesToCheck = [co1,co2,co3,co4,co5,co6,co7,co8,co9]

# In each step:
# Adding 2 coordinates
myList.append((x1,y1))
myList.append((x2,y2))
# Searching 9 specific coordinates among all
for coordinate in valuesToCheck:
    if coordinate in myList:
        print "Hit!"
        break
# Note that the valuesToCheck will change in each step.
del valuesToCheck[0]
valuesToCheck.append(co10)

Coordinates are floating point numbers, and their highest values are limited. They start from (0.0,0.0) to (1200.0,700.0).

I've searched about this but stored values were either string or constant numbers.

Solution 1

Maintain a set alongside your list, or replacing the list entirely if you have no other use for it. Membership checking and adding are O(1) on average for sets, so your overall algorithm will be O(N) compared to the O(N^2) of just using a list.

myList = []
mySet = set()
co1 = (12,20) # and so on..
valuesToCheck = [co1,co2,co3,co4,co5,co6,co7,co8,co9]

# In each step:
# Adding 2 coordinates
myList.append((x1,y1))
myList.append((x2,y2))
mySet.add((x1, y1))
mySet.add((x2, y2))
# Searching 9 specific coordinates among all
for coordinate in valuesToCheck:
    if coordinate in mySet:
        print "Hit!"
        break
# Note that the valuesToCheck will change in each step.

del valuesToCheck[0]
valuesToCheck.append(co10)

Solution 2

If I understand correctly, you're adding elements to myList, but never removing them. You're then testing every element of valuesToCheck for memebership in myList.

If that's the case, you could boost performance by converting myList to a set instead of a list. Testing for membership in a list is O(n), while testing for membership in a set is typically O(1).

Your syntax will remain mostly unchanged:

mySet = set()

# your code

# Adding 2 coordinates
mySet.add((x1,y1))
mySet.add((x2,y2))
# Searching 9 specific coordinates among all
for coordinate in valuesToCheck:
    if coordinate in mySet:
        print "Hit!"
        break
# Note that the valuesToCheck will change in each step.
del valuesToCheck[0]
valuesToCheck.append(co10)