Эффективный поиск всех узлов в древовидной структуре

Question

Я работаю со структурой древовидного типа, которая состоит из одной записи root'TreeNodeDefinition, которая может содержать, помимо прочего, список других классов TreeNodeDefinition, каждый из которых может содержать дополнительный список и т. Д. И т. Д.

В основном я хочу иметь возможность проходить ВСЕ узлы в древовидной структуре и проверять, выполняется ли условие для каждого узла, тогда эта запись определения добавляется в список.Я придумал способ сделать это, но не могу помочь, но думаю, что есть гораздо более эффективный способ сделать это:

List<ITreeNodeDefinition> treeNodeDefinitions = new List<ITreeNodeDefinition>();

treeNodeDefinitions = treeFactory.SearchNodesByRelationshipId(treeNodeDefinition, relationshipId, new List<ITreeNodeDefinition>());

, где первый параметр - это моя запись определения корневого узла, второй параметрэто то, что мне нужно для сравнения каждого узла, и, наконец, я передаю пустой список, который я хочу заполнить каждый раз, когда узел соответствует моей проверке.Метод выглядит следующим образом:

    public List<ITreeNodeDefinition> SearchNodesByRelationshipId(ITreeNodeDefinition treeNodeDefinition, int? relationshipId, List<ITreeNodeDefinition> tndList)
    {
        if (treeNodeDefinition.RelationshipId == relationshipId)
        {
            tndList.Add(treeNodeDefinition);
        }

        if (treeNodeDefinition.Nodes.Count != 0)
        {
            foreach (ITreeNodeDefinition nodeDefinition in treeNodeDefinition.Nodes)
            {
                List<ITreeNodeDefinition> tempTable = this.SearchNodesByRelationshipId(nodeDefinition, relationshipId, tndList);
            }
        }
        return tndList;
    }

Как видите, метод вызывает сам себя для каждого подузла, найденного в списке treeNodeDefinition.Nodes.Это возвращение к искушению, с которым я никогда ничего не делаю ... Это воняет мне неэффективностью.мне было интересно, есть ли более прямой способ навигации по такого рода структурам ... я уверен, что мне не хватает хитрости.

Answer 1

Глядя на вопрос / код, я думаю, что проблема связана не с одной вещью (как вы сказали избыточная переменная tempTable), а с несколькими областями, я попытаюсь выделить эти области / проблемы.

1) Теория. Первое, что вам нужно знать перед итерацией дерева, - это 2 способа итерации деревьев: " в ширину * " и " в глубину"».Они могут быть реализованы через ' recursion ' и ' loop '.Об этом много статей.

Предлагаю вам прочитать несколько статей об этих подходах, некоторые из них:

• Рекурсия против циклов
• https://github.com/tinkerpop/gremlin/wiki/Depth-First-vs.-Breadth-First

2) Проблема, которую вы заметили из производительности pov незначительна.Да, вы правы, когда говорите, что сохранение результата предыдущего вызова в 'tempTable' не очень хорошо.Возвращение «tempTable» не оказывает большого влияния на производительность или память, поскольку « tempTamble » ссылается на тот же объект, что и « tndList ».Возвращаемый параметр метода не дает « неэффективность ».Единственное, на что он влияет - не чистый код и несколько байтов в стеке.На самом деле вам не нужно ничего возвращать в вашем методе.Почему вы возвращаете список?

Предлагаю прочитать о значении и ссылочных типах .Некоторые материалы

• https://docs.microsoft.com/en-us/dotnet/csharp/language-reference/keywords/reference-types
• https://www.infoworld.com/article/3043992/application-development/a-deep-dive-value-and-reference-types-in-net.html

Я немного изменил ваш код, теперь он возвращает void :

public void SearchNodesByRelationshipId(ITreeNodeDefinition treeNodeDefinition, int? relationshipId, List<ITreeNodeDefinition> tndList)
{
    if (treeNodeDefinition.RelationshipId == relationshipId)
    {
        tndList.Add(treeNodeDefinition);
    }

    if (treeNodeDefinition.Nodes.Count != 0)
    {
        foreach (ITreeNodeDefinition nodeDefinition in treeNodeDefinition.Nodes)
        {
            this.SearchNodesByRelationshipId(nodeDefinition, relationshipId, tndList);
        }
    }
}

3) Еще одна проблема.Существенно. То, как вы выполняете итерации - это рекурсия ' глубина-первая '.Этот подход не является надежным, потенциально он приводит к «StackOverflowException».Из-за длинной цепочки рекурсивных вызовов методов.

Я предлагаю вам прочитать об алгоритмах итерации и рекурсии в контексте деревьев и реализовать подход итерации .

Только для информации: есть еще один способ избежать 'stackOverfrwException' с помощью подхода recursion - tail recursion , но, на самом деле, такого механизма нет в C#, но такой механизм существует в F# и других функциональных языках.

Вкратце, как работает итеративный подход, в псевдокоде:

put the root to the collection X (which is queue for '*breadth-first*' and stack for '*depth-first*')
Do while X is not empty
    var currentNode = get next node from X
    process current root (do checks that you need, aggregate data etc.)
    get child nodes of the currentNode, save them into X

• https://www.quora.com/Is-recursion-faster-than-loops

• Путь от рекурсии к итерации

Answer 2

Вы можете подойти к этому с явным стеком и вообще избежать рекурсии:

public static IEnumerable<ITreeNodeDefinition> DepthFirstSearch(ITreeNodeDefinition root, int? relationshipId)
{
    var stack = new Stack<ITreeNodeDefinition>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        if (current.RelationshipId == relationshipId)
            yield return current;

        foreach(var node in current.Nodes)
            stack.Push(node);
    }
}

Чтобы добавить к этому, возможно, будет проще и гибче вообще не жестко кодировать в проверке идентификатора взаимосвязи и просто отфильтровывать результаты впоследствии, если вы обнаружите, что вы обычно пытаетесь пройти по древовидной структуре:

var matches = treeFactory.Traverse(root)
                         .Where(t => t.RelationshipId == 5)
                         .ToList();

Более того, используя предикат поиска, вы можете встроить эту функцию поиска в метод так же, как это делает LINQ, который вы можете реализовать следующим образом:

public static IEnumerable<ITreeNodeDefinition> DepthFirstSearch(ITreeNodeDefinition root, Func<ITreeNodeDefinition, bool> predicate)
{
    var stack = new Stack<ITreeNodeDefinition>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if (predicate(current))
            yield return current;

        foreach (var node in current.Nodes)
            stack.Push(node);
    }
}

Преимущество заключается в том, что вы не жестко программируете в одном конкретном случае поиска при обходе. Вызов этого с поиском RelationshipId будет:

var matches = treeFactory.DepthFirstSearch(root, t => t.RelationshipId == 5)
                         .ToList();

Для полноты вот пример поиска в ширину. Обратите внимание на разницу в Queue<T> против Stack<T> в том, как изменяется порядок обхода:

public static IEnumerable<ITreeNodeDefinition> BreadthFirstSearch(ITreeNodeDefinition root, Func<ITreeNodeDefinition, bool> predicate)
{
    var queue = new Queue<ITreeNodeDefinition>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        if (predicate(current))
            yield return current;

        foreach (var node in current.Nodes)
            queue.Enqueue(node);
    }
}

В вашем случае использования, вероятно, нет никакого преимущества ни для одного из них, за исключением того, что порядок в ширину упорядочивается таким образом, который обычно лучше при перечислении узлов.