How do I implement this? Coordinate lookup....

[mrwooster]

I am having trouble implementing the following in a performance efficient way....


I have a number of particles which are randomly moving through a 'grid', every time a particle moves, its coordinates are checked to make sure they are valid.

I.E. there is a class called particle which contains the boolean function valid... every time a particle is moved, its x coord and y coord are updated (using a random number) and the valid function is called to see if the location the particle has moved to is valid.

I have a list of specific coordinates which are 'invalid'

What is the most efficient way of checking if e.g. coordinate x=57, y=88 is valid?

The problem is that the grid is approx 10,000 by 10,000 and there are around 100,000 'invalid' coordinates so I don't really want to have to loop through every coordinate every time as it takes ages...


I have thought of using 2-d arrays where I declare bool valids[10000][10000] and then use the array locations as coordinates, i.e. check to see if valids[57][88] is true.... but my program keeps on crashing...

is there a more efficient way, maybe using vectors or maps....

Thanks

[HKothari]

I don't know if this is a very good method, but I think it is. What you can do is put all of your invalid values into a STL container, probably vector, or list, then sort it. Then when ever you call the isValid function, perform a binary search or a better search algorithm to see if your value is in the container of invalid values, if not, then return true.

[Yves M]

Your program probably crashes because you tried to allocate your array on the stack and the program runs out of stack space. 10 000 x 10 000 = 100 000 000 (i.e. 100 MB). Using this array is probably close to the fastest way you can check but takes up an enormous amount of storage that is mostly empty. Using the STL, you can e.g. use a set, which will only store the invalid coordinates. That's a compromise between speed, size and ease of programming that is defendable, but it depends on your exact requirements if that's fast enough.

I wouldn't use std::list, but using a sorted vector can also work. It's conceptually the same as the set in any case.

[mrwooster]

I have implemented as you have suggested, using a binary_search and its working great! Thanks.