Самый эффективный способ создания дерева из списка смежности - PullRequest
Новая
       9

Самый эффективный способ создания дерева из списка смежности

6 голосов
/ 16 апреля 2010

У меня есть список смежных объектов (строки, загруженные из базы данных SQL с ключом и его родительским ключом), которые мне нужно использовать для построения неупорядоченного дерева. Это гарантированно не имеет циклов.

Это занимает слишком много времени (обрабатывается только ~ 3K из 870K узлов за 5 минут). На моей рабочей станции Core 2 Duo с большим количеством оперативной памяти.

Есть идеи, как сделать это быстрее? 

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
    }

Ответы [ 2 ]

4 голосов
/ 16 апреля 2010

  1. Поместите узлы в отсортированный список или словарь.

  2. Сканирование этого списка, выбор каждого узла, поиск его родительского узла в том же списке (бинарный поиск или поиск по словарю), добавление его в коллекцию Children родительского узла.

Стек не нужен, чтобы поместить это в дерево.

2 голосов
/ 16 апреля 2010

SortedList не является хорошим контейнером для использования в этом контексте. Это O (n) для операций вставки (повторные вызовы Add ()), так как он внутренне представлен как плоский список. Использование словаря вместо SortedList будет большим улучшением, так как это время вставки O (1).

...