заселить подэлементы набора списков

Question

Предоставлено следующие классы:

public class Parent { 
    public Parent() 
    { 
     children = new List<Child>(); 
    } 

    public Guid Id { get; set; } 
    public ICollection<Child> children { get; set; } 
} 

public class Child { 
    public Guid Id { get; set; } 
    public Guid ParentId { get; set; } 
} 

И следующие данные:

List<Parent> allParents = new List<Parent>() { /* ... */ }; 
List<Child> allChildren = new List<Child>() { /* ... */ }; 

Как бы объединить каждый Child в allChildren в правильное Parent в allParents эффективно?

Единственное решение, которое я могу придумать чувствует себя действительно неэффективна:

foreach (var child in allChildren) 
{ 
    allParents.Where(p => p.Id == child.ParentId).Single().Children.Add(child); 
} 

---

Edit: Мысль альтернативного решения:

var parents = listOfAllParents(); 
var allParents = new List<Parent>(); 
foreach (var parent in parents) { 
    parent.children = allChildren.Where(c => parent.Id == c.ParentId).ToList(); 
    allParents.Add(parent); 
} 

Это может быть проще, чтобы улучшить поскольку данные индексируются ParentId ...

Answer 1

В основном есть два эффективных метода, включая подготовку быстрой структуры данных поиска на основе хэша, а затем ее использование для связывания элементов.

• Использование Dictionary<Guid, Parent> для определения местонахождения родителя по ParentId ребенка:

  var parentById = allParents.ToDictionary(parent => parent.Id); 
  foreach (var child in allChildren) 
  { 
      var parent = parentById[child.ParentId]; 
      parent.children.Add(child); 
  } 
  

• Использование ILoookup<Guid, Child> для размещения детей от Id родителя:

  var childrenByParentId = allChildren.ToLookup(child => child.ParentId); 
  foreach (var parent in allParents) 
  { 
      foreach (var child in childrenByParentId[parent.Id]) 
      { 
       parent.children.Add(child); 
      } 
  } 
  

Оба решения имеют линейное время c omplexity.