树中嵌套产量的性能

发布于 2024-07-26 05:28:33 字数 796 浏览 4 评论 0原文

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

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

元素 C 调用 GetAll 返回 {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() 添加了 child-foos。

我的问题是使用yield的版本是否正确实现或者是否应该改进（特别是在性能方面）。或者这只是不好，我应该坚持使用 List（或 ReadOnlyCollections）？

原文

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

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.

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

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

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

究竟谁懂我的在乎 2024-08-02 05:28:33

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

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

You can improve performance if you unroll recurse to stack, so you will have only one iterator:

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

回复收藏 0 原文

鸩远一方 2024-08-02 05:28:33

就性能而言，这当然并不理想 - 您最终会为大型树创建大量迭代器，而不是知道如何有效遍历的单个迭代器。

与此相关的一些博客文章：

值得注意的是，F# 具有与提议的“yield foreach”等效的功能”和“屈服！”

回复收藏 0 原文

风蛊 2024-08-02 05:28:33

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

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

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

采用这种方法

避免创建大量嵌套迭代器
避免创建不必要的列表相对
高效
如果您只定期需要列表的一部分，则会失败

A better solution might be to create a visit method that recursively traverses the tree, and use that to collect items up.

Something like this (assuming a binary tree):

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

Taking this approach

Avoids creating large numbers of nested iterators
Avoids creating any more lists than necessary
Is relatively efficient
Falls down if you only need part of the list regularly

回复收藏 0 原文

素手挽清风 2024-08-02 05:28:33

不，看起来不错。

看看我的博客文章，它可能有一些用处:)

回复收藏 0 原文

缺⑴份安定 2024-08-02 05:28:33

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

yield break;

最后。 :-)

According to my prior experiences using yield is a lot more effective than creating a List.
If you're using .NET 3.5, this implementation should be fine. But don't forget the