c# - 是否有更好的方法将 SQL 中的分层数据填充到类结构、C# 或 VB.NET 中？

Question

我正在尝试在 .NET 2.0(是的，2.0)应用程序中填充分层数据，并且现在无法升级(因此没有 LINQ、LINQ Bridge 或其他东西)。

我想知道是否有更好的方法将分层数据填充到这个类结构中？我很确定有更好的方法来实现这一点。

如果能找到一种好方法来做到这一点，那就太好了。如果有人有时间展示 .NET 2.0 方式，并且如果有不同的方式他们会在 .NET 4.0+ 中实现，那就太好了。

这是节点类型结构的示例:

using System.Collections.Generic;

public class ExampleNode
{

private int _id;

private Nullable<int> _parentId;


private int _depth;

private List<ExampleNode> _children = new List<ExampleNode>();

public ExampleNode()
{
}

public virtual int ApplicationNumber {
    get { return _id; }
    set { _id = value; }
}

public virtual Nullable<int> ParentId {
    get { return _parentId; }
    set { _parentId = value; }
}


public virtual int Depth {
    get { return _depth; }
    set { _depth = value; }
}


public virtual List<ExampleNode> Children {
    get { return _children; }
    set { _children = value; }
}
}

这是一个用于填充节点结构的示例函数。这似乎不是执行此操作的最佳方法，并且有可能不填充孙子类型数据。深度作为层次结构中的级别从存储过程返回(级别为 0 的项目为顶级，如果节点是顶级节点的子节点，则为级别 1，顶级节点的孙子节点为级别2等)

public List<ExampleNode> GetNodes()
{
// This may not be optimal.

List<ExampleNode> nodeList = new List<ExampleNode>();
Dictionary<int, ExampleNode> nodeDictionary = new Dictionary<int, ExampleNode>();

using (SqlDataReader reader = SqlHelper.ExecuteReader(ConfigurationManager.ConnectionStrings("SqlServer").ConnectionString, CommandType.StoredProcedure, "proc_GetNodeStructure", new SqlParameter("@UserId", userId), new SqlParameter("@NodeTypeId", nodeType))) {
    while (reader.Read) {
        ExampleNode nodeInstance = new ExampleNode();

        nodeInstance.Id = Convert.ToInt32(reader("Id"));
        nodeInstance.Depth = Convert.ToInt32(reader("Depth"));


        if (!Information.IsDBNull(reader("ParentId"))) {
            nodeInstance.ParentId = Convert.ToInt64(reader("ParentId"));
        }

        // Add to list
        nodeList.Add(nodeInstance);

        // Add to dictionary
        nodeDictionary.Add(nodeInstance.Id, nodeInstance);

    }
}

foreach (ExampleNode item in nodeList) {
    if (item.ParentId.HasValue) {
        nodeDictionary(item.ParentId).Children.Add(item);
    }

}

for (int i = nodeList.Count - 1; i >= 0; i += -1) {
    if (nodeList(i).Depth > 0) {
        nodeList.RemoveAt(i);
    }
}

return nodeList;
}

Answer 1

如果我理解正确的话，你

1. 将节点收集到列表和字典中
2. 迭代列表并通过字典安排父/子关系
3. 从列表中删除深度为正的节点

... 留下包含层次结构中最顶层节点的列表。你的算法对我来说似乎是正确的。

前两个操作相对于节点数量而言，时间和空间复杂度都是 O(n)，这非常好!

您正在做的唯一真正低效的事情是在步骤 3 中从列表中删除元素。因为底层存储是一个向量，所以从列表前面删除一个元素的成本很高，因为所有剩余的元素都需要被删除。抄下来。您试图通过向后迭代列表来最小化此类复制的数量。想象一下，列表的后半部分是父节点，前半部分是子节点。每当删除子节点时，每次删除子节点时，您仍然需要复制原始列表大小的一半。这接近 O(n^2) 行为。

因此，对于第 3 步，如果您希望及时提高性能，您至少有两个选择:

1. 创建第二个列表，其中仅包含第一个列表中深度 == 0 的元素。
2. 改用链表，这样删除操作的时间复杂度为 O(1)，而不是 O(n) 性能。

这是第一个选项的代码:

...

List<ExampleNode> roots = new List<ExampleNode>();
for (int i = 0; i < nodeList.Count; i ++) { 
    if (nodeList[i].Depth == 0) { 
        roots.Add(nodeList[i]);
    }
} 
return roots;

通过计算步骤 1 或 2 中有多少个根节点，然后初始化第二个列表，使其容量等于根节点的数量，您可能会节省更多时间。这将防止在向列表添加元素时不必要的分配和复制底层列表向量。

List<ExampleNode> roots = new List<ExampleNode>(rootCount);

这同样适用于第一个nodeList；您可以延迟其构建，直到知道查询返回的记录数。