#algorithm #matrix #tree #adjacency-matrix
Вопрос:
У меня есть список объектов смежности (строки, загруженные из базы данных SQL с ключом, и это родительский ключ), который мне нужно использовать для построения неупорядоченного дерева. У него гарантированно не будет циклов.
Это занимает слишком много времени (обрабатывается только ~3 тыс. узлов из 870 тыс. примерно за 5 минут). Работает на моей рабочей станции Core 2 Duo с большим количеством оперативной памяти.
Есть какие-нибудь идеи о том, как сделать это быстрее?
public class StampHierarchy { private StampNode _root; private SortedListlt;int, StampNodegt; _keyNodeIndex; // takes a list of nodes and builds a tree // starting at _root private void BuildHierarchy(Listlt;StampNodegt; nodes) { Stacklt;StampNodegt; processor = new Stacklt;StampNodegt;(); _keyNodeIndex = new SortedListlt;int, StampNodegt;(nodes.Count); // find the root _root = nodes.Find(n =gt; 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 =gt; 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, Listlt;StampNodegt; Children } Комментарии:
1. Вам обязательно нужно делать это на C#? Потому что будет намного быстрее упорядочить узлы по пути в SQL, с помощью которого вы сможете построить дерево за O(N) время.
2. как я могу упорядочить по пути в SQL? Мои данные похожи на организационную диаграмму… много детей и много неровных уровней.
Ответ №1:
- Поместите узлы в отсортированный список или словарь.
- Просканируйте этот список, выберите каждый узел, найдите его родительский узел в том же списке (двоичный поиск или поиск по словарю), добавьте его в коллекцию дочерних узлов родительского узла.
Нет необходимости в стеке, чтобы поместить это в дерево.
Комментарии:
1. Стоит отметить, что сортировка узлов по ключу перед помещением их в отсортированный список имеет огромное значение в скорости. Использование словаря также является другой альтернативой, если память не является основным ограничением.
Ответ №2:
SortedList-неподходящий контейнер для использования в этом контексте. Это O(n) для операций вставки (повторные вызовы Add()), так как он внутренне представлен в виде плоского списка. Использование словаря вместо сортированного списка будет большим улучшением, так как это O(1) амортизированное время вставки.
Комментарии:
1. Ах, еще я соскучился по течению. Дети. Добавить строку. Вы не хотите повторно сканировать весь список узлов в поисках каждого родителя. Как и предполагал Хайтехрайдер, ввод узлов в словарь сначала значительно ускорит процесс, поскольку, опять же, вы измените операцию O(n) на операцию O(1).