从邻接表创建树的最有效的方法 [英] Most efficient way of creating tree from adjacency list

问题描述

我有对象的邻接表（从SQL数据库加载的关键行和它的父键），我需要用它来构建一个无序树。它保证不会有周期。

这是走wayyy太长（仅处理了〜3K出870K在5分钟内节点）。运行在我的工作站酷睿2有足够的内存。

在如何使这一更快任何想法？

 公共类StampHierarchy {
    私人StampNode _root;
    私有排序列表＆LT; INT，StampNode＆GT; _keyNodeIndex;

    //取节点列表，并建立一个树
    //开始_root
    私人无效BuildHierarchy（名单＆LT; StampNode个节点）
    {
        堆叠＆LT; StampNode＆GT;处理器=新的堆栈＆LT; StampNode＆GT;（）;
        _keyNodeIndex =新的排序列表＆LT; INT，StampNode＆GT;（nodes.Count）;

        //找到根
        _root = nodes.Find（N =＆GT; n.Parent == 0）;

        //发现孩子...
        processor.Push（_root）;
        而（processor.Count！= 0）
        {
            StampNode电流= processor.Pop（）;

            //保持直接联系的节点通过关键
            _keyNodeIndex.Add（current.Key，电流）;

            //增加儿童
            current.Children.AddRange（nodes.Where（N =＆GT; n.Parent == current.Key））;

            //排队孩子
            的foreach（StampNode孩子在current.Children）
            {
                processor.Push（子）;
                nodes.Remove（子）; //想这可能有助于上述哪里
            }
        }
    }
}

    公共类StampNode {
         //属性：INT重点，诠释家长，字符串名称，目录和LT; StampNode＆GT;儿童
    }
 

解决方案

1. 把节点分成一个排序列表或字典。

2. 扫描列表，拿起每一个节点，找到它的父节点在同一列表（二进制搜索或者字典查找），将其添加到父节点的孩子集合。

有没有需要一个堆栈来把这个变成一棵树。

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
    }

解决方案

1. Put the nodes into a sorted list or dictionary.

2. 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.

这篇关于从邻接表创建树的最有效的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！