пятница, 30 апреля 2010 г.

Visitor revisited

Сегодня я покажу свое видение паттерна Visitor. У меня складывается впечатление о том что в значительном количестве источников он представлен не самым удачным образом.

Рассмотрим пример из википедии. К сожалению, это типичный такой примерчик посетителя не без недостатков. Я бы даже сказал с ошибками.
Первая и не самая серьезная ошибка примера – то что вложенные элементы Car хранятся в массиве и паттерн Visitor – не лучший способ для перебора этих элементов. Куда проще и нагляднее было бы прикрутить паттерн Composite.
Вторая ошибка серьезнее – обход структуры заложен в методах accept. Я не считаю метод accept подходящим местом для расположения логики обхода структуры.
Я обозначил их для того, чтобы пробегая дальше по определениям сосредотачивать внимание именно на этом аспекте.

Вернемся к началу статьи в Wikipedia:
In object-oriented programming and software engineering, the visitor design pattern is a way of separating an algorithm from an object structure it operates on. A practical result of this separation is the ability to add new operations to existing object structures without modifying those structures.
Т.е. нам обещают что операции можно прикручивать на существующую структуру. Однако пример демонстрирует что мы не можем прикрутить обход извне. Более того, расположенная логика обхода в методе accept мешает выполнять другие операции над одиночными элементами структуры. Будучи примененный к Car посетитель CarElementPrintVisitor неизбежно выведет в консоль имена всех элементов машины, хотим мы этого или нет. Любая новая операция обречена выполняться над всей структурой. И об этом ничего не сказано в “определении”. В определении вообще ни слова про обход структуры, но как видно из примера, ничего кроме обхода паттерн делать не умеет. Но зато умеет их делать по-разному.

GoF
Назначение
Описывает операцию, выполняемую с каждым объектом из некоторый структуры. Паттерн посетитель позволяет определить новую операцию, не изменяя классы этих объектов.
Опять ничего про обход в назначении паттерна. Зато об обходе написано далее:
Результаты
  • Упрощает добавление новых операций. …
  • Объединяет родственные операции и отсекает те, которые не имеют к ним отношения. …
  • добавление новых классов ConcreteElement затруднено …
  • Посещение различных иерархий классов.
Аж на 4-м месте в списке результатов применения после отрицательного результата.
И далее:
Реализация
….
Какой участник несет ответственность за обход структуры. Посетитель должен обойти каждый элемент структуры объектов. Вопрос в том, как туда попасть.
Вот как, должен? А как же операции, не связанные с обходом?
Ответственность за обход можно возложить на саму структуру объектов, на посетителя и на отдельный объект итератор.
На саму структуру объектов – мы уже видели как это делается и к чему приводит.
Другое решение – воспользоваться итератором для посещения элементов. … Поскольку внутренние итераторы реализуются самой структурой объектов, то работа с ними во многом напоминает предыдущее решение, когда за обход отвечает структура.
Ну а почему тогда не композит?
Можно даже поместить алгоритмы обхода в посетитель, хотя закончится это дублированием кода обхода в каждом классе ConcreteVisitor для каждого агрегата ConcreteElement. Основная причина такого решения – необходимость реализовать особо сложную стратегию обхода (?!?!?!?), зависящую от результатов операций над объектами структуры. Этот случай рассматривается в разделе “Пример Кода”.
Если честно, то я не понимаю, откуда дублирование. И в разделе “Пример Кода” обход реализован в методах accept.

Джошуа Кериевски (Рефакторинг с использованием шаблонов) считает что все знакомы с назначением паттерна и пишет просто:
Переместить задачу накопления в реализацию шаблона Visitor, который для накопления информации может посетить каждый класс.
Да и рассматривает он Visitor только лишь в аспекте Move Accumulation to Visitor.

Роберт К. Мартин (Быстрая разработка программ. Принципы, примеры, практика)
Семейство Visitor позволяет добавлять к существующим иерархиям новые методы без обновления этих иерархий.
Отлично, новые методы без обновления этих иерархий! Кстати, чуть ли не единственный случай, где пример Visitor-а не содержит обхода. СОВСЕМ НЕ СОДЕРЖИТ.

The Visitor pattern and multiple dispatch
Its purpose is to provide new operations on a class or set of related classes without actually altering the classes involved.
Пример тоже не содержит обхода.

Попытаемся осмыслить

Итак, все рассмотренные источники (кроме Д. Кериевски) утверждают что паттерн предназначен для обеспечения новых операций без изменений классов структуры объектов. Для меня это ключевая особенность паттерна. Вот почему:

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

Какие еще бывают зайцы кроме обхода?
  • Валидация объектов (существуют разные причины по которым валидацию следует рассматривать как внешнюю по отношению к объектам операцию)
  • Вызов метода сохранения объекта в БД, Log файл, рисование на специализированных устройствах
  • Размазывание объектов по View-шкам GUI и собирание информации с вьюшек обратно в объект (это только пример, совсем не значит что я так делаю)
  • Получение локализованного наименования объекта
В общем все то, что нужно делать специальным способом в зависимости от типа объекта, но что по каким-то причинам не следует вставлять в методы объекта(ов).

Пример: есть Order и Product, которые не знают своих имен, но их надо как-то назвать чтобы представить пользователю. Операция получения названия объекта – внешняя по отношению к Order-у. Все к тому, чтобы воспользоваться посетителем еще раз (если он уже есть). Но если в методе accept класса Order-а реализован обход, то получить название Order-а мы сможем только в случае когда у Order-а нет вложенных объектов.

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

Приведу исходный код примера из википедии, но на C# и значительно упрощенный так, чтобы в нем осталась лишь суть паттерна и ничего более:
interface ICarElementVisitor
{
    void Visit(Wheel wheel);
    void Visit(Engine engine);
}

interface ICarElement
{
    void Accept(ICarElementVisitor visitor);
}

class Wheel : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class Engine : ICarElement
{
    public void Accept(ICarElementVisitor visitor)
    {
        visitor.Visit(this);
    }
}

class CarElementPrintVisitor : ICarElementVisitor 
{
    public void Visit(Wheel wheel)
    {
        Console.WriteLine("wheel");
    }
    public void Visit(Engine engine)
    {
        Console.WriteLine("engine");
    }
}

class Test
{
    public static void TestVisitor()
    {
        var elements = new ICarElement[] {new Engine(), new Wheel()};
        var visitor = new CarElementPrintVisitor();
        foreach (var carElement in elements)
        {
            carElement.Accept(visitor);
        }
    }
} 
Выше приведена квинтэссенция классического посетителя, лишенная недостатков примера из википедии. Ну конечно, некоторой функциональности я его тоже лишил (ниже я ее восстановлю).

Что мне еще не нравится в этом коде?
Метод
void Visit(Wheel wheel);
не позволяет получить результат применения паттерна напрямую. Единственный способ что-то получить – накопить это что-то в конкретном классе посетителя, либо извне (например в глобальной переменной) и потом забрать значение. Было бы лучше, если бы визитор умел возвращать результат операции. Но опять-таки, если операции разные, то и типы результатов у них будут разные. Тип возвращаемого результата должен передаваться generic параметром интерфейса (а не метода!!! Важно, чтобы все методы Visit интерфейса посетителя меняли тип результата синхронно, а не по отдельности):
TResult Visit(Wheel wheel);

Отлично. Еще бы уметь передать дополнительный аргумент. Хотя это как раз лишнее. Аргумент можно передать непосредственно в класс посетителя.

Итак, интерфейс посетителя будет выглядеть так:
interface ICarElementVisitor<out TResult> 
{
    TResult Visit(Wheel wheel);
    TResult Visit(Engine engine);
    TResult Visit(Car car); 
}
А лучше чуть по-другому:
interface IVisitor<in TVisitable, out TResult>
{
    TResult Visit(TVisitable visitable);
}

interface ICarElementVisitor<out TResult> :
    IVisitor<Wheel, TResult>,
    IVisitor<Engine, TResult>,
    IVisitor<Car, TResult>
{
    //TResult Visit(Wheel visitable);
    //TResult Visit(Engine visitable);
    //TResult Visit(Car visitable);
}
Функционально разницы никакой, просто я побаиваюсь напутать что-то с сигнатурой одного из методов, а вынесение метода Visit в отдельный интерфейс позволяет исключить некоторые ошибки.
(+) ключевые слова in/out в объявлении интерфейса

Если кого-то смущают ключевые слова in и out в списке generic параметров интерфейса, то об этом можно почитать здесь. Для этой статьи они никакой роли не играют и должны быть удалены при использовании кода в версиях языка C# 2.0-3.0
(-) ключевые слова in/out

Интерфейс элемента напротив не должен зависеть от generic параметров, но метод Accept должен уметь работать с разными типами посетителей:
interface ICarElement
{
    TResult Accept<TResult>(ICarElementVisitor<TResult> visitor);
}

Вот собственно реализация конкретного элемента паттерна:
class Wheel : ICarElement
{
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}
Ничего кроме метода Accept! Все как и в стандартных примерах, только угловых скобочек побольше.

Дальше будет элемент посложнее. Помните, в определениях говорилось о том, что паттерн visitor можно применять к существующим структурам не модифицируя их? Покажу как это можно сделать не модифицируя элемент совсем (с помощью адаптера).
class Engine
{
}

class EngineAdapter : ICarElement
{
    public EngineAdapter(Engine engine)
    {
        Engine = engine;
    }
    public Engine Engine { get; private set; }

    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(Engine);
    }
}
Можно было интерфейс ICarElementVisitor замкнуть на EngineAdapter вместо Engine, если бы это играло какую-то роль.

Теперь составной элемент Car. Обратите внимание на то, что метод Accept не содержит логики обхода!
class Car : ICarElement
{
    public Wheel[] Wheels = Enumerable.Range(1, 4).Select(_ => new Wheel()).ToArray();
    public Engine Engine = new Engine();
        
    public TResult Accept<TResult>(ICarElementVisitor<TResult> visitor)
    {
        return visitor.Visit(this);
    }
}

Дальше код визитора, достающего имена объектов:
class GetNameVisitor : ICarElementVisitor<string>
{
    public string Visit(Wheel visitable)
    {
        return "wheel";
    }

    public string Visit(Engine visitable)
    {
        return "engine";
    }

    public string Visit(Car visitable)
    {
        return "car";
    }
}

Дальше чуть сложнее. Посетитель, который из элементов достает наборы вложенных элементов:
class GetChildrenVisitor : ICarElementVisitor<IEnumerable<ICarElement>>
{
    public IEnumerable<ICarElement> Visit(Wheel visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Engine visitable)
    {
        yield break;
    }

    public IEnumerable<ICarElement> Visit(Car visitable)
    {
        yield return new EngineAdapter(visitable.Engine);
        foreach (var wheel in visitable.Wheels)
        {
            yield return wheel;
        }
    }
}
Здесь следует обратить на метод посещения составного объекта Car. Проходя по engine элементу он возвращает не сам элемент, а адаптер.

Ну и в конце-концов метод, который демонстрирует поведение паттерна:
public static void TestVisitor()
{
    var childrenVisitor = new GetChildrenVisitor();
    var nameVisitor = new GetNameVisitor();

    ICarElement car = new Car();

    var elements = car.Walk(e => e.Accept(childrenVisitor));
    var elementNames = elements.Select(e => e.Accept(nameVisitor));

    foreach (var elementName in elementNames)
    {
        Console.WriteLine(elementName);
    }
}

static IEnumerable<T> Walk<T>(this T root, Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new[] { root }.Concat(q);
}
Во-первых создаются экземпляры посетителей и составного элемента Car. Далее с помощью метода Walk, представляющего дерево в виде одиночной последовательности и описанного в предыдущем посте, а так же посетителя GetChildrenVisitor, строится набор элементов. Затем набор элементов преобразовывается в набор имен с помощью GetNameVisitor и выводится в консоль циклом foreach.

Итог

Итак, я восстановил функциональность примера из википедии, но избежал недостатков. Перечислю еще раз достоинства такого подхода:
  • метод accept не содержит логики обхода (это достоинство само по себе, как и вытекающие из него следствия);
  • логика обхода содержится снаружи иерархии, и это позволяет менять ее не изменяя объектов иерархии;
  • внешний обход не мешает выполнению других операций, реализованных с помощью паттерна, и более того, позволяет комбинирование обхода с другими операциями;
  • посетитель, возвращающий результат, позволяет избавиться от накопления данных внутри объектов либо внутри самого посетителя и использовать мощь LINQ в обходе иерархии;
  • посетитель, возвращающий generic результат, позволяет удобно совмещать одним паттерном множество разнотипных операций.
Замечу так же, что никакого дублирования логики обхода в каждом классе ConcreteVisitor, как это было написано в GoF, не намечается.

Надеюсь, что моя статья позволит читателям использовать паттерн Visitor более эффективно.

З.Ы.
Респект тем кто дочитал до конца.

понедельник, 12 апреля 2010 г.

LINQ-ом по деревьям (часть 2)

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

Walk

С прошлого поста заменил Enumerable.Repeat(root, 1) на new [] {root}.
public static IEnumerable<T> Walk<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var q = next(root).SelectMany(n => Walk(n, next));
    return new []{root}.Concat(q);
}

Walk2

Слегка оптимизированная версия Walk, где методы SelectMany и Concat развернуты в конечный автомат yield return:
public static IEnumerable<T> Walk2<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    yield return root;
    foreach (var child in next(root))
    {
        foreach (var node in Walk2(child, next))
        {
            yield return node;
        }
    }
}
Эта версия Walk метода покажет нам ценность такого переписывания. Я не буду пропагандировать ни за ни против, просто предоставлю данные, а решать пусть будет каждый сам за себя, пользоваться ли высокоуровневыми методами, либо эквивалентными циклами.

WalkS

WalkS – обход с помощью структуры Stack<T>. Это самый простой способ преобразования callstack-а в структуру данных.
public static IEnumerable<T> WalkS<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current).Reverse())
        {
            stack.Push(x);
        }
    }
}
Здесь использован метод Enumerable.Reverse чисто для сохранения порядка обхода в соответствии с оригинальным методом Walk. Но гоняться в бенчмарке будет немного другой метод:

WalkS2

У этой модификации используется 2 стека (Stack<T>). Второй заменяет Enumerable.Reverse.
public static IEnumerable<T> WalkS2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var stack = new Stack<T>();
    var stack2 = new Stack<T>();
    stack.Push(root);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach (var x in next(current))
        {
            stack2.Push(x);
        }
        foreach (var x in stack2)
        {
            stack.Push(x);
        }
        stack2.Clear();
    }
}

WalkL

В очередной модификации вместо Stack<T> используется односвязный список.
class ListNode<T>
{
    public T Value { get; private set; }
    public ListNode<T> Next { get; private set; }

    public ListNode(T value, ListNode<T> next)
    {
        Value = value;
        Next = next;
    }
}
public static IEnumerable<T> WalkL<T>(
    this T root, 
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var current = list;
        list = list.Next;
        yield return current.Value;

        foreach (var x in next(current.Value).Reverse())
        {
            list = new ListNode<T>(x, list);
        }
    }
}
Но воевать будет не она, а та что использует 2 односвязных списка:

WalkL2

Последняя модификация, учавствующая в бенчмарке использует один список для замены callstack-а, другой вместо Enumerable.Reverse().
public static IEnumerable<T> WalkL2<T>(
    this T root,
    Func<T, IEnumerable<T>> next)
{
    var list = new ListNode<T>(root, null);
    while (list != null)
    {
        var currentNode = list;
        var nextNode = list.Next;
        yield return currentNode.Value;

        ListNode<T> tmpList = null;
        foreach (var v in next(currentNode.Value))
        {
            tmpList = new ListNode<T>(v, tmpList);
        }

        if(tmpList != null)
        {
            for (; tmpList != null; tmpList = tmpList.Next)
            {
                nextNode = new ListNode<T>(tmpList.Value, nextNode);
            }
        }
        list = nextNode;
    }
}

Depth

В бенчмарке учавствует еще один метод, который тоже обходит дерево, но при этом не пытается выпрямить его узлы в последовательность. Подсчет глубины конкретного двоичного дерева в чисто рекурсивной форме. Этот метод будет эталоном скорости.
Вслед за методом GetDepth привел класс узла дерева, на котором проходил бенчмарк.
public static int GetDepth<T>(this Node<T> node)
{
    return (node == null)
        ? 0
        : 1 + Math.Max(
            node.Left.GetDepth(),
            node.Right.GetDepth());
}

public class Node<T>
{
    public Node(T value, Node<T> left, Node<T> right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
    public T Value { get; set; }
    public Node<T> Left { get; set; }
    public Node<T> Right { get; set; }
}

Забег №1

Случайным образом перемешанный массив индексов [0..N] подается на вход алгоритму, строящему двоичное дерево (без балансировки). Полученное дерево скармливается вышеуказанным методам Walk* и у полученного IEnumerable<int> извлекается последний элемент Enumerable.Last ().
Результаты первого забега (по оси x кол-во элементов, по y – время обхода в секундах):

Следующим образом выглядит таблица времен обхода дерева из 10М элементов:
Метод обхода
Время
Walk
00:00:24.7759974
Walk2 00:00:10.8108170
WalkS2 00:00:03.5185059
WalkL2 00:00:02.7030328
Depth 00:00:01.0753161
Что-то здесь не так. Судя по графику, нерекурсивные методы значительно быстрее, но я не увидел зависимости графиков рекурсивных методов от глубины дерева… И деревья-то подсовывались не слишком глубокие. Глубина дерева из случайно перемешанного набора из 20М индексов не превышала 60. При таком подходе, увеличивая вдвое число элементов, мы будем получать увеличение глубины дерева лишь на единицу. Геометрическая, блин, прогрессия! Страшно подумать, сколько нужно элементов, для того чтобы достичь глубины 1000 :(
Но кое-какие выводы можно сделать и из этого забега:
  • Методы Walk и Walk2 идут ноздря в ноздрю и значительного перевеса не наблюдается, хотя и foreach-и немного опережают высокоуровневые методы SelectMany+Concat.
  • Нерекурсивные методы WalkS2 и WalkL2 достаточно близки к эталонному Depth
  • Односвязные списки немного шустрее чем Stack<T>.

Забег №2

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

Что интересно, рекурсивные методы Walk и Walk2 не осилили дерево глубиной 12000 и отвалились с StackOverflowException. Однако метод GetDepth работал стабильно (полагаю что JIT распознал хвостовую рекурсию и преобразовал рекурсию в цикл это не так, спасибо Пельмешко за внимательность. GetDepth-у для исключения нужно глубину 65000).


Этот эксперимент показывает нелинейную зависимость рекурсивных методов Walk и Walk2 от глубины дерева и совершенно ничего не показывает о нерекурсивных методах WalkS2, WalkL2 и рекурсивном но преобразованном в цикл методе GetDepth. Т.е. их зависимость от глубины на этом графике не видна. Время, которое показывали три последних метода на обходе 10000 элементов не превышало 0.001 секунды.

Итого:

Рекурсивная комбинация перечислителей представляет опасность переполнения стека на глубинах дерева от 10К. На глубинах дерева до 1000 рекурсивными перечислителями вполне можно пользоваться и их производительность хоть и уступает нерекурсивным методам,  но может быть вполне приемлема для множества задач.

P.S.

На RSDN Sinix-ом был приведен другой метод выпрямления рекурсивных комбинаций перечислителей. Нетрудно увидеть схожесть его метода с представленными мной. Отличия в сигнатуре (принимает коллекцию узлов), в порядке обхода (нет Reverse), да и в стек он помещает не узлы, а перечислители узлов. Не знаю, в чем фокус, но его метод работает примерно в 2 раза медленнее WalkS2, представленного мной (с Reverse-ом с помощью дополнительного стека). Ну и собственно название, UngroupRecurseEnumerator сбивает с толку. Это тот же самый обход дерева.

P.P.S.

В этой статье упоминается Range через yield foreach:
static IEnumerable<int> FromTo(int b, int e)
{
    if (b > e)
        yield break;
    yield return b;
    yield foreach FromTo(b + 1, e);
}
А вот и наш ответ Чемберлену
static IEnumerable<int> FromTo(int b, int e)
{
    return b.WalkL2(i =>
         (i < e)
            ? new int[] { i+1 } 
            : new int[] {});
}
Не столь красивый, но не требующий изменения языка.
А yield foreach все-таки сила!

Upd.

Я таки написал версию GetDepth с хвостовой рекурсией:
public static int GetDepthC<T>(this Node<T> node)
{
    return GetDepthCps(node, d => d);
}

static int GetDepthCps<T>(Node<T> node, Func<int, int> cont)
{
    return (node == null)
       ? cont(1)
       : GetDepthCps(node.Left, leftDepth =>
            GetDepthCps(node.Right, rightDepth =>
                cont(Math.Max(leftDepth, rightDepth))));
}
Естественно я не ожидал что C# ее выпрямит в цикл. А вот F# выпрямляет!
Если будут пожелания, можно в другой раз написать что-то вроде "CPS для чайников". Толку, правда, будет немного в рамках C#. Но разжевать предмет можно попробовать.

суббота, 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.


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