Блог

У меня есть проблема, когда мне нужно удалить все объекты дерева из списка.

У меня есть a 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 #) для доступа к тегам.

Мне интересно узнать о процессе загрузки дочерних устройств из базы данных. Поскольку вы выполняете итерацию по всему дереву, вы можете загружать в память фрагменты более подходящего размера. Поиск по ширине может загрузить большую часть дерева в память перед началом удаления узлов из очереди (если дерево очень широкое).

Было бы неплохо настроить или профилировать ваш код, чтобы выяснить, куда идет большая часть времени. Более ранний комментарий и ответ о «загрузке запроса в базу данных» (т. Е. childDevices = device.ChildDevices.ToList(); ), требующий времени, могут быть правильными, но, возможно, вместо этого это может быть
tags.Remove(device.Tag); это пустая трата времени. A .Remove() выполняется для каждого элемента, поставленного в очередь. Удаление требует O(n) времени: «Этот метод выполняет линейный поиск; следовательно, этот метод представляет собой операцию O (n), где n — количество». [MSDN]

То есть предположим, что вы ставите в очередь m элементы устройства, многие из которых имеют .Тега нет в вашем tags списке с n записями. .Удаление затрагивает каждый элемент tags , когда он ищет .Тега нет в списке; и в среднем он просматривает n/2 записи, чтобы найти .Тег, который находится в списке, так что общая работа есть O(m*n) . Напротив, работа в приведенном ниже методе O(m n) , который обычно будет в сотни раз меньше.

Чтобы обойти проблему:

1. Предварительная tags обработка списка путем создания соответствующей ему хэш-таблицы H
2. Для каждого устройства.Тег, проверьте, находится ли его хэш-значение в H
3. Если значение указано в H, добавьте устройство.Тег в словарь D
4. После обработки всего устройства.Теги для каждого элемента T tags списка, если T находится в общем выводе 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);
  

вам не нужно преобразовывать устройство.Дочерние устройства в список, потому что он уже перечислим. когда вы преобразуете это в list, оно будет нетерпеливым, которое перечисляется, оно будет ленивым.

Попробуйте это.