0

I'm looking for the most efficient way to search a large array of a class. I have an array of tiles and need to find them by ID, the only way I've come up with is below although I'm sure there are far quicker ways, probably some kind of Array.Find, but I'm unsure on the correct syntax. Any help would be greatly appreciated.

class Program
{
    public static tiles[,] tile = new tiles[100,100];
    static void Main(string[] args)
    {
        for (int x = 0; x < 100; x++)
        {
            for (int y = 0; y < 100; y++)
            {
                if (tile[x, y].ID == 2)
                {
                    // DO SOMETHING
                }
            }
        }
    }
}

public class tiles
{
    public int _ID;
    public int ID
    {
        get { return _ID; }
        set { _ID = value; }
    }
}
John Willemse
  • 6,608
  • 7
  • 31
  • 45
user3208483
  • 385
  • 5
  • 14
  • What makes you think this isn't the best way? Also, please use singular uppercase class names (e.g. `Tile`)... unless there is a valid reason to pluralize – musefan Jan 21 '14 at 09:35
  • There is not much more than sequential search possible in your case. If you really need to do it fast, besides `tiles`, hold an additional dictionary of the references with `ID` key. – Konrad Kokosa Jan 21 '14 at 09:37
  • If the data is going to be somehow sorted, you should take advantage of that (i.e. binary search), otherwise what you're doing is *probably* as good as it gets – Alex Jan 21 '14 at 09:38
  • 1
    Assuming IDs are unique, don't forget to `break` at the end of the `if` block. – dcastro Jan 21 '14 at 09:54
  • Thanks for the advice, just want to note that this isn't my code. Just something I knocked up quickly to attach with the question. – user3208483 Jan 21 '14 at 10:02

1 Answers1

1

Arrays can only be used for linear search, which means you'll have to iterate through the elements, one by one, to find the one you want.

In your case, since you seem to want to find a tile by its Id, I suggest you use an additional Dictionary<int, Tile>, where the Id is the key, to retrieve a particular tile in amortized O(1) time (if you don't mind the extra space, and assuming you only need to retrieve the tile, not its index in the array). You can still use the two-dimensional array to retrieve a tile by its index.

Pros:

  • Find a tile by its Id in amortized O(1) time.

Cons:

  • extra space
  • you need to update the dictionary whenever you update the array
dcastro
  • 66,540
  • 21
  • 145
  • 155
  • This is a comment, not an answer. – H H Jan 21 '14 at 09:35
  • Thanks, I considered a dictionary but this is just one example array, my code has many formatted the same so would get pretty messy with lots and lots of dictionaries. Ill just have to write some code to search through any array rather than writing it individually each time. – user3208483 Jan 21 '14 at 10:04
  • 1
    "Arrays can only be used for linear search..." Really? Sure linear search is the typical way of searching an array, but I could implement a random search etc. if I so desired. – NPSF3000 Jan 21 '14 at 10:16
  • @NPSF3000 Of course, you *could* implement your own algorithm (e.g., binary search, simulating a BST). Those algorithms often depend on certain invariants (e.g., elements order), so you might as well encapsulate the array in a proper class. – dcastro Jan 21 '14 at 10:29