树中嵌套产量的性能

Question

我有一个树状的结构.此结构中的每个元素都应该能够返回它所属的所有元素的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().

我的问题是,是否正确实施了使用产量的版本,或者是否应该改进(特别是在性能方面).或者这只是坏事我应该坚持Lists(或ReadOnlyCollections)而不是？

Answer 1

如果您将recurse展开到堆栈,则可以提高性能,因此您将只有一个迭代器:

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

Answer 2

它在性能方面肯定不理想 - 你最终为大树创建了很多迭代器,而不是一个知道如何有效遍历的迭代器.

一些关于此的博客文章:

• Wes Dyer:关于迭代器的一切
• Eric Lippert:C#的不变性,第6部分
• Eric再次说明:C#中的不变性,第7部分

值得注意的是,F#具有相当于提议的" yield foreach"与" yield!"