Рекурсивный поиск по коллекции

У меня есть коллекция (List<Element>) объектов, как описано ниже:

class Element
{
  string Name;
  string Value;
  ICollection<Element> ChildCollection;
  IDictionary<string, string> Attributes;
}

Я создаю List<Element> коллекцию из Element объектов на основе некоторого XML, который я прочитал, и я вполне доволен этим. Как реализовать поиск этих элементов в настоящее время, я не в тупике, но задаюсь вопросом, есть ли лучшее решение.

Структура коллекции выглядит примерно так:

- Element (A)
  - Element (A1)
    - Element (A1.1)
  - Element (A2)
- Element (B)
  - Element (B1)
    - Element (B1.1)
    - Element (B1.2)
- Element (C)
  - Element (C1)
  - Element (C2)
  - Element (C3)

В настоящее время я использую рекурсию для поиска в Attributes словаре каждого верхнего уровня (A, B, C) Element определенного KeyValuePair. Если я не нахожу его на верхнем уровне Element, я таким же образом начинаю искать его ChildElement коллекцию (1, 1.1, 2, 2.1, n и т. д.).

Что мне интересно, так это то, есть ли лучший метод реализации поиска по этим объектам или рекурсия является лучшим ответом в этом случае, если я должен реализовать поиск, как сейчас, top -> child -> child -> и т. д. или мне следует искать каким-то другим способом, например, сначала все верхние уровни?

Могу ли я и будет ли разумно использовать TPL для параллельного поиска на каждом верхнем уровне (A, B, C)?


search c# recursion task-parallel-library icollection
person Peppermintology    schedule 13.07.2013    source источник
comment
Что вы ищете?   -  person Sayse    schedule 13.07.2013

Ответы (3)


arrow_upward
1
arrow_downward

Рекурсия — это один из способов реализации поиска по дереву, когда вы посещаете элементы в порядке глубины. Вы можете реализовать тот же алгоритм с циклом вместо рекурсии, используя структуру данных стека для хранения узлов вашего дерева, которые вам нужно посетить.

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

В обоих случаях общий алгоритм выглядит так:

var nodes = ... // some collection of nodes
nodes.Add(root);
while (nodes.Count != 0) {
    var current = nodes.Remove ... // Take the current node from the collection.
    foreach (var child in current.ChildCollection) {
        nodes.Add(child);
    }
    // Process the current node
    if (current.Attributes ...) {
        ...
    }
}

Обратите внимание, что алгоритм не является рекурсивным: он использует явный набор nodes для сохранения текущего состояния поиска, тогда как рекурсивная реализация использует стек вызовов для той же цели. Если nodes равно Stack<Element>, поиск продолжается в в порядке поиска в глубину; если nodes равно Queue<Element>, поиск выполняется в в ширину.

person Sergey Kalinichenko    schedule 13.07.2013
comment
Это заставило меня двигаться в том направлении, в котором я надеялся. Хорошо объяснил ответ, так что спасибо. - person Peppermintology; 15.07.2013

arrow_upward
0
arrow_downward

Я взял этот бит из SO где-то, он не мой, но я не могу дать ссылку на него. Этот класс сглаживает древовидную структуру для рекурсивного поиска, похоже, он должен делать то же самое для вас.

public static class SOExtension
{
    public static IEnumerable<TreeNode> FlattenTree(this TreeView tv)
    {
        return FlattenTree(tv.Nodes);
    }

    public static IEnumerable<TreeNode> FlattenTree(this TreeNodeCollection coll)
    {
        return coll.Cast<TreeNode>()
                    .Concat(coll.Cast<TreeNode>()
                                .SelectMany(x => FlattenTree(x.Nodes)));
    }
}

Я нашел ссылку, по которой я получил это, - ее очень легко использовать. взглянуть. Есть ли способ для поиска поля TreeNode.Text в коллекции TreeView.Nodes?

person John Faulkner    schedule 13.07.2013

arrow_upward
0
arrow_downward

Вы можете повторно использовать существующие компоненты, разработанные специально для обхода, различными способами, например Метод расширения NETFx IEnumerable.Traverse. Это позволяет вам в глубину или в ширину в первую очередь. Он позволяет вам пройти по перечислимому дереву, сначала в глубину или в ширину.

Пример получения сглаженного перечисления каталогов:

IEnumerable<DirectoryInfo> directories = ... ;

IEnumerable<DirectoryInfo> allDirsFlattened = directories.Traverse(TraverseKind.BreadthFirst, dir => dir.EnumerateDirectories());

foreach (DirectoryInfo directoryInfo in allDirsFlattened)
{
    ...
}

Для BreadhFirst используется Queue‹T>. внутренне и для DepthFirst он использует Stack‹T>внутренне.

Это не параллельный обход узлов, и если обход не требует ресурсов, использование параллелизма на этом уровне нецелесообразно. Но это зависит от контекста.

person lightbricko    schedule 13.07.2013