Cách hiệu quả nhất để tạo cây từ danh sách kề

Question

Tôi có một danh sách kề các đối tượng (các hàng được nạp từ cơ sở dữ liệu SQL với khóa và khóa chính) mà tôi cần sử dụng để xây dựng một cây không theo thứ tự. Nó được đảm bảo không có chu kỳ.

Quá trình này mất quá nhiều thời gian (chỉ xử lý ~ 3K trong số 870K nút trong khoảng 5 phút). Chạy trên máy trạm Core 2 Duo của tôi với nhiều RAM.

Bất kỳ ý tưởng nào về cách thực hiện điều này nhanh hơn?

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. Đặt các nút vào một danh sách được sắp xếp hay từ điển.

2. Quét danh sách đó, chọn từng nút, tìm nút cha trong cùng một danh sách (tìm kiếm nhị phân hoặc tra cứu từ điển), thêm nó vào bộ sưu tập Trẻ em của nút cha.

Không cần một ngăn xếp để đặt nó vào một cái cây.

Answer 2

SortedList không phải là vùng chứa tốt để sử dụng trong ngữ cảnh này. Nó là O (n) cho hoạt động chèn (các cuộc gọi lặp đi lặp lại đến Add()), vì nó được biểu diễn bên trong như một danh sách phẳng. Sử dụng từ điển thay vì SortedList sẽ là một cải tiến lớn, vì nó là O (1) thời gian chèn khấu hao.