0

I have a recursion function that builds a node list from an IEnumerable of about 2000 records. The procedure currently takes around 9 seconds to complete and has become a major performance issue. The function serves to:

a) sort the nodes hierarchically

b) calculate the depth of each node

This is a stripped down example:

public class Node
{
    public string Id { get; set; }
    public string ParentId { get; set; }
    public int Depth { get; set; }
}

private void GetSortedList()
{
// next line pulls the nodes from the DB, not included here to simplify the example         
IEnumerable<Node> ie = GetNodes();

    var l = new List<Node>();
    foreach (Node n in ie)
    {
        if (string.IsNullOrWhiteSpace(n.ParentId))
        {
            n.Depth = 1;
            l.Add(n);
            AddChildNodes(n, l, ie);
        }
    }
}

private void AddChildNodes(Node parent, List<Node> newNodeList, IEnumerable<Node> ie)
{
    foreach (Node n in ie)
    {
        if (!string.IsNullOrWhiteSpace(n.ParentId) && n.ParentId == parent.Id)
        {
            n.Depth = parent.Depth + 1;
            newNodeList.Add(n);
            AddChildNodes(n, newNodeList, ie);
        }
    }
}

What would be the best way to rewrite this to maximize performance? I've experimented with the yield keyword but I'm not sure that will get me the result I am looking for. I've also read about using a stack but none of the examples I have found use parent IDs (they use child node lists instead), so I am a little confused on how to approach it.

4

1 回答 1

3

递归不是导致性能问题的原因。真正的问题是，在每次递归调用 时AddChildNodes，您都会遍历整个列表以找到当前父项的子项，因此您的算法最终为 O(n^2)。

为了解决这个问题，您可以创建一个字典，为每个节点 Id 提供所有子节点的列表。这可以在列表的单遍中完成。然后，您可以从根 ID ("") 开始并递归地访问它的每个子节点（即“深度优先遍历”）。这将只访问每个节点一次。所以整个算法是O(n)。代码如下所示。

调用后GetSortedList，排序结果在result. 请注意，如果您愿意，可以在其中创建children和result局部变量GetSortedList并将它们作为参数传递给DepthFirstTraversal。但这不必要地减慢了递归调用，因为这两个参数在每个递归调用上总是具有相同的值。

您可以使用堆栈摆脱递归，但性能提升可能不值得。

Dictionary<string, List<Node>> children = null; 
List<Node> result = null;

private void GetSortedList()
{
    var ie = data;
    children = new Dictionary<string,List<Node>>();

    // construct the dictionary 
    foreach (var n in ie) 
    {
        if (!children.ContainsKey(n.ParentId)) 
        {
            children[n.ParentId] =  new List<Node>();
        }
        children[n.ParentId].Add(n);
    }

    // Depth first traversal
    result = new List<Node>();
    DepthFirstTraversal("", 1);

    if (result.Count() !=  ie.Count()) 
    {
        // If there are cycles, some nodes cannot be reached from the root,
        // and therefore will not be contained in the result. 
        throw new Exception("Original list of nodes contains cycles");
    }
}

private void DepthFirstTraversal(string parentId, int depth)
{
    if (children.ContainsKey(parentId))
    {
        foreach (var child in children[parentId])
        {
            child.Depth = depth;
            result.Add(child);
            DepthFirstTraversal(child.Id, depth + 1);
        }
    }
}
于 2013-09-06T02:03:12.787 回答