La forma más eficiente de crear un árbol desde la lista de adyacencia

Question

Tengo una lista de adyacencia de objetos (filas cargadas desde la base de datos SQL con la clave y su clave principal) que necesito usar para construir un árbol desordenado. Está garantizado que no tiene ciclos.

Esto lleva demasiado tiempo (solo procesa ~ 3K de nodos de 870 K en aproximadamente 5 minutos). Corriendo en mi estación de trabajo Core 2 Duo con mucha RAM.

¿Alguna idea sobre cómo hacer esto más rápido?

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. puso a los nodos en una lista ordenada o diccionario.

2. Escanee esa lista, recoja cada nodo, encuentre su nodo primario en la misma lista (búsqueda binaria o búsqueda en el diccionario), agréguelo a la colección Children del nodo primario.

No hay necesidad de una pila para poner esto en un árbol.

Answer 2

SortedList no es un buen contenedor para usar en este contexto. Es O (n) para operaciones de inserción (las llamadas repetidas a Agregar()), ya que se representa internamente como una lista plana. Usar Dictionary en lugar de SortedList será una gran mejora, ya que es O (1) tiempo de inserción amortizado.