Заливка ICollection <Class> с правильным родителем объекты

Question

У меня есть класс:

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

и мне нужно заполнить parentObj с соответствующими объектами. Мне нужно сделать это, взглянув на производительность и простоту.

Так что я код:

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 распределения, но среда выполнения будет (теоретически) О (п + п) = О (п)