2

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?

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.
}
4

4 回答 4

8

这取决于您的实际需求，但选择更合适的数据结构可能是一种方法。

一个示例是以 aTuple<int, int>作为键的字典，其中第一项是行索引，第二项是列索引。“搜索”现在将是一个查找和 O(1)：

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

向字典中添加一个新对象如下所示：

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

如果 - 由于某种原因 - 您需要在另一个方法中迭代所有对象，您仍然可以使用Values字典的属性来执行此操作：

foreach(var o in MyObjects.Values)
{
    // do something for each of your objects.
}
于 2013-02-21T08:37:39.990 回答
1

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

于 2013-02-21T08:39:51.037 回答
1

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>

于 2013-02-21T08:52:30.073 回答
0

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];
于 2013-02-21T09:10:59.263 回答