Алгоритм удаления всех объектов дерева из списка

Question

У меня проблема с удалением всех объектов дерева из списка.

У меня есть 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 секунд, что слишком долго.

Я пытался изменить список тегов на хэш-набор, но это приводит к незначительным улучшениям скорости.

Любые идеи алгоритма / изменения, которые яможно использовать, чтобы сделать это быстрее?

Answer 1

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

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

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

1. Предварительная обработка tags Список путем создания соответствующей ему хэш-таблицы H
2. Для каждого устройства. Отметьте, если его значение хеш-функции указано в H
3. Если значение в H, добавить device.Tag в словарь D
4. После обработки всех device.Tag, для каждого элемента T из списка tags, если T находится в D-выходе T, иначе подавить T

Answer 2

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

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

Answer 3

Вы можете использовать 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);

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

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

Answer 4

Я собираюсь догадаться, что ваше дерево довольно "толстое". То есть каждый из ваших узлов имеет МНОГИХ детей, но у вас мало слоев. Если это так, попробуйте Depth First Search . Вы должны быстро достичь дна и затем начать удаление узлов. Вам по-прежнему необходимо посещать все узлы, но вам не нужно будет хранить столько промежуточных данных, сколько в BFS.