Remplir ICollection <Class> avec des objets parent approprié

Question

J'ai une classe:

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

et je dois remplir parentObj avec des objets appropriés. Je dois faire ceci avec regard sur la performance et la simplicité.

J'ai le code:

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

    return coll; 
} 

que je besoin de remplir le parentObj avec des objets appropriés de cette collection. Comme je peux penser que le complexe de ce problème est N * log (N).

Answer 1

Une approche classique utilise des dictionnaires. L'opération de recherche (récupérer la valeur pour une clé donnée) peut être implémentée dans O (1). Cela suppose une bonne fonction de hachage qui mappe la clé à une position dans un tableau de recherche. Si vous utilisez l'implémentation Dictionary par défaut dans .net, cela se traduira par ce code.

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

Il y a une surcharge de la mémoire avec l'allocation lookup, mais le temps d'exécution sera (théoriquement) O (n + n) = O (n)