从列表中删除树的所有对象的算法

本文关键字：对象 算法 列表 删除 | 更新日期: 2023-09-27 18:13:34

我有一个问题，我需要从列表中删除树的所有对象。

我有一个List<String> Tags，它包含了我的整个系统中与某个标准匹配的标签(通常从某个搜索字符串开始)。我还有一个根Device对象。Device类说明如下:

public class Device
{
    public int ID;
    public String Tag;
    public EntityCollection<Device> ChildDevices;
}

我所做的尝试是使用广度优先搜索，并在访问每个节点时从列表中删除标记，然后返回剩余的内容:

private List<String> RemoveInvalidTags(Device root, List<String> tags)    
{
    var queue = new Queue<Device>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var device = queue.Dequeue();
        //load all the child devices of this device from DB
        var childDevices = device.ChildDevices.ToList();
        foreach (var hierarchyItem in childDevices)
            queue.Enqueue(hierarchyItem.ChildDevice);
        tags.Remove(device.Tag);
    }
    return tags;
}

此刻，我正在访问2000+设备节点，并从大约1400个标签的列表中删除(由于搜索字符串减少)。这需要大约4秒，这太长了。

我已经尝试将标签列表更改为哈希集，但它带来的速度改进微不足道。

有什么算法/改变的想法，我可以用它来使这个更快吗?

从列表中删除树的所有对象的算法

我猜你的树相当"胖"。也就是说，你的每个节点都有很多子节点，但是你没有很多层。如果是这种情况，请尝试深度优先搜索。您应该快速到达底部，然后能够开始移除节点。您仍然需要访问所有节点，但您不必像在BFS中那样存储那么多的中间数据。

你绝对应该使用某种哈希表(对不起，不熟悉c#的细节)来访问标签。

我很好奇从DB加载子设备的过程。由于要遍历整个树，因此可以将大小更合适的块加载到内存中。宽度优先搜索可能会在开始从队列中删除节点之前(如果树非常宽)将树的大部分加载到内存中。

对您的代码进行检测或分析，以找出大部分时间的去向，这将是一个好主意。关于"向数据库加载查询"(，即: childDevices = device.ChildDevices.ToList();)占用时间可能是正确的，但似乎有可能是
那是在浪费时间。对每个队列项执行. remove()。Remove占用O(n)时间:"这个方法执行线性搜索;因此，该方法是一个O(n)操作，其中n为Count。(MSDN)

也就是说，假设您排队m设备项，其中许多具有n条目的。tag不在tags列表中。remove在查找不在列表中的。tag时触摸tags的每个元素;平均而言，它会查看n/2条目以找到列表中的. tag，因此总工作量为O(m*n)。相比之下，下面方法中的工作是O(m + n)，它通常会小数百倍。

回避问题:

  1. 通过创建与tags列表对应的哈希表H来预处理CC_14列表
  2. 每个设备。标记，测试其哈希值是否在H
    3. 中
  3. 如果值为H，则添加设备。标记到字典D
  4. 处理完所有设备后。标签s，对于tags列表中的每个元素T，如果T在D输出T中，否则抑制T

您可以使用Stopwatch来查找瓶颈，如果您问我

var childDevices = device.ChildDevices.ToList();
foreach (var hierarchyItem in childDevices)
   queue.Enqueue(hierarchyItem.ChildDevice);

那是你的瓶颈。

看看c#中的树实现，我希望你已经知道了树遍历。

你为什么不试试这个?

foreach (var hierarchyItem in device.ChildDevices)
   queue.Enqueue(hierarchyItem.ChildDevice);

你不需要转换设备。ChildDevices列表，因为它已经是可枚举的。当你将它转换为list时，它将是eager，而enumerable将是lazy

试试。

相关文章：