Méthode la plus efficace pour créer une arborescence à partir d'une liste d'adjacences

Question

J'ai une liste d'adjacences d'objets (lignes chargées depuis la base de données SQL avec la clé et sa clé parent) que je dois utiliser pour construire une arborescence non ordonnée. C'est garanti de ne pas avoir de cycles.

Cela prend wayyy trop longtemps (traité seulement ~ 3K sur 870K nœuds en environ 5 minutes). En cours d'exécution sur mon poste de travail Core 2 Duo avec beaucoup de RAM.

Des idées sur la façon d'accélérer les choses?

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. Mettre les noeuds dans une liste triée ou un dictionnaire. Scannez cette liste, sélectionnez chaque nœud, trouvez son nœud parent dans la même liste (recherche binaire ou recherche de dictionnaire), ajoutez-la à la collection Children du nœud parent.

Une pile n'est pas nécessaire pour placer ceci dans un arbre. SortedList n'est pas un bon conteneur à utiliser dans ce contexte.

Answer 2

C'est O (n) pour les opérations d'insertion (les appels répétés à Add()), car il est représenté en interne sous la forme d'une liste plate. Utiliser Dictionary à la place de SortedList sera une amélioration importante, car il s'agit d'un temps d'insertion amorti en O (1).