7

順序付けされていないツリーを構築するために使用する必要のあるオブジェクト（キーとその親キーを使用してSQLデータベースからロードされた行）の隣接リストがあります。サイクルがないことが保証されています。

これには時間がかかりすぎます（約5分で87万ノードのうち約3Kしか処理されませんでした）。十分なRAMを搭載したワークステーションCore2Duoで実行しています。

これをより速くする方法について何かアイデアはありますか？

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
    }
4

2 に答える 2

5

  1. ノードをソートされたリストまたは辞書に入れます。

  2. そのリストをスキャンし、各ノードを取得し、同じリストでその親ノードを見つけ（バイナリ検索または辞書検索）、それを親ノードのChildrenコレクションに追加します。

これをツリーに入れるためにスタックは必要ありません。

于 2010-04-16T16:48:14.163 に答える
2

SortedListは、このコンテキストで使用するのに適したコンテナではありません。内部的にフラットリストとして表されるため、挿入操作（Add（）への繰り返し呼び出し）の場合はO（n）です。SortedListの代わりにDictionaryを使用すると、O（1）で償却された挿入時間になるため、大幅に改善されます。

于 2010-04-16T16:48:29.797 に答える