树中嵌套产量的性能

我有一个树状的结构。 此结构中的每个元素都应该能够返回它所属的所有元素的Enumerable。 我们将此方法称为IEnumerable GetAll() 。 所以,如果我们有

  A <-- topmost root / \ BC / \ / \ DEFG 

在元素C上调用GetAll返回{C, F, G} (元素的固定顺序会很好,但不需要)。 我想每个人都已经知道了。

GetAll的当前实现如下所示:

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

在早期的实现中,我返回了一个List并使用List.AddRange()添加了child-foos。

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

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

一些关于此的博客文章:

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

值得注意的是,F#具有与“ yield! ”相同的“ yield! ”。

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

 public IEnumerable GetAll() { Stack FooStack = new Stack(); FooStack.Push(this); while (FooStack.Count > 0) { Foo Result = FooStack.Pop(); yield return Result; foreach (Foo NextFoo in Result.MyChildren) FooStack.Push(NextFoo); } } 

一个更好的解决方案可能是创建一个递归遍历树的访问方法,并使用它来收集项目。

像这样的东西(假设一棵二叉树):

 public class Node { public void Visit(Action action) { action(this); left.Visit(action); right.Visit(action); } public IEnumerable GetAll () { var result = new List(); Visit( n => result.Add(n)); return result; } } 

采取这种方法

  • 避免创建大量嵌套迭代器
  • 避免创建超出必要的列表
  • 相对有效
  • 如果您只需要定期列出部分列表,则会跌倒

不,那看起来不错。

看看我的博客文章 ,它可能有些用:)

根据我以前的经验,使用yield比创建List更有效。 如果您使用的是.NET 3.5,那么此实现应该没问题。 但别忘了

 yield break; 

在末尾。 🙂