public static class TreeWalker { public static IEnumerable<T> Walk<T>(T root, Func<T, IEnumerable<T>> next) { var q = next(root).SelectMany(n => Walk(n, next)); return Enumerable.Repeat(root, 1).Concat(q); } }
За исключением нескольких отличий, этот метод похож на Enumerable.SelectMany. Отличия:
- В качестве первого аргумента принимается один элемент (корень дерева), а не последовательность.
- Метод рекурсивно применяется ко всем элементам, полученным с помощью делегата next из исходного.
Области применения
Для начала прогуляемся по дереву каталогов файловой системы:
foreach(var dir in TreeWalker.Walk(@"d:\Test", Directory.GetDirectories)) { Console.WriteLine(dir); }
Однако, гулять – не главный бенефит этого метода. Главный – “выпрямлять” деревья для того чтобы по ним можно было гулять LINQ-ом.
Еще один пример - собрать только листовые узлы у TreeView можно такой конструкцией
var q = from rootNode in treeVew1.Nodes.Cast<TreeNode>() from node in TreeWalker.Walk(rootNode, n => n.Nodes.Cast<TreeNode>()) where node.Nodes.Count == 0 select node;
Совсем не обязательно обходить дерево целиком. Например, при работе с двоичными деревьями поиска, с помощью метода Walk можно находить минимальный, максимальный элемент и даже делать поиск конкретного элемента за время соразмерное высоте дерева (при сбалансированном дереве – O(log N)).
Пусть у нас есть дерево из узлов следующего вида:
public class Node<T> { public Node(T value, Node<T> left, Node<T> right) { Value = value; Left = left; Right = right; } public T Value { get; private set; } public Node<T> Left { get; private set; } public Node<T> Right { get; private set; } }
Тогда для поиска минимального элемента потребуется следующий вспомогательный метод:
public static IEnumerable<Node<T>> NextLeft<T>(this Node<T> root) { if (root.Left != null) yield return root.Left; }
Тогда найти узел с минимальным элементом двоичного дерева можно следующей конструкцией:
TreeWalker.Walk(root, r => r.NextLeft()).Last();
Для поиска узла с конкретным элементом потребуется более хитрая вспомогательная функция, которая будет возвращать подузлы Left или Right в зависимости от результата сравнения значения текущего узла с искомым значением.
А если к функции получения дочерних узлов добавить маркировку пройденных узлов, то из метода Walk получится алгоритм “поиск в глубину” для графов.
Особенности реализации
Вместо Enumerable.Repeat(root, 1) можно было сделать new [] { root}, но я хотел сделать акцент на другом.
Как можно заметить, метод Walk ленив. Притом что его можно считать рекурсивным (он использует себя в определении своего тела), он не вызывает себя рекурсивно при обращении, а возвращает управление сразу же, возвращая перечислитель. Однако, агрессивное использование стека при работе метода никуда не делось, более того, оно более агрессивно, по сравнению с обычным рекурсивным методом. Все дело в том, что при погружении в дерево выстраиваются в цепочку активные перечислители на манер вложенных декораторов, длина цепочки которых пропорционален глубине погружения в дерево.
next(root).SelectMany добавляет в цепочку свои перечислители (полагаю что больше одного, лениво лезть в рефлектор). Над ним надстраивается Сoncat перечислитель.
Даже если дерево состоит только лишь из одного корневого элемента, вызовы IEnumerator<T>.MoveNext(), IEnumerator<T>.Current будут выполнены каскадно через 2-3 (а может и больше) перечислителей.
Итого, обход дерева высотой в несколько сот тысяч элементов с хорошей вероятностью может завершиться StackOverflowException (udated: 12000 элементов достаточно)… Даже если не завершится, цена вызова по цепочке перечислителей длиной в несколько глубин дерева может серьезно сказаться на производительности приложения. Ведь для получения очередного элемента нужно сделать два таких сверхглубоких вызова (MoveNext и Current).
Естественно, ситуацию можно изменить за счет переписывания метода Walk с какой-нибудь структурой данных, эмулирующей стек вызовов (например, Stack<T>). Но я пока в этом необходимости не испытываю. StackOverflowException я видел только на тестовых данных (двоичное дерево из миллиона элементов). А на тех данных, с которыми приходилось работать методу Walk, проблем с производительностью или с переполнением стека нет. Даже не было повода замеров производительности метода Walk с целью выявить зависимость времени выполнения от глубины дерева.
Если кому-то вопрос производительности и/или нерекурсивный вариант Walk метода окажется интересным, дайте знать в комментариях. А пока будем считать что я поделился красивым но не очень быстрым способом обхода деревьев с помощью LINQ-а.
P.S.
На авторство не претендую, аналогичный подходы к обходу деревьев я определенно встречал, единственное что я сделал – обобщил его, представил и предостерег от использования с деревьями больших глубин.
А где бы на русском почитать хорошее объяснение проблемы производительности вложенных итераторов (или их цепочек)?
ОтветитьУдалитьГде почитать не подскажу. Да и проблемы-то собственно нет. Если речь об использовании LINQ-а, то бояться цепочек вложенных итераторов не нужно, больших проблем с производительностью это обычно не вызывает, т.к. глубина вложенности LINQ запросов обычно не превышает 10-15. В отношении именно представленной реализации обхода деревьев я сделал акцент на вложенных итераторах только потому что глубина их вложенности будет пропорциональна глубине дерева. Не упомянуть об этом я просто не мог. Другие реализации могут быть лишены этого недостатка, но они будут менее лаконичны чем представленная мной.
ОтветитьУдалитьЕсли интересно, я могу найти время для более шустрой реализации и возможно даже для бенчмарка.
Кстати, можно заменить "from rootNode in treeVew1.Nodes.Cast()" на "from TreeNode rootNode in treeVew1.Nodes" ;)
ОтветитьУдалитьПо поводу вложенных итераторов можно почитать эту тему на rsdn: http://rsdn.ru/forum/dotnet/3713743.flat.aspx, там я приводил несколько ссылок на англоязычные посты, обсуждающие проблему вложенных итераторов.
ОтветитьУдалитьПельмешко>Кстати, можно заменить "from rootNode in treeVew1.Nodes.Cast()" на "from TreeNode rootNode in treeVew1.Nodes" ;)
ОтветитьУдалитьПриятно увидеть в читателях своего блога знатока спецификации компилятора! Спасибо за подсказку.
Пельмешко>По поводу вложенных итераторов можно почитать эту тему на rsdn
ОтветитьУдалитьЭта тема как-то обошла мое внимание.
Пельмешко>там я приводил несколько ссылок на англоязычные посты, обсуждающие проблему вложенных итераторов.
Жаль, ссылка на pdf не доступна :(
Alexey>Жаль, ссылка на pdf не доступна :(
ОтветитьУдалитьНашел по этому адресу
http://research.microsoft.com/en-us/projects/specsharp/iterators.pdf
Alexey>Приятно увидеть в читателях своего блога знатока спецификации компилятора!
ОтветитьУдалитьЭто, видимо, шутка :)))))
На самом деле давно Вас читаю, актуально и понятно пишите. Было бы очень интересно увидеть нерекурсивную реализацию и конечно-же сравнение производительности.
Спасибо за пост :)
Пельмешко>Это, видимо, шутка :)))))
ОтветитьУдалитьНет, это наблюдение ;)
Пельмешко>На самом деле давно Вас читаю, актуально и понятно пишите. Было бы очень интересно увидеть нерекурсивную реализацию и конечно-же сравнение производительности.
Рад что интересно.
Нерекурсивная реализация в лоб оказалась довольно тривиальна. Неожиданность получилась с бенчмарком. На размерах деревьев до 20*10^6 элементов (не глубина) графики и рекурсивной и нерекурсивной версии линейны и отличаются лишь наклоном. На неделе постараюсь получить бенчмарки с глубинами деревьев, аки у Wes Dyer-а, и выложу в новом посте.
З.Ы. Предлагаю перейти на "ты"