У меня есть список смежности объектов (строки, загруженные из базы данных SQL с ключом, и это - родительский ключ), что я должен использовать для создания незаказанного дерева. Это, как гарантируют, не будет иметь циклы.
Это берет wayyy слишком долго (обработал только ~3K из 870K узлов приблизительно за 5 минут). Работа моего Core 2 Duo рабочей станции с большим количеством RAM.
Какие-либо идеи о том, как сделать это быстрее?
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
}
Поместите узлы в отсортированный список или словарь.
Просканируйте этот список, выберите каждый узел, найдите его родительский узел в том же списке (бинарный поиск или поиск по словарю), добавьте его в коллекцию Children родительского узла.
Нет необходимости в стеке, чтобы поместить это в дерево.
SortedList не подходит для использования в этом контексте. Это O (n) для операций вставки (повторные вызовы Add ()), так как внутри он представлен в виде плоского списка. Использование Dictionary вместо SortedList будет большим улучшением, так как это амортизированное время вставки O (1).