树中嵌套收益的性能 [英] Performance of nested yield in a tree

问题描述

我有一个类似树的结构.此结构中的每个元素都应该能够返回其根目录所在的所有元素的Enumerable.我们将此方法称为IEnumerable<Foo> GetAll().所以如果我们有

I've got a tree-like structure. Each element in this structure should be able to return a Enumerable of all elements it is root to. Let's call this method IEnumerable<Foo> GetAll(). So if we have

      A <-- topmost root
    /   \
   B     C
  / \   / \
  D  E  F  G

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

a call to GetAll on element C returns {C, F, G} (fixed order of elements would be nice, but is not needed). I guess everybody knew that already.

GetAll的当前实现如下所示:

The current implementation of GetAll looks like this:

public IEnumerable<Foo> GetAll ()
{
    yield return this;

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

在较早的实现中，我返回了一个列表，并使用List.AddRange()添加了子foos.

In an earlier implementation, I returned a List and added the child-foos using List.AddRange().

我的问题是，是否正确实施了使用yield的版本，或者是否应该对其进行改进(特别是在性能方面).还是这不好，我应该坚持使用List(或ReadOnlyCollections)?

My question is if the version using yield is correcly implemented or if it should be improved (esp. in terms of performance). Or is this just bad and I should stick to Lists (or ReadOnlyCollections) instead?

推荐答案

就性能而言，这当然不是理想的选择-您最终为大型树创建了很多迭代器，而不是一个知道如何有效遍历的单个迭代器.

It's certainly not ideal in terms of performance - you end up creating a lot of iterators for large trees, instead of a single iterator which knows how to traverse efficiently.

一些与此相关的博客条目:

Some blog entries concerning this:

• Wes Dyer:有关迭代器的所有信息
• 埃里克·利珀特(Eric Lippert):

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

值得注意的是，F#与建议的"yield foreach"和"yield!"等效.

It's worth noting that F# has the equivalent of the proposed "yield foreach" with "yield!"

这篇关于树中嵌套收益的性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！