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

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

7 голосов
/ 25 июня 2009

У меня древовидная структура. Каждый элемент в этой структуре должен иметь возможность возвращать Enumerable всех элементов, к которым он относится. Давайте назовем этот метод 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;
        }
    }
}

В более ранней реализации я возвратил List и добавил child-foos, используя List.AddRange().

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

Ответы [ 5 ]

20 голосов
/ 25 июня 2009

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

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);
    }
}
10 голосов
/ 25 июня 2009

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

Некоторые записи в блоге, касающиеся этого:

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

2 голосов
/ 25 июня 2009

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

Примерно так (предполагается, что двоичное дерево): 

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;
    }
}

При таком подходе

  • Предотвращает создание большого количества вложенных итераторов
  • Предотвращает создание большего числа списков, чем необходимо
  • Относительно эффективен
  • Падениявниз, если вам нужна только часть списка регулярно
1 голос
/ 25 июня 2009

Нет, это выглядит хорошо.

Посмотрите на мою запись в блоге , она может быть полезна:)

0 голосов
/ 25 июня 2009

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

yield break;

В конце. : -)

...