6

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.

Sweeney Todd
  • 880
  • 1
  • 11
  • 25
  • Is the only search you need to do on the coordinate set is whether the 9 special coordinates are in there? Do these 9 special coords change (if not, why not throw out the 2D points that do not match)? Any other searches you need to do on your points? – angelatlarge Apr 01 '13 at 19:56
  • As I added in the code part, these 9 special coordinates change in each step too. There are no other searches to do on points though. – Sweeney Todd Apr 01 '13 at 19:57
  • 2
    In this case with this number of items I would keep it simple and use a dict. http://stackoverflow.com/questions/1938614/in-what-case-would-i-use-a-tuple-as-a-dictionary-key – YXD Apr 01 '13 at 20:00
  • 2
    Tuples are hashable and immutable, so putting them into a set to check for existence would work. Alternatively, if you need to associate a value, a dictionary would work. – hughdbrown Apr 01 '13 at 20:01
  • Are the coordinates always integers? And, are they always constrained by maximum/minimum values? (ex. they will never be smaller than (0,0) or larger than (500,500)) – Kevin Apr 01 '13 at 20:28
  • Coordinates are floating point numbers, and yes, they are limited. They start from (0.0,0.0) to (1200.0,700.0) – Sweeney Todd Apr 01 '13 at 20:34
  • Ah, if they were integers, I was going to suggest storing the coordinates in a 1200-by-700 2d list. But you can't do that with floats. Just as well, it would have taken up a lot of memory. – Kevin Apr 01 '13 at 20:40

2 Answers2

7

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)
Kevin
  • 74,910
  • 12
  • 133
  • 166
  • Will using a set be more efficient than using a dict.? And is there any more sophisticated but efficient ways? (I'm looking for the [**K-d tree**](http://en.wikipedia.org/wiki/K-d_tree) @angelatlarge suggested) – Sweeney Todd Apr 01 '13 at 20:20
  • 2
    As I understand it, sets are implemented as dicts by the back end, so the efficiency will be the same. I am not aware of more efficient ways, although I can't discount their existence. – Kevin Apr 01 '13 at 20:22
  • Why would it be `O(N^2)` ? Wouldn't it just be O(1) for the list append and O(n) for the list lookup? – Davos Jun 04 '18 at 06:45
  • @Davos, I think I misread the problem the first time around - I thought that `valuesToCheck` grew in size proportionally with `myList`. So doing list lookup inside a `for coordinate in valuesToCheck:` loop would have been O(N^2). But on second look I expect `valuesToCheck` never gets bigger than nine elements, so the OP's original code would be O(N). I still recommend the set approach, which, given a constant-sized valuesToCheck, becomes O(1) total. – Kevin Jun 04 '18 at 11:48
  • Thanks for clearing that up for me, I assumed you were right and were going to point out what I'd missed. Yes of course, my comment is completely orthogonal to the Q&A. In my case I am going with a dict that uses tuples as keys because I want to store data with coordinates, thanks for your additional link to complexity and also the info about sets being implemented as dicts. That link backs up that claim exactly under `Sets` : "See dict -- the implementation is intentionally very similar" – Davos Jun 04 '18 at 13:35
  • @SweeneyTodd You can't use a dictionary for coordinates because a dictionary can only have one Y value for an X value. So coordinates with the same X value will overwrite each other. – Kleysley Oct 18 '21 at 09:31
5

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)
dckrooney
  • 3,041
  • 3
  • 22
  • 28
  • Will using a set be more efficient than using a dict.? And is there any more sophisticated but efficient ways? (I'm looking for the [link](http://en.wikipedia.org/wiki/K-d_tree) **K-d tree**. @angelatlarge suggested) – Sweeney Todd Apr 01 '13 at 20:12
  • 1
    @SweeneyTodd- If all you're doing is checking for membership, a `dict` and `set` will perform essentially the same operation. Regarding more sophisticated methods: I would first consider developing some metrics for how fast this section of code needs to be before it's "good enough". Premature optimization is the root of all evil and all that :) – dckrooney Apr 01 '13 at 21:07