CODEWITHSUNDEEP
c#.netlist
woodykiddy
woodykiddy

Reputation: 6455

More efficient way to find object in List<object>

Assume that arrRowLength&arrColLength have all been properly defined and assigned, and MyObjectList<MyObject> has been instantiated and populated with a few objects.

class MyObject
{
    public MyObject() { }
    public int rowIndex {get; set;}
    public int colIndex {get; set;}
} 

List<MyObject> MyObjectList = new List<MyObject>();

for (int r = 1; r <= arrRowLength; r++)
{
    for (int c = 1; c <= arrColLength; c++)
    {
         MyObject mo = MyObjectList.Find(item => (item.rowIndex == r && item.colIndex == c));
         if(mo != null)
         {
              //found, do sth...
         }
    }
}

Above is my current approach to finding a MyObject object from MyObjectList, where rowIndex and colIndex equal to r and c in for loops.

However, Find() has O(n) complexity. The larger the MyObjectList gets, the longer it takes. So I wonder if there's a better / more efficient way to find the object. How can I implement this with .BinarySearch() method?

Upvotes: 2

Views: 273

Answers (4)

Woodman
Woodman

Reputation: 1137

Another idea - for cases when you need to find only specific row (or column) and not the cell you can use Lookup class: 

Lookup<int, MyObject> rowIndex = MyObjectList.ToLookup(o => o.rowIndex, o => o);

having this you can quickly retrieve all cells of given row i by simply referencing: 

IEnumerable<MyObject> rowCells = rowIndex[i];

Upvotes: 0

Nogard
Nogard

Reputation: 1789

Another way to reduce number of iterations:

  1. Sort MyObjectList: by rowIndex Asc -> by colIndex Asc
  2. Iterate MyObjectList with foreach loop until rowIndex is equal to arrRowLength

This approach eliminates neccessity of iterating wh0le 2d-matrix + reduces number of visited instances in List<MyObject>

Upvotes: 1

888
888

Reputation: 3396

You can use SortedList<> with its method IndexOfKey(), which uses a binary search.

It returns the zero-based index of the key parameter, if key is found in the SortedList object; otherwise, -1.

Take a look at http://msdn.microsoft.com/en-us/library/system.collections.sortedlist(v=vs.100).aspx

Upvotes: 1

Daniel Hilgarth
Daniel Hilgarth

Reputation: 174299

It depends on your real requirements, but choosing more appropriate data structures could be one approach.

One example would be a Dictionary with a Tuple<int, int> as the key, where the first item is the row index and the second item is the column index. "Search" would now be a lookup and O(1):

Dictionary<Tuple<int, int>, MyObject> MyObjects;
MyObject o;
if(MyObjects.TryGetValue(Tuple.Create(r, s), out o)
{
    //found, do sth...
}

Adding a new object to the dictionary would look like this:

MyObjects.Add(Tuple.Create(o.rowIndex, o.colIndex), o);

If - for some reason - you would need to iterate all objects in another method, you can still do this using the Values property of the dictionary:

foreach(var o in MyObjects.Values)
{
    // do something for each of your objects.
}

Upvotes: 8

Related Questions