c# - リスト内のオブジェクトをより効率的に検索する方法

Question

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?

score 8 · Accepted Answer

実際の要件によって異なりますが、より適切なデータ構造を選択することが 1 つのアプローチになる可能性があります。

1 つの例は、キーとして a を持つディクショナリTuple<int, int>です。最初の項目は行インデックスで、2 番目の項目は列インデックスです。「検索」はルックアップと 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.
}

score 1 · Accepted Answer

反復回数を減らす別の方法:

並べ替えMyObjectList: rowIndex Asc で -> colIndex Asc で
が等しくなるまでループMyObjectListを繰り返すforeachrowIndexarrRowLength

このアプローチにより、w0le 2d-matrix を反復する必要がなくなります + で訪問されたインスタンスの数が減少しますList<MyObject>

score 1 · Accepted Answer

二分探索を使用するSortedList<>メソッドで使用できます。IndexOfKey()

キーがSortedList object; otherwise, -1.

http://msdn.microsoft.com/en-us/library/system.collections.sortedlist(v=vs.100).aspxをご覧ください。

score 0 · Accepted Answer

別のアイデア - セルではなく特定の行 (または列) のみを検索する必要がある場合は、Lookup クラスを使用できます。

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

これがあれば、次を参照するだけで、指定された行 i のすべてのセルをすばやく取得できます。

IEnumerable<MyObject> rowCells = rowIndex[i];

4 に答える 4

Related

Reference