快速树形控件TreeView

深度学习才能真正掌握工作经验，本文就是数据结构和UI结合深度学习的例子，里面的字典类Dictionary类的应用非常经典，翻译自codeproject。

介绍

将项目加载到 Windows Forms standardTreeView时，您会发现加载很多项目会花费大量时间！这个简单的扩展将使加载速度快如闪电。

在这个简单的演示应用程序中，我使用了自己的TreeViewFast控件并将其与标准TreeView. 如您所见，差异很大。

背景

在我的项目中，我需要一次加载约 100 000 个项目。使用TreeView控件时，当我发现花了我40-50分钟时，我有点沮丧....

我的第一次尝试是使用 SQL Server 2008 重新组织项目HierarchyId。这在很多方面都很有趣，也很有用，但对我来说，影响不大。我们有一个典型的“邻接”表列表，其中每个项目都存储在一个可能引用 a 的表中parentId。

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

我知道有许多不错的控件可以购买，它们具有许多不错的功能。但我只是想证明这种情况，如果您需要的只是更好的性能，那么对现有的简单扩展TreeView实际上就可以了。

注：作者的要求，在不扩展底层情况下实现不了，所以要扩展。

标准方法

我首先生成大量演示项目。在这种情况下，它们是employee具有连续Id属性和随机生成的名称组合的 s。每个employee都和一个经理对应，对应通过可选的ManagerId实现。如果设置为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 个项目需要 3 427 380 毫秒才能加载到 standardTreeView中。相当于57分钟！在中TreeViewFast，它需要 1 467 毫秒，即 1.4 秒。
我跳过了尝试将 1 000 000 个项目加载到正常TreeView....

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

优化方法

我决定使用标准TreeView，但只是稍微扩展一下。所以我创建了一个TreeViewFast继承自TreeView. 主要技巧是创建一个内部Dictionary存储所有节点。这样一来，所有的父查找总是很快的，即使对于大型集合也是如此。

我决定将intitemId和int?for用作数据类型parentId。这可能会受到质疑，但在大多数情况下，我认为它会适合现有的数据结构。我尝试使用string但发现它会使时间慢 10%。如果需要string或guid，只需要修改代码就很简单了。

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

如您所见，我决定将TreeNode项目存储在Dictionary. 这样使用起来会很方便。对象将item存储在TreeNode通用Tag属性中。这样，我们就可以随时轻松访问项目对象。

理想情况下，我们希望有一个控件类的通用构造函数。就像是：

public class TreeViewFast<T> : TreeView

这将使在课堂上随处引用该类型变得非常容易。但不幸的是，Windows 窗体设计器无法处理具有通用构造函数的控件。

更好的主意是使用实现通用接口的类型，例如ITreeViewFastItem.
但这将迫使所有实体都可以访问该接口。在我的设置中，实体是在项目中定义的，这些项目不能依赖于我在其中定义所有控件的 Windows 窗体项目。

所以在我的例子中，我决定允许每个方法都有一个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。当您需要搜索内部项集合或查找特定项的子项时，它们很有用。

得到教训

进行详细的性能测量以找到关键瓶颈总是很有用的！
只要小心处理，大数据集本身不是问题。
我喜欢字典。他们似乎一次又一次地拯救我。

友情链接