Производительность вложенного урожая в дереве

Question

У меня есть древовидная структура. Каждый элемент этой структуры должен иметь возможность возвращать Enumerable из всех элементов, к которым он принадлежит root. Назовем этот метод IEnumerable<Foo> GetAll(). Так что, если у нас есть

 A <-- topmost root 
    / \ 
    B  C 
/\ /\ 
    D E F G 

исходящий вызов в GetAll на элемент C возвращает {C, F, G} (фиксированный порядок элементов было бы хорошо, но не требуется). Думаю, все это уже знали.

Текущая реализация GetAll выглядит следующим образом:

public IEnumerable<Foo> GetAll() 
{ 
    yield return this; 

    foreach (Foo foo in MyChildren) { 
     foreach (Foo f in foo.GetAll()) { 
      yield return f; 
     } 
    } 
} 

В предыдущей реализации, я вернулся в списке и добавил ребенок-FOOS использования List.AddRange().

Мой вопрос в том, что версия с использованием доходности реализована или если она должна быть улучшена (особенно с точки зрения производительности). Или это просто плохо, и я должен придерживаться List s (или ReadOnlyCollections) вместо этого?

Answer 1

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

Некоторые записи в блоге относительно этого:

• Wes Dyer: All about iterators
• Эрик Липперт: Immutability in C#, part 6
• Эрик снова: Immutability in C#, part 7

Стоит отметить, что F # имеет эквивалент из предлагается «yield foreach» с «yield!»

Answer 2

Нет, это выглядит нормально.

Посмотри на моих blog entry, он может быть полезны :)

Answer 3

По моему предыдущему опыту, используя выход намного более эффективный, чем создание списка. Если вы используете .NET 3.5, эта реализация должна быть прекрасной. Но не забывайте, что

yield break; 

В конце. :-)

Answer 4

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

Нечто подобное (предполагая, что бинарное дерево):

public class Node<T> 
{ 
    public void Visit(Action<T> action) 
    { 
     action(this); 
     left.Visit(action); 
     right.Visit(action); 
    } 

    public IEnumerable<Foo> GetAll() 
    { 
     var result = new List<T>(); 
     Visit(n => result.Add(n)); 
     return result; 
    } 
} 

Принимая этот подход

• Избегает создания большого количества вложенных итераторы
• Избегает создания каких-либо дополнительных списков, чем необходимо
• Является относительно эффективным
• Падает вниз, если вам нужна только часть l IST регулярно

Answer 5

Вы можете улучшить производительность, если раскатать рекурсию в стек, так что вы будете иметь только один итератор:

public IEnumerable<Foo> GetAll() 
{ 
    Stack<Foo> FooStack = new Stack<Foo>(); 
    FooStack.Push(this); 

    while (FooStack.Count > 0) 
    { 
     Foo Result = FooStack.Pop(); 
     yield return Result; 
     foreach (Foo NextFoo in Result.MyChildren) 
      FooStack.Push(NextFoo); 
    } 
}