2

我正在尝试在 .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;
}
4

2 回答 2

2

如果我理解正确，你

  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；您可以延迟它的构建，直到您知道查询返回的记录数。

于 2012-07-09T03:17:24.027 回答
0

使用NHibernate怎么样？它适用于 .net 2 plus，因此您也可以继续使用它。

于 2012-07-09T01:24:20.840 回答