Pull to refresh

Мини-задачка: «олд-скульное» дерево

Reading time 3 min
Views 1.8K

Постановка задачи



Буквально несколько дней назад Eric Lippert на своем блоге Fabulous Adventures In Coding опубликовал очень простую, но занимательную задачку:

Есть дерево, заданное с помощью класса Node, в котором есть Children с теми же самыми Node и какой-то Text (чуть ниже приведу код класса). Необходимо сгенерировать строку такого вида (включая переносы строк):
Использовать нужно юникодовые символы "│ ├ ─ └" (вспомним старые добрые картинки с псевдографикой). Цель, которую поставил себе Эрик — выяснить, какие предпочтения будут сделаны при составлении решения: рекурсивное (так как дерево), более быстрое или более читабельное.

&nbsp

Код исходного класса Node:
class Node<br>{<br>  public Node(string text, params Node[] children)<br>  {<br>    this.Text = text;<br>    this.Children = children ?? new Node[] {};<br>  }<br>  public string Text { get; private set; }<br>  public IList<Node> Children { get; private set; }<br>}<br><br>* This source code was highlighted with Source Code Highlighter.


Исходные данные:
var root = new Node("a", <br>  new Node("b",<br>    new Node("c", <br>      new Node("d")),<br>    new Node("e",<br>      new Node("f"))),<br>  new Node("g",   <br>    new Node("h",<br>      new Node("i")),<br>    new Node("j")));<br><br>* This source code was highlighted with Source Code Highlighter.


Задача заполнить пропущенные строки тут:
sealed class Dumper<br>{<br>  static public string Dump(Node root) { /* ... */ }<br>  /* ... */ <br>}<br><br>* This source code was highlighted with Source Code Highlighter.


Решения



Так, как я не нашел тега "<spoiler>" у хабрапарсера, и не хочу приводить решения в открытом виде. Чтоб не лишать удовольствия от написания собственного решения, я приведу ссылки на эти свои решения и немного поясню.

Но я бы все-таки посоветовал потратить десяток минут на написание своего решения. Если нет IDE или лень запускать, рекомендую Snippet Compiler (хотя он только для .NET 3.5, для 4.0 я не нашел ничего аналогичного — чтоб с code completition, без создания файлов).

Первый подход

Сначала я для себя поставил задачу пойти наиболее LINQ-way, абсолютно не учитывая скорость выполнения. Вышло довольно интересно — linq-подобный вариант. В коде есть как рекурсивная энумерация всех узлов дерева, так и итеративная. Прошу отметить, что вычисление происходит «лениво», все строки собираются или StringBuilder'ом или с помощью LinkedList и потом собираются Join'ом, что позволяет минимизировать лишнее копирование строк или сдвиг массивов.

Вариант вышел медленным. Очень.

Второй подход

Ленвые вычисления и т.д. конечно красиво, но захотелось написать наиболее оптимальную по скорости реализацию. Отметив, что «уровневый» отступ всегда одинаковый, и его мы можем использовать каждый раз при добавлении нового уровня, решил оформить это вот в такой вариант. Все в одной функции, добавлен только вспомогательный класс-контейнер. То же StringBuilder, но, на этот раз, решил отказаться от каких либо массивов для кусков индентов. И снова таки никакой рекурсии — проход по дереву и построение результата происходит одновременно.

Данный вариант отказался совсем хорошим в плане скорости выполнения. Сразу забегу чуть вперед, скажу что он даже иногда быстрее варианта Эрика на «широких» (т.е. тех, в которых больше children'ов, чем глубина).

Решение Эрика

Ну и решение Эрика. Как ни странно, в нем я нашел много из того, что я сделал в своем «быстром» решении — например, то как он проверяет последний ли элемент в списке «детей» или нет.

Лично мне эта задачка понравилась тем, что пару раз приходилось решать что-то похожее. Да и размять мозги приятно.

Если кто придумает более быстрый вариант — напишите, интересно еще посмотреть на подходы к оптимизации C# кода. И хотя пост похож на то, что пишут в «Спортивном программировании», но, мне кажется, тут слишком простая задача, чтоб сравнивать реализации с другими платформами и языками.

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

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

Upd:
Модифицированный вариант Эрика от lam0x86 в виде только одной функции: Смотреть
Два очень лаконичных варианта от steck активно использующих Linq: Смотреть
Tags:
Hubs:
+20
Comments 21
Comments Comments 21

Articles