Search Algorithm Question

Question

I need to retrieve five stars from a group of stars so I can hide them by turning their visible flag to "false".

I know the x, y coordinate value of each star I am looking for. My algorithm opens a transaction and retrieves a group of stars whose x, y values falls within the extents of the five stars I am looking for.

This is faster than opening five separate transactions and looking at a particular x, y location of each star individually.

With the group of stars below what I want to do is to compare the x, y value of each star to find a match to the one of the five I am looking for.

Group of 400+ Stars to search

---

 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************
 *********************************************

My thoughts on this is I have two choices for iterating through the collection:

(1) I can iterate through the 400+ stars one at a time, grab the x, y values of each and then iterate through the five sets of coordinates to see if it matches one of the five I am looking for.

(2) I can iterate through the "five stars to find" one at a time and then iterate the 400+ stars collection looking for a match

NB:

The stars collection has 400+ stars that fall within the extents.

The "visible" property only works for items in the stars collection.

The stars_to_find collection has the coordinates of the five stars I am looking for.

Code snippets

(1)

foreach (Star star in stars)
{
 foreach (Star star_to_find in stars_to_find)
 {
 if (star.Coordinates.Equals(star_to_find.Coordinates))
 {
 star.Visible = false;
 }
 }
}

(2)

foreach (Star star_to_find in stars_to_find)
{
 foreach (Star star in stars)
 {
 if (star.Coordinates.Equals(star_to_find.Coordinates))
 {
 star.Visible = false;
 }
 }
}

Is either search method, (1) or (2), faster than the other? Is there a different search algorithm that would work better?

• BobDalgleish: What tests have you run? Both algorithms are very short, so setting up and running a number of performance comparison tests should be really straightforward. How large are your data sets?

Answer 1

As a rule of thumb put the collection that is easiest to loop over on the inner most loop. Your 5 stars to find would just be a simple array so put that in the inner loop.

However it's much more efficient if you don't need a loop in the first place or reduce the number of iterations of the loop.

For example you could keep the stars in a nested Star[][] array (array of arrays) so you can do stars[x][y] and directly get the star you need.

If you need something less dense then you can use a hashmap and use the Coordinates as key. In both cases the eventual algorithm comes down to:

foreach (Star star_to_find in stars_to_find)
{
 stars.get(star_to_find.Coordinates).Visible = false;
}

• scott_f: Thanks for the advice / rule of thumb. I don't completely understand the nested array example you described. Can you expand on that please?

Answer 2

Generally speaking, when you need to search a collection for items that fall within a range of 2d coordinates, you should probably be using a quadtree (or an octree for 3d coordinates).

• scott_f: Thanks! That looks very interesting. I will have a deep dive and see if I can incorporate something like that.