Najbardziej efektywny sposób tworzenia drzewa z listy sąsiedztwa

Question

Mam listę obiektów znajdujących się obok siebie (wiersze załadowane z bazy danych SQL z kluczem i jego kluczem nadrzędnym), których potrzebuję do zbudowania nieuporządkowanego drzewa. Gwarantuje to, że nie ma cykli.

Trwa to zbyt długo (przetwarzane tylko ~ 3K z 870K węzłów w około 5 minut). Działa na mojej stacji roboczej Core 2 Duo z dużą ilością pamięci RAM.

Jakieś pomysły, jak przyspieszyć działanie?

public class StampHierarchy { 
    private StampNode _root; 
    private SortedList<int, StampNode> _keyNodeIndex; 

    // takes a list of nodes and builds a tree 
    // starting at _root 
    private void BuildHierarchy(List<StampNode> nodes) 
    { 
     Stack<StampNode> processor = new Stack<StampNode>(); 
     _keyNodeIndex = new SortedList<int, StampNode>(nodes.Count); 

     // find the root 
     _root = nodes.Find(n => n.Parent == 0); 

     // find children... 
     processor.Push(_root); 
     while (processor.Count != 0) 
     { 
      StampNode current = processor.Pop(); 

      // keep a direct link to the node via the key 
      _keyNodeIndex.Add(current.Key, current); 

      // add children 
      current.Children.AddRange(nodes.Where(n => n.Parent == current.Key)); 

      // queue the children 
      foreach (StampNode child in current.Children) 
      { 
       processor.Push(child); 
       nodes.Remove(child); // thought this might help the Where above 
      } 
     } 
    } 
} 

    public class StampNode { 
     // properties: int Key, int Parent, string Name, List<StampNode> Children 
    } 

Answer 1

1. Put węzły do ​​posortowanej listy lub słownika.

2. Zeskanuj tę listę, podnieś każdy węzeł, znajdź jego węzeł nadrzędny na tej samej liście (wyszukiwanie binarne lub wyszukiwanie w słowniku), dodaj go do kolekcji Dzieci węzła nadrzędnego.

Nie ma potrzeby, aby stos umieszczał go w drzewie.

Answer 2

SortedList nie jest dobrym kontenerem do użycia w tym kontekście. Jest to O (n) dla operacji wstawiania (powtarzające się wywołania Add()), ponieważ jest wewnętrznie reprezentowane jako lista pusta. Używanie Dictionary zamiast SortedList będzie dużym usprawnieniem, ponieważ jest to O (1) czas amortyzacji.