Обход дерева без рекурсивного/стекового использования (C#)?

Question

Я работаю с WPF, и я разрабатываю сложный пользовательский контроль, состоящий из дерева с богатой функциональностью и т. Д. Для этого я использовал шаблон проектирования View-Model, поскольку некоторые операции не могли быть достигнуты напрямую в WPF. Поэтому я беру IHierarchyItem (который является узлом и передать его в этот конструктор, чтобы создать структуру дерева)

private IHierarchyItemViewModel(IHierarchyItem hierarchyItem, IHierarchyItemViewModel parent) 
     { 
      this.hierarchyItem = hierarchyItem; 
      this.parent = parent;  

      List<IHierarchyItemViewModel> l = new List<IHierarchyItemViewModel>(); 
      foreach (IHierarchyItem item in hierarchyItem.Children) 
      { 
       l.Add(new IHierarchyItemViewModel(item, this)); 
      } 
      children = new ReadOnlyCollection<IHierarchyItemViewModel>(l); 
     } 

Проблема заключается в том, что этот конструктор занимает около 3 секунд !! для 200 предметов на моем двухъядерном процессоре. Я делаю anythig неправильный или рекурсивный вызов конструктора, это медленно? Большое спасибо!

Answer 1

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

Было бы полезно выполнить некоторые простые профилирования для вашего конструктора. Используя одно из предложений от: http://en.csharp-online.net/Measure_execution_time, вы можете указать, сколько времени занимает каждая часть.

Существует вероятность того, что одна деталь, в частности, занимает много времени. В любом случае, это может помочь вам сузить место, где вы действительно проводите время.

Answer 2

OK Я нашел нерекурсивную версию самостоятельно, хотя она использует стек. Он проходит по всему дереву:

Stack<MyItem> stack = new Stack<MyItem>(); 

stack.Push(root); 

while (stack.Count > 0) 
{ 
    MyItem taken = stack.Pop(); 

    foreach (MyItem child in taken.Children)     
     stack.Push(MyItem);      

}