7

我有一个树状结构。此结构中的每个元素都应该能够返回它作为根的所有元素的 Enumerable。让我们调用这个方法IEnumerable<Foo> GetAll()。所以如果我们有

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

GetAll对on elementC返回的调用{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 并使用List.AddRange().

我的问题是使用 yield 的版本是否正确实施或者是否应该改进（尤其是在性能方面）。还是这很糟糕，我应该坚持使用Lists （或ReadOnlyCollections） ？

4

5 回答 5

20

如果将递归展开到堆栈，则可以提高性能，因此您将只有一个迭代器：

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-25T11:13:48.797 回答
11

就性能而言，这当然不是理想的——你最终会为大树创建很多迭代器，而不是一个知道如何有效遍历的迭代器。

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

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

于 2009-06-25T10:16:10.100 回答
2

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

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

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

采取这种方法

  • 避免创建大量嵌套迭代器
  • 避免创建不必要的列表
  • 比较有效率
  • 如果您只需要定期列出清单的一部分，就会跌倒
于 2009-06-25T10:22:57.277 回答
1

不，看起来不错。

看看我的博文，也许有用:)

于 2009-06-25T10:13:34.003 回答
-1

根据我之前的经验，使用 yield 比创建 List 更有效。如果您使用的是 .NET 3.5，则此实现应该没问题。但不要忘记

yield break;

在末尾。:-)

于 2009-06-25T10:15:56.557 回答