Fill ICollection <Class> mit der richtigen Eltern-Objekte

Question

Ich habe eine Klasse:

public class MyObject { 
    int id; 
    int parentId; 
    MyObject parentObj; 
} 

und ich brauche parentObj mit der richtigen Objekte zu füllen. Ich muss dies mit Blick auf Leistung und Einfachheit tun.

So habe ich Code:

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

    return coll; 
} 

, die ich brauchen würde, die parentObj mit der richtigen Objekte aus dieser Sammlung zu füllen. Wie ich denken kann, ist der Komplex dieses Problems N * log (N).

Answer 1

Ein klassischer Ansatz ist die Verwendung von Wörterbüchern. Die Nachschlageoperation (Abrufen des Werts für einen bestimmten Schlüssel) kann in O (1) implementiert werden. Dies setzt eine gute Hash-Funktion voraus, die den Schlüssel einer Position in einem Nachschlagefeld zuordnet.

Mit der Standardimplementierung Dictionary in .net wird dies zu diesem Code führen.

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; 
} 

Es gibt einen Speicher-Overhead lookup mit Zuweisung, aber die Laufzeit wird (theoretisch) sein O (n + n) = O (n)