树中嵌套良率的性能

我有一棵树状结构。这个结构中的每个元素都应该能够返回它所有根元素的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.AddRange()增加了儿童的Foo。

我的问题是如果使用yield的版本得到了正确实施，或者应该改进（特别是在性能方面）。或者这是不好的，我应该坚持List s（或ReadOnlyCollections）？

来源

2009-06-25 mafu

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

关于这方面的一些博客文章：

韦斯·戴尔：All about iterators
埃里克利珀：再次Immutability in C#, part 6
埃里克：Immutability in C#, part 7

值得一提的是，F＃拥有的等效建议“yield foreach”与“yield!”

来源

2009-06-25 10:16:10

不，看起来不错。

看一看我的blog entry，也可能是一些使用:)

来源

2009-06-25 10:13:34 leppie

-1

的根据使用屈服我以前的经验是很多不是创建一个列表更有效。如果你使用.NET 3.5，这个实现应该没问题。但别忘了

yield break;

最后。 :-)

来源

2009-06-25 10:15:56 ShdNx

嗯，你为什么会想在这种情况下，最终得到休息？ – 2009-06-25 10:16:59

为什么最后需要这个？我认为枚举器在Enumerable方法退出时自动完成... – Bevan 2009-06-25 10:18:02

嗯，或许我误解了有关使用yield的一些问题。正如我记得，如果我没有用yield break来关闭这个方法，我会得到一个错误。如果我说了些蠢话，我很抱歉！要研究这个问题... – ShdNx 2009-06-25 10:20:18

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

像这样的东西（假设二叉树）：

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北京时间定期

来源

2009-06-25 10:22:57 Bevan

可以提高性能，如果你解开递归堆栈，所以你将有只有一个迭代器：

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

来源

2009-06-25 11:13:48 arbiter

树中嵌套良率的性能

回答

相关问题