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

[lam0x86]

Те же яйца, только в профиль:

sealed class Dumper
{
  static public string Dump(Node root)
  {
    var sb = new StringBuilder();
    Action<Node, string> action = null;
    action = (node, indent) =>
    {
      // Precondition: indentation and prefix has already been output
      // Precondition: indent is correct for node's *children*
      sb.AppendLine(node.Text);
      for (int i = 0; i < node.Children.Count; ++i)
      {
        bool last = i == node.Children.Count - 1;
        var child = node.Children[i];
        sb.Append(indent);
        sb.Append(last ? '└' : '├');
        sb.Append('─');
        action(child, indent + (last ? "  " : "│ "));
      }
    };

    action(root, "");

    return sb.ToString();
  }
}

Преимущество — многопоточность.

[lam0x86]

Ой, стыдно-то как… Исходная реализация тоже многопоточна =)
В общем, преимуществ нет, разве что более компактный вид получился.

[AlexTikhonov]

Красиво переписан вариант Эрика :) Он, насколько я знаю, не любит замыкания. Но Ваш вариант мне нравится больше.

Но я в упор не вижу многопоточности. Можете пояснить?

[AlexTikhonov]

а… заметил Ваш коммент :)

Как я понял, имелась ввиду «потокобезопасность» (thread-safity)?

[lam0x86]

так точно!

[lam0x86]

Я имел в виду, что данный метод не сломается, если вызывать его одновременно из нескольких потоков. Мне сначала показалось, что у Эрика весь класс помечен как статический, из-за чего экземпляр StringBuilder-а будет одним для всех потоков. Облажался, что ж=)
А метод, который я применил, я взял из его же блога. Странно, что он его не использовал. Видимо, решил не захламлять код модными лямбдами =)

blogs.msdn.com/b/ericlippert/archive/2010/04/22/every-tree-there-is.aspx

[AlexTikhonov]

Кстати, если сравнивать его метод и переписанный с лямбдой, то отличиия в основном только в замыкании. Но это замыкание точь-в-точь повторяет нестатическую часть класса Dumper у Эрика :)

Фактически в автоматически сгенерированном замыкании будет тот же самый StringBuilder и один анонимный метод.

Т.е. по производительности варианты должны практически полностью совпадать :)

[XaBoK]

Я бы лишь немного изменил. Убрал излишние обращения к колекции (обращения к Count), срезал ветвления if-else, кастинг char-string, убрал лишние Append (несколько Append подряд всегда вызывают подозрение, что как минимум AppendFormat был бы уместней). Кстати не понял зачем var child…
Как то так:

static public string Dump(Node root)
{
  StringBuilder result = new StringBuilder();
  Action<Node, string> action = null;
  action = (node, indent) =>
  {
    result.AppendLine(node.Text);
    for (int i = 0, lim = node.Children.Count, last=lim-1; i < lim; ++i)
    {
      string now = indent + "├─", next = indent + "│ ";
      if (i == last)
      {
        now = indent + "└─";
        next = indent + " ";
      }
      result.Append(now);
      action(node.Children[i], next);
    }
  };
  action(root, String.Empty);
  return result.ToString();
}

* This source code was highlighted with Source Code Highlighter.

[AlexTikhonov]

var child действительно не нужен. В остальном:

Проблема с "+" над строками в том, что он создает новую строку. А если i == last, то в Вашем варианте создается строки для обоих случаев.

Несколько Append-ов работают практически всегда быстрее, чем AppendFormat (хотя есть редкий usecase когда формат быстрее — на стековерфлоу пробегало). Другое дело, что можно было бы записать sb.Append().Append().Append()

Кастинга в char-string я не вижу. Append принимает char напрямую и добавляет в свой буффер, который сам char[] :)

Что же про Count, то тут Эрик пользуется тем, что у нас обычный массив, и обращение Array.Count довольно быстрое. Кстати, оно помеченно вот таким интересных атрибутиком:
[TargetedPatchingOptOut(«Performance critical to inline this type of method across NGen image boundaries»)]
Т.е. при NGen-e оно даже будет пытатся инлайнить этот вызов :)

[XaBoK]

Ну я не написал, что я улучшил вашу версию. Точнее — я написал свою и посмотрел, что она сильно похожа на вашу. Спасибо за информацию насчёт инлайна.

[JayDi]

Отличная иллюстрация того, к чему может привести злоупотребление всякими «новомодными штуками» при решение повседневных задач.

[s0rr0w]

Пояснение будет? Лично мне непонятно, что вы имеете в виду, где «новомодные штуки», а где злоупотребление…

[JayDi]

Злоупотребление в том, что здесь классическую задачу по перебору элементов дерева вместо простого решения с использованием рекурсии и цикла решают с помощью таких громозких инструментов, как LINQ и т.п. Все-равно, что стрелять в мух из пушки.

В приведенных решениях мало того, что невозможно разобраться с первого раза (в одном из примеров даже потребовались комментарии!), этот код невозможно легко модифицировать, отлаживать, да и вообще что-либо с ним делать. За такой код, попади он в рабочую ветку, ваши коллеги долго будут вспоминать вас добрым словом.

[s0rr0w]

Теперь понятнее. Но рекурсия не всегда быстра. Если ваша цель скорость… то скорее всего нужно менять технологию хранения данных, ибо id/parentid неприменима в таком контексте

[AlexTikhonov]

Хочу отметить, что в варианте «полностью LINQ» есть рекурсия, но закомментированна чтоб показать еще вариант и без рекурсии. Так же там есть тот же самый цикл.

Коментарии не необходимы, я просто их добавил чтоб еще более упростить прочтение.

С отладкой я тоже не вижу никаких проблем — на любой строчке ставиться breakpoint, можно смотреть текущее состояние.

Зачем нужен LINQ-вариант? Не всегда в реальных проектах имеем простые массивый (например, когда данные хранятся в базе данных и нет смысла загружать все данные в виде массива), не всегда в результате нужно получить строку (например, когда нужно построить какую-то объектную модель). И тогда уже LINQ-решения из «громоздкого инструмента» превращаются в инструмент, сокращающий код в разы. А эта задачка как раз чтоб потренироваться.

Код же я намеренно «растянул» (временные переменные, шаги) чтоб легче было читать. Более компактные варианты уже приведены в комментариях. Но не смотря на то, что они более лаконичные, мне лично их тяжелее читать. Кроме того, мои решения, которые я выложил, я написал еще до просмотра какого либо другого решения. Конечно же сейчас я бы мог еще более красивее написать.

Если не сложно, напишите свой вариант, в котором исправьте все недочеты приведенных вариантов.

[steck]

Решил подумать, можно ли сделать одним запросом.

static public string Dump(Node root)
    {
      return string.Join("",
        new[] { root.Text + "\n" }.Concat(
          root.Children.Take(root.Children.Count - 1).Select(Dump).Select(x => "├─" + x.TrimEnd().Replace("\n", "\n│ ")+"\n"))
          .Concat(root.Children.Skip(root.Children.Count - 1).Select(Dump).Select(x => "└─" + x.TrimEnd().Replace("\n", "\n ")+"\n"))
          .ToArray());      
    }

* This source code was highlighted with Source Code Highlighter.

Ну или если немного извратиться то

static public string Dump(Node root)
    {
      Func<Func<IEnumerable<Node>, int, IEnumerable<Node>>, string, string, Func<IEnumerable<Node>, IEnumerable<string>>> func =
        (take, a, b) => source => take(source, root.Children.Count - 1).Select(Dump)
          .Select(x => string.Format("{0}─{1}\n", a, x.TrimEnd().Replace("\n", "\n"+b+" ")));
      
      return string.Join("",
        new[] { root.
          Text + "\n" }.Concat(
          new []{func(Enumerable.Take,"├","│"),func(Enumerable.Skip,"└"," ")}.SelectMany(f => f(root.Children)))
          .ToArray());
    }

* This source code was highlighted with Source Code Highlighter.

[AlexTikhonov]

Спасибо! Вот теперь я полностью уверен, что не даром сделал свой пост :)

[AlexTikhonov]

Единственное что, скорость выполнения намного медленнее простых вариантов типа моего второго или Эрика или lam0x86 (на дереве с глубиной 7 и шириной 6 — прибавка около 98% под релиз конфигурацией). Думаю из-за операций со строками.

[dobersoft]

Многобукв в коде. В своё время я это делал двухстрочной хранимой процедурой в БД.