1

私は定期的に再帰IEnumerable<T>イテレータを書いて、たとえばXContainer.Descendants. 私が実装し続けているパターンは次のとおりFooですChildren。

public static IEnumerable<Foo> Descendants(this Foo root) {
    foreach (var child in root.Children()) {
        yield return child;
        foreach (var subchild in child.Descendants()) {
            yield return subchild;
        }
    }
}

この古い StackOverflow の質問は、同じパターンを示唆しています。rootしかし、何らかの理由で、3 つのレベルの階層 ( 、child、および)を参照する必要があるのは奇妙に感じますsubchild。この基本的な深さ優先の再帰パターンをさらに減らすことはできますか? それとも、これは一種のアルゴリズムのプリミティブですか?

私が思いつく最善の方法は、パターンを一般的な拡張に抽象化することです。これにより、上記の反復子パターンのロジックが縮小されることはありませんが、Descendants複数の特定のクラスに対してメソッドを定義する必要がなくなります。欠点として、これはそれ自体に拡張メソッドを追加しObjectますが、これは少し臭いです:

public static IEnumerable<T> SelectRecurse<T>(
    this T root, Func<T, IEnumerable<T>> enumerator) {

    foreach (T item in enumerator(root))
    {
        yield return item;
        foreach (T subitem in item.SelectRecurse(enumerator))
        {
            yield return subitem;
        }
    }
}

// Now we can just write:
foreach(var item in foo.SelectRecurse(f => f.Children())) { /* do stuff */ }
4

7 に答える 7

1

私はこれを次のように管理しますList：

public static IEnumerable<Foo> Descendants(this Foo root) {
    List<Foo> todo = new List<Foo>();
    todo.AddRange(root.Children());
    while(todo.Count > 0)
    {
        var first = todo[0];
        todo.RemoveAt(0);
        todo.InsertRange(0,first.Children());
        yield return first;
    }
}

再帰的ではないので、スタックを爆破すべきではありません。リストの先頭に常に自分の作業を追加するだけで、深さ優先のトラバーサルを実現できます。

于 2013-10-18T14:28:30.637 に答える
0

yield を使用せずに、別のバージョンを提案します。

    public abstract class RecursiveEnumerator : IEnumerator {
        public RecursiveEnumerator(ICollection collection) {
            this.collection = collection;
            this.enumerator = collection.GetEnumerator();
        }

        protected abstract ICollection GetChildCollection(object item);

        public bool MoveNext() {
            if (enumerator.Current != null) {
                ICollection child_collection = GetChildCollection(enumerator.Current);
                if (child_collection != null && child_collection.Count > 0) {
                    stack.Push(enumerator);
                    enumerator = child_collection.GetEnumerator();
                }
            }
            while (!enumerator.MoveNext()) {
                if (stack.Count == 0) return false;
                enumerator = stack.Pop();
            }
            return true;
        }

        public virtual void Dispose() { }

        public object Current { get { return enumerator.Current; } }

        public void Reset() {
            stack.Clear();
            enumerator = collection.GetEnumerator();
        }

        private IEnumerator enumerator;
        private Stack<IEnumerator> stack = new Stack<IEnumerator>();
        private ICollection collection;
    }

使用例

    public class RecursiveControlEnumerator : RecursiveEnumerator, IEnumerator {
        public RecursiveControlEnumerator(Control.ControlCollection controlCollection)
            : base(controlCollection) { }

        protected override ICollection GetChildCollection(object c) {
            return (c as Control).Controls;
        }
    }
于 2016-11-23T02:08:56.137 に答える
0

Damien_the_Unbeliever と Servy の両方が、何らかのタイプのコレクションを使用して再帰呼び出しスタックの作成を回避するアルゴリズムのバージョンを提示しました。Damien が a を使用するとList、リストの先頭に挿入するパフォーマンスが低下する可能性があり、Servy がスタックの a を使用すると、ネストされた要素が逆の順序で返される可能性があります。一方向リンク リストを手動で実装すると、元の順序ですべての項目を返しながら、Servy のパフォーマンスが維持されると思います。唯一のトリッキーな部分はForwardLink、ルートを反復して最初の s を初期化することです。Traverseきれいに保つために、それを のコンストラクターに移動しましたForwardLink。

public static IEnumerable<T> Traverse<T>(
    this T root, 
    Func<T, IEnumerable<T>> childrenSelector) {

    var head = new ForwardLink<T>(childrenSelector(root));

    if (head.Value == null) yield break; // No items from root iterator

    while (head != null)
    {
        var headValue = head.Value;
        var localTail = head;
        var second = head.Next;

        // Insert new elements immediately behind head.
        foreach (var child in childrenSelector(headValue))
            localTail = localTail.Append(child);

        // Splice on the old tail, if there was one
        if (second != null) localTail.Next = second;

        // Pop the head
        yield return headValue;
        head = head.Next; 
    }
}

public class ForwardLink<T> {
    public T Value { get; private set; }
    public ForwardLink<T> Next { get; set; }

    public ForwardLink(T value) { Value = value; }

    public ForwardLink(IEnumerable<T> values) { 
        bool firstElement = true;
        ForwardLink<T> tail = null;
        foreach (T item in values)
        {
            if (firstElement)
            {
                Value = item;
                firstElement = false;
                tail = this;
            }
            else
            {
                tail = tail.Append(item);
            }
        }
    }

    public ForwardLink<T> Append(T value) {
        return Next = new ForwardLink<T>(value);
    } 
}
于 2013-10-18T16:27:00.560 に答える
-1

私のコメントを拡張するには、これでうまくいくはずです：

public static IEnumerable<Foo> Descendants(this Foo node)
{
    yield return node; // return branch nodes
    foreach (var child in node.Children())
        foreach (var c2 in child.Descendants())
            yield return c2; // return leaf nodes
}

これにより、すべてのブランチ ノードとリーフ ノードが返されます。リーフ ノードのみを返したい場合は、最初の yield リターンを削除します。

あなたの質問に答えて、はい、それはアルゴリズムのプリミティブです.node.Children（）を呼び出す必要があり、各子でchild.Descendants（）を呼び出す必要があるからです。2 つの "foreach" ループがあるのは奇妙に思えることに同意しますが、2 番目のループは実際には、子を反復するのではなく、全体的な列挙を継続するだけです。

于 2013-10-18T14:00:14.680 に答える
-1

これを試して：

private static IEnumerable<T> Descendants<T>(
    this IEnumerable<T> children, Func<T, IEnumerable<T>> enumerator)
{
    Func<T, IEnumerable<T>> getDescendants =
        child => enumerator(child).Descendants(enumerator);

    Func<T, IEnumerable<T>> getChildWithDescendants =
        child => new[] { child }.Concat(getDescendants(child));

    return children.SelectMany(getChildWithDescendants);
}

または、Linq 以外のバリアントを好む場合は、次のようにします。

private static IEnumerable<T> Descendants<T>(
    this IEnumerable<T> children, Func<T, IEnumerable<T>> enumerator)
{
    foreach (var child in children)
    {
        yield return child;

        var descendants = enumerator(child).Descendants(enumerator);

        foreach (var descendant in descendants)
        {
            yield return descendant;
        }
    }
}

そして、次のように呼び出します。

root.Children().Descendants(f => f.Children())
于 2013-10-18T14:35:49.327 に答える