23

階層オブジェクトを再帰的に列挙し、いくつかの基準に基づいていくつかの要素を選択する場合、「フラット化」してから Linq を使用してフィルタリングするなどの手法の例が多数あります。

リンクテキスト

しかし、Form の Controls コレクションや TreeView の Nodes コレクションのようなものを列挙する場合、IEnumerable である (拡張メソッドへの) 引数が必要なように見えるため、これらの種類の手法を使用できませんでした。 collection : SomeForm.Controls を渡すとコンパイルされません。

私が見つけた最も有用なものはこれでした:

リンクテキスト

これにより、Linq で使用できる IEnumerable の結果を持つ Control.ControlCollection の拡張メソッドが得られます。

上記の例を変更して、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 です。

また、Linq で使用できる形式で TreeNodeCollection または Control.ControlCollection を取得するために、2 番目のリンク (上記) に示されている方法よりも他の方法 (安い? 速い?) があるかどうかも知りたいと思います。

最初にリンクされた SO 投稿 (上記) の「SelectMany」に関する Leppie のコメントは、手がかりのようです。

SelectMany を使った私の実験は次のとおりです。:)

ポインタに感謝します。私は数時間を費やして、これらの領域に触れている SO の投稿をすべて読み、「y コンビネーター」などの異国情緒をとりとめのない道を歩んできました。「謙虚な」経験、私は付け加えるかもしれません:)

4

5 に答える 5

33

このコードはうまくいくはずです

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

次のベンチマーク手法を使用して簡単なパフォーマンス テストを行いました。結果が物語っています。ツリーの深さは、2 番目のソリューションのパフォーマンスにほとんど影響しません。一方、最初のソリューションではパフォーマンスが急速に低下し、最終的StackOverflowExceptionにはツリーの深さが大きくなりすぎます。

ベンチマーク

于 2009-11-29T13:56:31.530 に答える
22

あなたは正しい方向に進んでいるようで、上記の回答にはいくつかの良いアイデアがあります。しかし、これらすべての再帰的なソリューションにはいくつかの重大な欠陥があることに注意してください。

問題のツリーに合計 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/

最後に、再帰イテレータを書くための優れたテクニックをいくつか紹介しています。

于 2009-11-29T15:46:11.113 に答える
2

TreeNodes についてはよくわかりませんが、System.Linqたとえば and を使用して、フォーム IEnumerable の Controls コレクションを作成できます。

var ts = (from t in this.Controls.OfType<TextBox>
                 where t.Name.Contains("fish")
                 select t);
//Will get all the textboxes whose Names contain "fish"

頭のてっぺんから、これを再帰的にする方法がわからないと言って申し訳ありません。

于 2009-11-29T13:32:58.667 に答える
2

mrydengrenのソリューションに基づく:

public static IEnumerable<T> GetRecursively<T>(this IEnumerable collection,
    Func<T, IEnumerable> selector,
    Func<T, bool> predicate)
{
    foreach (var item in collection.OfType<T>())
    {
        if(!predicate(item)) continue;

        yield return item;

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


var theNodes = treeView1.Nodes.GetRecursively<TreeNode>(
    x => x.Nodes,
    n => n.Text.Contains("1")).ToList();

編集:BillW用

于 2009-11-29T14:29:55.587 に答える
1

このようなことを求めていると思います。

public static IEnumerable<T> <T,TCollection> GetNodesRecursively(this TCollection nodeCollection, Func<T, TCollection> getSub)
 where T, TCollection: IEnumerable
{   
    foreach (var theNode in )
    {
        yield return theNode;
        foreach (var subNode in GetNodesRecursively(theNode, getSub))
        {
            yield return subNode;
        }
    }
}

var all_control = GetNodesRecursively(control, c=>c.Controls).ToList();
于 2009-11-29T14:06:32.433 に答える