塗りつぶしいるICollection <Class>は

Question

は、私はクラスを持つオブジェクト。パフォーマンスとシンプルさを見てこれを行う必要があります。

だから私はコードを持っている：

ICollection<MyObject> Method(ICollection<MyObject> coll) 
{ 
    foreach(var item in coll) 
     ... 

    return coll; 
} 

私はこのコレクションから適切なオブジェクトとparentObjを記入する必要があります。私はこの問題の複雑さがN * log（N）であると考えることができます。

Answer 1

古典的なアプローチは辞書を使用しています。ルックアップ操作（特定のキーの値を取得）は、O（1）に実装できます。これは、キーをルックアップ配列内の位置にマッピングする良いハッシュ関数を前提としています。

デフォルトのDictionary実装を.netで使用すると、このコードになります。

ICollection<MyObject> Method(ICollection<MyObject> coll) 
{ 
    var lookup = new Dictionary<int, MyObject>(); 
    foreach (var item in coll) 
    { 
     lookup.Add(item.id, item); 
    } 
    foreach (var item in coll) 
    { 
     item.parentObj = lookup[item.parentId]; 
    } 

    return coll; 
} 

ありlookupを割り当てると、メモリのオーバーヘッドがあるが、ランタイムが（理論上）O（N + N）となります= O（n）の