Вопрос по c#, performance – Производительность вложенного урожая в дереве

7

У меня древовидная структура. Каждый элемент в этой структуре должен иметь возможность возвращать 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с (илиReadOnlyCollections) вместо?

Ваш Ответ

5   ответов
1

Взгляни на мойзапись в блогеэто может быть полезно :)

10

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

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

Wes Dyer: All about iterators Eric Lippert: Immutability in C#, part 6 Eric again: Immutability in C#, part 7

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

2

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

Примерно так (при условии бинарного дерева):

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

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

Avoids creating large numbers of nested iterators Avoids creating any more lists than necessary Is relatively efficient Falls down if you only need part of the list regularly
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded mafu
Error: User Rate Limit Exceeded
-1

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

yield break;

В конце. :-)

Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
20

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

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);
    }
}
Error: User Rate Limit ExceededList<T>Error: User Rate Limit ExceededQueue<T>Error: User Rate Limit ExceededStack<T>Error: User Rate Limit ExceededList<T>.AddRange(...)Error: User Rate Limit Exceededforeach(...) { Queue<T>Enqueue(...) }.
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded mafu
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded

Похожие вопросы