我有一个对象的邻接列表(使用键及其父键从 SQL 数据库加载的行),我需要使用它来构建无序树。保证没有循环。
这花费的时间太长了(在大约 5 分钟内仅处理了 870K 个节点中的 ~3K)。在我的工作站 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
}
最佳答案
将节点放入排序列表或字典中。
扫描那个列表,取出每个节点,在同一个列表中找到它的父节点(二进制搜索或字典查找),将它添加到父节点的 Children 集合中。
不需要堆栈将其放入树中。
关于c# - 从邻接表创建树的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2654627/