[c#] LINQ経由でツリーをフラット化する方法は?



4 Answers

受け入れられた答えの問題は、樹木が深い場合には非効率的であるということです。 木が非常に深い場合は、スタックを吹き飛ばします。 明示的なスタックを使用することで、この問題を解決できます。

public static IEnumerable<MyNode> Traverse(this MyNode root)
{
    var stack = new Stack<MyNode>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in current.Elements)
            stack.Push(child);
    }
}

この方法は、スタック空間ではO(1)、ヒープ空間ではO(h)、時間ではO(n)である。 他のアルゴリズムはスタックではO(h)、ヒープではO(1)、時間ではO(nh)です。 分岐因子がnに比べて小さい場合、hはO(lg n)とO(n)の間にあり、これはナイーブなアルゴリズムが危険な量のスタックを使用できることと、hがnに近い場合は長い時間を使用できることを示しています。

トラバーサルができたので、あなたの問い合わせは簡単です:

root.Traverse().Where(item=>item.group == 1);
Question

だから私は単純な木を持っている:

class MyNode
{
 public MyNode Parent;
 public IEnumerable<MyNode> Elements;
 int group = 1;
}

私はIEnumerable<MyNode>を持っています。 私はすべてのMyNode (内部ノードオブジェクト( Elements )を含む)のリストを1つのフラットリストとして取得したいと思いますMyNode group == 1 。 そのようなことをLINQ経由で行う方法は?




以下はIvan Stoevのコードで、パス内のすべてのオブジェクトのインデックスを伝える追加機能があります。 例: "Item_120"を検索:

Item_0--Item_00
        Item_01

Item_1--Item_10
        Item_11
        Item_12--Item_120

アイテムとint配列[1,2,0]を返します。 明らかに、配列の長さとしてネストレベルも使用できます。

public static IEnumerable<(T, int[])> Expand<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> getChildren) {
    var stack = new Stack<IEnumerator<T>>();
    var e = source.GetEnumerator();
    List<int> indexes = new List<int>() { -1 };
    try {
        while (true) {
            while (e.MoveNext()) {
                var item = e.Current;
                indexes[stack.Count]++;
                yield return (item, indexes.Take(stack.Count + 1).ToArray());
                var elements = getChildren(item);
                if (elements == null) continue;
                stack.Push(e);
                e = elements.GetEnumerator();
                if (indexes.Count == stack.Count)
                    indexes.Add(-1);
                }
            if (stack.Count == 0) break;
            e.Dispose();
            indexes[stack.Count] = -1;
            e = stack.Pop();
        }
    } finally {
        e.Dispose();
        while (stack.Count != 0) stack.Pop().Dispose();
    }
}



これに対処する最も簡単で最も明確な方法は、再帰LINQクエリを使用することです。 この質問: LINQでの再帰の表現にはこれに関する議論がたくさんありますhttps://.com/a/793531/1550この特定の回答https://.com/a/793531/1550は、どのように実装するかについていくつか詳しく説明しています。




更新:

ネスティングのレベル(深さ)に興味のある人向け。 明示的な列挙型スタックの実装に関する良い点の1つは、いつでも(特に要素を生成するとき)、 stack.Countが現在の処理の深さを表していることです。 このことを考慮に入れて、C#7.0値のタプルを利用すると、単にメソッド宣言を次のように変更することができます。

public static IEnumerable<(T Item, int Level)> ExpandWithLevel<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)

そしてyield文:

yield return (item, stack.Count);

次に、上記の単純なSelectを適用して元のメソッドを実装することができます。

public static IEnumerable<T> Expand<T>(
    this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector) =>
    source.ExpandWithLevel(elementSelector).Select(e => e.Item);

元の:

意外なことに誰も(エリックでさえも)再帰的な事前注文DFTの「自然な」反復ポートを示したので、

    public static IEnumerable<T> Expand<T>(
        this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
    {
        var stack = new Stack<IEnumerator<T>>();
        var e = source.GetEnumerator();
        try
        {
            while (true)
            {
                while (e.MoveNext())
                {
                    var item = e.Current;
                    yield return item;
                    var elements = elementSelector(item);
                    if (elements == null) continue;
                    stack.Push(e);
                    e = elements.GetEnumerator();
                }
                if (stack.Count == 0) break;
                e.Dispose();
                e = stack.Pop();
            }
        }
        finally
        {
            e.Dispose();
            while (stack.Count != 0) stack.Pop().Dispose();
        }
    }



DaveとIvan Stoevの答えを組み合わせると、ネスティングのレベルが必要で、リストが "順番に"平らになり、Konamimanによって与えられた答えのように逆転されません。

 public static class HierarchicalEnumerableUtils
    {
        private static IEnumerable<Tuple<T, int>> ToLeveled<T>(this IEnumerable<T> source, int level)
        {
            if (source == null)
            {
                return null;
            }
            else
            {
                return source.Select(item => new Tuple<T, int>(item, level));
            }
        }

        public static IEnumerable<Tuple<T, int>> FlattenWithLevel<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> elementSelector)
        {
            var stack = new Stack<IEnumerator<Tuple<T, int>>>();
            var leveledSource = source.ToLeveled(0);
            var e = leveledSource.GetEnumerator();
            try
            {
                while (true)
                {
                    while (e.MoveNext())
                    {
                        var item = e.Current;
                        yield return item;
                        var elements = elementSelector(item.Item1).ToLeveled(item.Item2 + 1);
                        if (elements == null) continue;
                        stack.Push(e);
                        e = elements.GetEnumerator();
                    }
                    if (stack.Count == 0) break;
                    e.Dispose();
                    e = stack.Pop();
                }
            }
            finally
            {
                e.Dispose();
                while (stack.Count != 0) stack.Pop().Dispose();
            }
        }
    }



Related