快速 TreeView

• 下载源代码 - 39.4 KB

引言

在将项加载到 Windows Forms 标准 TreeView 时，您会发现加载大量项可能需要花费 enormous 的时间！这个简单的扩展将使加载速度 lightning fast。

在这个简单的演示应用程序中，我使用了我自己的 TreeViewFast 控件并将其与标准的 TreeView 进行了比较。您可以看到，差异是 substantial 的。

背景

在我的项目中，我需要一次性加载 ~100,000 项。在使用 TreeView 控件时，我发现花费了我 40-50 分钟，我简直要 depression 了……

我的第一个尝试是使用 SQL Server 2008 HierarchyId 来重组这些项。这在很多方面都很有趣且有用，但对我来说，它几乎没有带来任何改变。我们有一个典型的“相邻”表列表，其中每个项都存储在一个表中，并可能引用一个 parentId。

在将项添加到 TreeView 节点的集合时，我不知道它们的结构，除了对父项的引用。这意味着我被迫使用 TreeViewNodesCollection 的 Find 方法来获取父项。显然，TreeView 在内部数据结构上性能非常差，对于大型项集合来说，它的速度非常慢。

我知道有很多不错的付费控件具有许多很棒的功能。但我只是想证明一点，如果所有您需要的是更好的性能，那么对现有 TreeView 的简单扩展实际上就可以做到。

标准方法

我首先生成一组 large 的演示项。在这种情况下，它们是具有连续 Id 属性和随机生成的名称组合的 employee。每个 employee 通过一个可选的 ManagerId 与一个 manager 相关联。如果设置为 NULL，则表示该 employee 处于顶层。

将这些项作为节点添加到 TreeView 控件的标准方法如下：

foreach (var employee in employees)
{
    var node = new TreeNode { Name = employee.EmployeeId.ToString(), 
                              Text = employee.Name,
                              Tag = employee };
    if (employee.ManagerId.HasValue)
    {
        var parentId = employee.ManagerId.Value.ToString();
        var parentNode = myTreeView.Nodes.Find(parentId, true)[0];
        parentNode.Nodes.Add(node);
    }
    else
    {
        myTreeView.Nodes.Add(node);
    }
}  

当集合很小时，这还可以，但当您开始计算成千上万时，就太糟糕了。事实上，加载时间是项数量的指数增长，如以下表格所示。
给定的时间以毫秒为单位。将 100,000 项加载到标准 TreeView 中需要 3,427,380 ms。这相当于 57 分钟！而在 TreeViewFast 中，只需要 1,467 ms，也就是 1.4 秒。
我跳过了尝试将 1,000,000 项加载到普通的 TreeView 中……

在 TreeViewFast 实现中，加载时间是成比例的，甚至更快。

优化方法

我决定使用标准的 TreeView，只是对其进行 sedikit 扩展。所以我创建了一个名为 TreeViewFast 的类，它继承自 TreeView。主要技巧是创建一个内部 Dictionary 来存储所有节点。这样，即使对于大型集合，所有父项查找也始终很快。

我决定使用 int 作为项 Id 的数据类型，并使用 int? 作为 parentId。这一点可以商榷，但在大多数情况下，我认为它将适合现有的数据结构。我尝试使用 string，但发现它会使时间慢 10%。如果您需要 string 或 guid，只需修改代码即可，非常简单。

private readonly Dictionary<int, TreeNode> _treeNodes = new Dictionary<int, TreeNode>();  

您可以看到，我决定将 TreeNode 项存储在 Dictionary 中。这样使用起来很方便。item 对象将存储在 TreeNode 的泛型 Tag 属性中。这样，我们始终可以轻松访问 item 对象。

理想情况下，我们希望拥有一个控件类的泛型构造函数。类似这样的

public class TreeViewFast<T> : TreeView 

这将使在类中的任何地方引用类型变得非常容易。但不幸的是，Windows Forms 设计器无法处理具有泛型构造函数的控件。

更好的方法是使用实现通用接口的类型，例如 ITreeViewFastItem。
但这将强制所有实体访问该接口。在我的设置中，实体定义在不能依赖于我定义所有控件的 Windows Forms 项目的项目中。

因此，在我的情况下，我决定允许每个方法都有一个 T 说明符，并在必要时，我输入解析函数来帮助加载器解释对象。这意味着 Load 方法看起来像这样：

/// <summary>
/// Load the TreeView with items.
/// </summary>
/// <typeparam name="T">Item type</typeparam>
/// <param name="items">Collection of items</param>
/// <param name="getId">Function to parse Id value from item object</param>
/// <param name="getParentId">Function to parse parentId value from item object</param>
/// <param name="getDisplayName">Function to parse display name
/// value from item object. This is used as node text.</param>
public void LoadItems<T>(IEnumerable<T> items, Func<T, int> getId, 
       Func<T, int?> getParentId, Func<T, string> getDisplayName)
{
    // Clear view and internal dictionary
    Nodes.Clear();
    _treeNodes.Clear();
 
    // Load internal dictionary with nodes
    foreach (var item in items)
    {
        var id = getId(item);
        var displayName = getDisplayName(item);
        var node = new TreeNode { Name = id.ToString(), 
                                    Text = displayName, 
                                    Tag = item };
        _treeNodes.Add(getId(item), node);
    }

    // Create hierarchy and load into view
    foreach (var id in _treeNodes.Keys)
    {
        var node = GetNode(id);
        var obj = (T)node.Tag;
        var parentId = getParentId(obj);
        if (parentId.HasValue)
        {
            var parentNode = GetNode(parentId.Value);
            parentNode.Nodes.Add(node);
        }
        else
        {
            Nodes.Add(node);
        }
    }
} 

节点和对象的实际存储在 Dictionary 中。

为了使节点可见，它们被添加到 TreeView 的内部 Nodes 集合中，从而使预期的层次结构按预期显示。Nodes 集合实际上只会持有对 Dictionary 对象的引用，所以我们不会浪费任何内存。

重要的区别在于 GetNode 查找，它现在可以使用快速的 Dictionary 查找。

/// <summary>
/// Retrieve TreeNode by Id.
/// Useful when you want to select a specific node.
/// </summary>
/// <param name="id">Item id</param>
public TreeNode GetNode(int id)
{
    return _treeNodes[id];
}

调用上述 Load 方法很简单：

// Define functions needed by the load method
Func<Employee, int> getId = (x => x.EmployeeId);
Func<Employee, int?> getParentId = (x => x.ManagerId);
Func<Employee, string> getDisplayName = (x => x.Name);
 
// Load items into TreeViewFast
myTreeViewFast.LoadItems(employees, getId, getParentId, getDisplayName); 

控件还添加了一些额外的便利方法：GetItems 和 GetDescendants。当您需要搜索内部项集合或查找特定项的子项时，它们非常有用。

学到的教训

• 对性能进行详细测量以找出关键瓶颈始终很有用！
• 大量数据本身不是问题，只要您小心处理它们。
• 我喜欢 Dictionaries。它们似乎一次又一次地拯救了我。

历史

• 第一版