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很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

3

您可以使用显式堆栈，而不是隐式使用线程的调用堆栈来存储您正在使用的数据。这甚至可以推广到Traverse只接受一个代表来代表“让我的孩子”调用的方法：

public static IEnumerable<T> Traverse<T>(
    this IEnumerable<T> source
    , Func<T, IEnumerable<T>> childrenSelector)
{
    var stack = new Stack<T>(source);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childrenSelector(next))
            stack.Push(child);
    }
}

因为这不是递归的，因此不会不断地创建状态机，所以它的性能会好很多。

旁注，如果您想要呼吸优先搜索，只需使用 aQueue而不是 a Stack。如果您想要最佳优先搜索，请使用优先级队列。

为了确保兄弟姐妹的返回顺序与它们从 selecor 的顺序返回的顺序相同，而不是相反，只需添加Reverse对childrenSelector.

于 2013-10-18T14:47:50.213 回答
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 回答
1

我认为这是一个很好的问题。我对为什么需要两个循环的最佳解释：我们需要认识到每个项目都被转换为多个项目（本身及其所有后代）的事实。这意味着我们不映射一对一（like Select），而是一对多（SelectMany）。

我们可以这样写：

public static IEnumerable<Foo> Descendants(this IEnumerable<Foo> items) {
 foreach (var item in items) {
  yield return item;
  foreach (var subitem in item.Children().Descendants())
   yield return subitem;
 }
}

或者像这样：

public static IEnumerable<Foo> Descendants(Foo root) {
 var children = root.Children();
 var subchildren = children.SelectMany(c => c.Descendants());
 return children.Concat(subchildren);
}

或者像这样：

public static IEnumerable<Foo> Descendants(this IEnumerable<Foo> items) {
 var children = items.SelectMany(c => c.Descendants());
 return items.Concat(children);
}

采用 an 的版本IEnumerable<Foo>必须在 上调用root.Children()。

我认为所有这些重写都揭示了看待问题的不同方式。另一方面，它们都有两个嵌套循环。循环可以隐藏在辅助函数中，但它们仍然存在。

于 2013-10-18T14:19:21.603 回答
0

Damien_the_Unbeliever 和 Servy 都提出了一种算法版本，通过使用一种或另一种类型的集合来避免创建递归调用堆栈。Damien 使用 aList可能会导致在列表头部插入时性能不佳，而 Servy 使用 a of stack 会导致嵌套元素以相反的顺序返回。我相信手动实现单向链表将保持 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 回答
0

我提出了一个不同的版本，不使用产量：

    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 回答
-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
}

这应该会返回所有分支节点和叶节点。如果您只想返回叶节点，请删除第一个收益返回。

回答您的问题，是的，它是一个算法原语，因为您肯定需要调用 node.Children()，并且您肯定需要对每个孩子调用 child.Descendants()。我同意有两个“foreach”循环似乎很奇怪，但第二个实际上只是继续整体枚举，而不是迭代孩子。

于 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 回答