суббота, 3 апреля 2010 г.

LINQ-ом по деревьям

Сегодня покажу универсальный код обхода любых деревьев с однотипными узлами.
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. Отличия:
  1. В качестве первого аргумента принимается один элемент (корень дерева), а не последовательность.
  2. Метод рекурсивно применяется ко всем элементам, полученным с помощью делегата 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.


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

9 комментариев:

  1. А где бы на русском почитать хорошее объяснение проблемы производительности вложенных итераторов (или их цепочек)?

    ОтветитьУдалить
  2. Где почитать не подскажу. Да и проблемы-то собственно нет. Если речь об использовании LINQ-а, то бояться цепочек вложенных итераторов не нужно, больших проблем с производительностью это обычно не вызывает, т.к. глубина вложенности LINQ запросов обычно не превышает 10-15. В отношении именно представленной реализации обхода деревьев я сделал акцент на вложенных итераторах только потому что глубина их вложенности будет пропорциональна глубине дерева. Не упомянуть об этом я просто не мог. Другие реализации могут быть лишены этого недостатка, но они будут менее лаконичны чем представленная мной.

    Если интересно, я могу найти время для более шустрой реализации и возможно даже для бенчмарка.

    ОтветитьУдалить
  3. Кстати, можно заменить "from rootNode in treeVew1.Nodes.Cast()" на "from TreeNode rootNode in treeVew1.Nodes" ;)

    ОтветитьУдалить
  4. По поводу вложенных итераторов можно почитать эту тему на rsdn: http://rsdn.ru/forum/dotnet/3713743.flat.aspx, там я приводил несколько ссылок на англоязычные посты, обсуждающие проблему вложенных итераторов.

    ОтветитьУдалить
  5. Пельмешко>Кстати, можно заменить "from rootNode in treeVew1.Nodes.Cast()" на "from TreeNode rootNode in treeVew1.Nodes" ;)

    Приятно увидеть в читателях своего блога знатока спецификации компилятора! Спасибо за подсказку.

    ОтветитьУдалить
  6. Пельмешко>По поводу вложенных итераторов можно почитать эту тему на rsdn

    Эта тема как-то обошла мое внимание.

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

    Жаль, ссылка на pdf не доступна :(

    ОтветитьУдалить
  7. Alexey>Жаль, ссылка на pdf не доступна :(
    Нашел по этому адресу
    http://research.microsoft.com/en-us/projects/specsharp/iterators.pdf

    ОтветитьУдалить
  8. Alexey>Приятно увидеть в читателях своего блога знатока спецификации компилятора!

    Это, видимо, шутка :)))))

    На самом деле давно Вас читаю, актуально и понятно пишите. Было бы очень интересно увидеть нерекурсивную реализацию и конечно-же сравнение производительности.

    Спасибо за пост :)

    ОтветитьУдалить
  9. Пельмешко>Это, видимо, шутка :)))))
    Нет, это наблюдение ;)

    Пельмешко>На самом деле давно Вас читаю, актуально и понятно пишите. Было бы очень интересно увидеть нерекурсивную реализацию и конечно-же сравнение производительности.
    Рад что интересно.
    Нерекурсивная реализация в лоб оказалась довольно тривиальна. Неожиданность получилась с бенчмарком. На размерах деревьев до 20*10^6 элементов (не глубина) графики и рекурсивной и нерекурсивной версии линейны и отличаются лишь наклоном. На неделе постараюсь получить бенчмарки с глубинами деревьев, аки у Wes Dyer-а, и выложу в новом посте.

    З.Ы. Предлагаю перейти на "ты"

    ОтветитьУдалить