从邻接表创建树的最有效方法
我有一个对象的邻接列表（使用键及其父键从 SQL 数据库加载的行），我需要使用它来构建无序树。保证没有循环。
这花费了太长的时间（大约 5 分钟内仅处理了 870K 个节点中的约 3K 个节点）。在我的具有充足 RAM 的 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
}
I have an adjacency list of objects (rows loaded from SQL database with the key and it's parent key) that I need to use to build an unordered tree. It's guaranteed to not have cycles.
This is taking wayyy too long (processed only ~3K out of 870K nodes in about 5 minutes). Running on my workstation Core 2 Duo with plenty of RAM.
Any ideas on how to make this faster?
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
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
将节点放入排序列表或字典中。
扫描该列表，选取每个节点，在同一列表中找到其父节点（二分搜索或字典查找），将其添加到父节点的 Children 集合中。
堆栈不需要将其放入树中。
Put the nodes into a sorted list or dictionary.
Scan that list, pick up each node, find its parent node in the same list (binary search or dictionary lookup), add it to the Children collection of the parent node.
There's no need for a Stack to put this into a tree.
在这种情况下，SortedList 不是一个好的容器。插入操作（重复调用 Add()）的时间复杂度为 O(n)，因为它在内部表示为平面列表。使用 Dictionary 代替 SortedList 将是一个很大的改进，因为它的摊销插入时间为 O(1)。
SortedList is not a good container to use in this context. It is O(n) for insertion operations (the repeated calls to Add()), as it is internally represented as a flat list. Using Dictionary instead of SortedList will be a large improvement, as it is O(1) amortized insertion time.