代码之家 › 专栏 › 技术社区 › mafu

树的嵌套产量性能

yield ienumerable performance c#

6

mafu · 技术社区 · 16 年前

我有一个树形结构。此结构中的每个元素都应该能够返回其根目录下的所有元素的可枚举值。让我们调用这个方法 IEnumerable<Foo> GetAll() . 如果我们有

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

对…的呼唤 GetAll 关于元素 C 收益率 {C, F, G} (元素的固定顺序很好,但不需要)。我想大家都已经知道了。

当前实施的 盖特尔 如下所示:

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

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

在早期的实现中,我返回了一个列表,并使用 List.AddRange() .

我的问题是,使用yield的版本是正确实现的还是应该改进的(特别是在性能方面)。还是这很糟糕,我应该坚持 List S(或) ReadOnlyCollections 而不是?

5 回复 | 直到 16 年前

1

10

Jon Skeet 16 年前

在性能方面,它当然不理想——您最终会为大型树创建很多迭代器,而不是一个知道如何高效遍历的迭代器。

关于这方面的一些博客条目:

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

值得注意的是,F与提议的 yield foreach “随” yield! “

2

19

arbiter 16 年前

如果展开Recurse到Stack,可以提高性能,因此只有一个迭代器:

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

3

2

Bevan 16 年前

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

类似这样(假设是二叉树):

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

采用这种方法

避免创建大量嵌套迭代器
避免创建任何超出需要的列表
相对有效
如果你经常只需要一部分的话,就会掉下来。

4

1

leppie 16 年前

不,看起来不错。

看看我的 blog entry ,它可能有一些用途:)

5

-1

ShdNx 16 年前

根据我以前的经验,使用yield比创建一个列表要有效得多。如果您使用的是.NET 3.5,那么这个实现就可以了。但别忘了

yield break;

最后。-)