枚举本质上不是IEnumerable的集合？

Question

当你想递归枚举一个分层对象,根据一些标准选择一些元素时,有许多技术的例子,如"展平",然后使用Linq进行过滤:如下所示:

链接文字

但是,当您枚举类似Form的Controls集合或TreeView的Nodes集合时,我一直无法使用这些类型的技术,因为它们似乎需要一个参数(对于扩展方法),这是一个IEnumerable集合:传入SomeForm.Controls不编译.

我发现最有用的是:

链接文字

哪个为您提供Control.ControlCollection的扩展方法,其中包含IEnumerable结果,然后您可以使用Linq.

我修改了上面的例子来解析TreeView的节点没有问题.

public static IEnumerable<TreeNode> GetNodesRecursively(this TreeNodeCollection nodeCollection)
{
    foreach (TreeNode theNode in nodeCollection)
    {
        yield return theNode;

        if (theNode.Nodes.Count > 0)
        {
            foreach (TreeNode subNode in theNode.Nodes.GetNodesRecursively())
            {
                yield return subNode;
            }
        }
    }
}

这是我现在使用扩展方法编写的代码:

    var theNodes = treeView1.Nodes.GetNodesRecursively();

    var filteredNodes = 
    (
        from n in theNodes
            where n.Text.Contains("1")
                select n
    ).ToList();

而且我认为在传递约束的地方可能会有更优雅的方法.

我想知道是否可以一般性地定义这样的过程,以便:在运行时我可以将集合类型以及实际集合传递给泛型参数,因此代码与是否无关它是TreeNodeCollection或Controls.Collection.

我还有兴趣知道是否有任何其他方式(更便宜？fastser？)比第二个链接(上面)中所示,以获得Linq可用的形式的TreeNodeCollection或Control.ControlCollection.

Leppie关于'在第一个(上图)链接的SO帖子中的SelectMany的评论似乎是一个线索.

我对SelectMany的实验是:好吧,称之为"灾难".:)

感谢任何指针.我已经花了几个小时阅读我发现的那些触及这些区域的SO帖子,然后漫无目的地进入像"y-combinator"这样的exotica.一个"谦卑"的经历,我可能会补充:)

Answer 1

这段代码应该可以解决问题

public static class Extensions
{
    public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        foreach (var item in collection.OfType<T>())
        {
            yield return item;

            IEnumerable<T> children = selector(item).GetRecursively(selector);
            foreach (var child in children)
            {
                yield return child;
            }
        }
    }
}

这是一个如何使用它的例子

TreeView view = new TreeView();

// ...

IEnumerable<TreeNode> nodes = view.Nodes.
    .GetRecursively<TreeNode>(item => item.Nodes);

更新:回应Eric Lippert的帖子.

这是使用All About Iterators中讨论的技术的一个大大改进的版本.

public static class Extensions
{
    public static IEnumerable<T> GetItems<T>(this IEnumerable collection,
        Func<T, IEnumerable> selector)
    {
        Stack<IEnumerable<T>> stack = new Stack<IEnumerable<T>>();
        stack.Push(collection.OfType<T>());

        while (stack.Count > 0)
        {
            IEnumerable<T> items = stack.Pop();
            foreach (var item in items)
            {
                yield return item;

                IEnumerable<T> children = selector(item).OfType<T>();
                stack.Push(children);
            }
        }
    }
}

我使用以下基准测试技术进行了简单的性能测试.结果不言自明.树的深度对第二种解决方案的性能只有微不足道的影响; 而第一种解决方案的性能迅速下降,最终StackOverflowException导致树的深度变得太大.

Answer 2

你似乎走在正确的轨道上,上面的答案有一些好主意.但我注意到所有这些递归解决方案都有一些深层次的缺陷.

假设所讨论的树总共有n个节点,其最大树深度为d <= n.

首先,它们消耗树深处的系统堆栈空间.如果树结构非常深,那么这可能会破坏堆栈并使程序崩溃.树深d是O(lg n),取决于树的分支因子.更糟糕的情况是根本没有分支 - 只是一个链表 - 在这种情况下,只有几百个节点的树会炸掉堆栈.

其次,你在这里做的是构建一个迭代器,它调用一个调用迭代器的迭代器......这样顶层迭代器上的每个MoveNext()实际上都会在成本中再次调用O(d).如果在每个节点上执行此操作,则调用的总成本为O(nd),最差情况为O(n ^ 2),最佳情况为O(n lg n).你可以做得比两者都好; 没有理由为什么这不能及时线性.

诀窍是停止使用小而脆弱的系统堆栈来跟踪下一步该做什么,并开始使用堆分配的堆栈来明确跟踪.

您应该在阅读列表中添加Wes Dyer的文章:

https://blogs.msdn.microsoft.com/wesdyer/2007/03/23/all-about-iterators/

他最后给出了一些编写递归迭代器的好技巧.