0

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?

  • 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? – BobDalgleish Nov 3 '15 at 12:54
0

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;
}
  • 1
    Thanks for the advice / rule of thumb. I don't completely understand the nested array example you described. Can you expand on that please? – scott_f Nov 3 '15 at 1:06
0

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).

  • Thanks! That looks very interesting. I will have a deep dive and see if I can incorporate something like that. – scott_f Nov 3 '15 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.