logo标签列表

如何“展开”一个“递归”结构

c#recursionienumerable
38

不确定怎么称呼它，但是假设你有一个类看起来像这样：

class Person
{
    public string Name;
    public IEnumerable<Person> Friends;
}

你现在有一个人，想要递归地“展开”这个结构，以便最终得到一个没有重复的所有人的列表。
你会怎么做？我已经做了一些看起来可以工作的东西，但我很好奇其他人会如何做，特别是是否有内置于Linq中的东西可以巧妙地解决这个小问题 :)
以下是我的解决方案：
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    // Stop if subjects are null or empty
    if(subjects == null)
        yield break;

    // For each subject
    foreach(var subject in subjects)
    {
        // Yield it
        yield return subject;

        // Then yield all its decendants
        foreach (var decendant in SelectRecursive(selector(subject), selector))
            yield return decendant;
    }
}

以下是使用示例：

var people = somePerson.SelectRecursive(x => x.Friends);
我似乎漏掉了什么...如果有循环，它会停止吗？ - Kobi
@Kobi：这可以通过 if(!subjects.Any()) yield break; 来完成。 - Oliver
@Oliver：不会的。只有当主题列表为空时，它才会停止。所以我想我实际上可以完全跳过那部分，因为它不会有任何影响... - Svish
1
@Kobi：不，你没有错过任何东西。它永远不会停止:p 当我制作它时，我使用的东西永远不会有任何循环，所以没有做任何关于它的事情。如果需要，我可能会使用HashSet来跟踪我已经访问过的主题。 - Svish
移除了 !subjects.Any() 部分，因为它并没有真正起到好的作用，反而让事情变得更加混乱 :p - Svish
7个回答
45

我不认为 LINQ 中有任何内置的方法可以做到这一点。

使用递归的方式存在一个问题 - 你最终会创建大量的迭代器。如果树很深，这可能会非常低效。 Wes Dyer 和 Eric Lippert 都在博客中写过这方面的内容。

你可以通过消除直接递归来消除这种低效性。例如：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects,
    Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
    {
        yield break;
    }

    Queue<T> stillToProcess = new Queue<T>(subjects);

    while (stillToProcess.Count > 0)
    {
        T item = stillToProcess.Dequeue();
        yield return item;
        foreach (T child in selector(item))
        {
            stillToProcess.Enqueue(child);
        }
    }
}

这也会改变迭代顺序 - 它变成了广度优先而不是深度优先; 重写它仍然是深度优先是棘手的。我还改变了它不使用Any() - 这个修订版本不会评估任何序列超过一次，这在某些情况下可能很方便。这确实有一个问题 - 它将需要更多的内存，因为排队。我们可以通过存储迭代器队列而不是项来减轻这个问题，但我不确定...这肯定会更加复杂。

值得注意的一点（当我查找博客文章时ChrisW也指出了这一点：）- 如果您的朋友列表中存在任何循环（即如果A有B，B有A），那么您将永远递归。

3
只有类型可变时才能这样做。否则，您可以使用HashSet<T>来存储已经访问过的项。 - Jon Skeet
3
@Eric：这很有可能......虽然这样你会先按深度优先顺序获取 每个集合内的最后一个元素，所以它仍然不符合原始顺序 :( 再次强调，我相信稍加努力就可以做到 - 但我的大脑现在无法思考这个问题。 - Jon Skeet
2
啊，是的，我完全明白你的意思。有趣的巧合是，我刚刚在检查我们用来确定发射类顺序的递归算法，想知道它是否可以被迭代。将这个算法变成迭代式就会出现这个问题；如果仅按照深度优先，则会颠倒给定命名空间中类发射顺序。使用Reverse()序列操作符进行适当的修复应该很容易。 - Eric Lippert
1
@Eric：这是一个较旧的问题，但我有一个保留顺序的解决方案。今天我为自己的项目苦苦思索时意识到 - 只需将枚举器本身推入堆栈即可。请参见我的答案（为后人添加）。 - Kevin Brock
1
@JonSkeet 那么，一个队列的堆栈可能是更好的权衡。 - user3638471
显示剩余14条评论
15
我找到了这个问题，因为我正在寻找并思考类似的解决方案——在我的情况下创建一个有效的 ASP.NET UI 控件的 IEnumerable<Control> 。我之前使用的递归 yield 是快速的，但我知道它可能会有额外的成本，因为控件结构越深，花费的时间就越长。现在我知道这是 O(n log n)。
这里提供的解决方案提供了一些答案，但正如评论中讨论的那样，它确实改变了顺序（这不是 OP 关心的）。我意识到，为了保留 OP 给出的顺序以及我需要的顺序，既不能使用简单的 Queue（如 Jon 所用），也不能使用 Stack，因为所有父对象都将首先被生成，然后才是任何子对象（或反之亦然）。
为了解决这个问题并保持顺序，我意识到解决方案只需将Enumerator自身放在一个Stack中。要使用 OP 的原始问题，看起来像这样：
public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector)
{
    if (subjects == null)
        yield break;

    var stack = new Stack<IEnumerator<T>>();

    stack.Push(subjects.GetEnumerator());

    while (stack.Count > 0)
    {
        var en = stack.Peek();
        if (en.MoveNext())
        {
            var subject = en.Current;
            yield return subject;

            stack.Push(selector(subject).GetEnumerator());
        }
        else 
        {
            stack.Pop().Dispose();
        }
    }
}

在这里，我使用 stack.Peek 来避免将相同的枚举器重新推回到堆栈中，因为这可能是更频繁的操作，期望该枚举器提供多个项。

这样做会创建与递归版本中相同数量的枚举器，但新对象可能会比将所有主题放入队列或堆栈并继续添加任何后代主题少。这是 O(n) 时间，因为每个枚举器都是独立的（在递归版本中，对一个 MoveNext 的隐式调用会执行当前深度中子枚举器的 MoveNext）。

4
当你从栈中弹出枚举器后，应该将其处理掉。 - Logerfo
1
注意：“将枚举器本身放在堆栈上”-这样做是可行的，但代价是创建大量枚举器，每个递归节点一个。与Jon的解决方案相比，后者不会创建相同的枚举顺序，但避免了对所有后代进行GetEnumerator调用。一种优化方法是让节点（主题）类实现ICollection，以便可以执行if（node.Count> 0）stack.Push（selector（node）。GetEnumerator（））;这避免了在所有“叶子”节点上创建枚举器。 - ToolmakerSteve
@ToolmakerSteve foreach 使用 GetEnumerator（编译器生成）；而 new Queue(IEnumerable<T>) 本身使用 foreach 来将每个元素入队，因此我认为这两者具有相同数量的 GetEnumerator 调用。 - Kevin Brock
@KevinBrock - 我评论中的重要部分是if测试。这可以避免在每个叶子节点（没有子节点，不需要枚举）上执行任何工作（不要执行foreach或enumerator）。 - ToolmakerSteve
3
您也可以使用非递归的方法，像这样：
  HashSet<Person> GatherAll (Person p) {
     Stack<Person> todo = new Stack<Person> ();
     HashSet<Person> results = new HashSet<Person> ();
     todo.Add (p); results.Add (p);
     while (todo.Count > 0) {
        Person p = todo.Pop (); 
        foreach (Person f in p.Friends) 
           if (results.Add (f)) todo.Add (f);
     }
     return results;
  }

这应该可以正确地处理循环。我从单个人开始，但您可以轻松扩展为从人员列表开始。

2

这是一个实现，它可以：

  • Does a depth first recursive select,
  • Doesn't require double iteration of the child collections,
  • Doesn't use intermediate collections for the selected elements,
  • Doesn't handle cycles,

  • Can do it backwards.

    public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
{
    return new RecursiveEnumerable<T>(rootItems, selector, false);
}

public static IEnumerable<T> SelectRecursiveReverse<T>(this IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector)
{
    return new RecursiveEnumerable<T>(rootItems, selector, true);
}

class RecursiveEnumerable<T> : IEnumerable<T>
{
    public RecursiveEnumerable(IEnumerable<T> rootItems, Func<T, IEnumerable<T>> selector, bool reverse)
    {
        _rootItems = rootItems;
        _selector = selector;
        _reverse = reverse;
    }

    IEnumerable<T> _rootItems;
    Func<T, IEnumerable<T>> _selector;
    bool _reverse;

    public IEnumerator<T> GetEnumerator()
    {
        return new Enumerator(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    class Enumerator : IEnumerator<T>
    {
        public Enumerator(RecursiveEnumerable<T> owner)
        {
            _owner = owner;
            Reset();
        }

        RecursiveEnumerable<T> _owner;
        T _current;
        Stack<IEnumerator<T>> _stack = new Stack<IEnumerator<T>>();


        public T Current
        {
            get 
            {
                if (_stack == null || _stack.Count == 0)
                    throw new InvalidOperationException();
                return _current; 
            }
        }

        public void Dispose()
        {
            _current = default(T);
            if (_stack != null)
            {
                while (_stack.Count > 0)
                {
                    _stack.Pop().Dispose();
                }
                _stack = null;
            }
        }

        object System.Collections.IEnumerator.Current
        {
            get { return Current; }
        }

        public bool MoveNext()
        {
            if (_owner._reverse)
                return MoveReverse();
            else
                return MoveForward();
        }

        public bool MoveForward()
        {
            // First time?
            if (_stack == null)
            {
                // Setup stack
                _stack = new Stack<IEnumerator<T>>();

                // Start with the root items
                _stack.Push(_owner._rootItems.GetEnumerator());
            }

            // Process enumerators on the stack
            while (_stack.Count > 0)
            {
                // Get the current one
                var se = _stack.Peek();

                // Next please...
                if (se.MoveNext())
                {
                    // Store it
                    _current = se.Current;

                    // Get child items
                    var childItems = _owner._selector(_current);
                    if (childItems != null)
                    {
                        _stack.Push(childItems.GetEnumerator());
                    }

                    return true;
                }

                // Finished with the enumerator
                se.Dispose();
                _stack.Pop();
            }

            // Finished!
            return false;
        }

        public bool MoveReverse()
        {
            // First time?
            if (_stack == null)
            {
                // Setup stack
                _stack = new Stack<IEnumerator<T>>();

                // Start with the root items
                _stack.Push(_owner._rootItems.Reverse().GetEnumerator());
            }

            // Process enumerators on the stack
            while (_stack.Count > 0)
            {
                // Get the current one
                var se = _stack.Peek();

                // Next please...
                if (se.MoveNext())
                {
                    // Get child items
                    var childItems = _owner._selector(se.Current);
                    if (childItems != null)
                    {
                        _stack.Push(childItems.Reverse().GetEnumerator());
                        continue;
                    }

                    // Store it
                    _current = se.Current;
                    return true;
                }

                // Finished with the enumerator
                se.Dispose();
                _stack.Pop();

                if (_stack.Count > 0)
                {
                    _current = _stack.Peek().Current;
                    return true;
                }
            }

            // Finished!
            return false;
        }

        public void Reset()
        {
            Dispose();
        }
    }
}
1

递归总是很有趣的。也许你可以简化你的代码：

public static IEnumerable<T> SelectRecursive<T>(this IEnumerable<T> subjects, Func<T, IEnumerable<T>> selector) {
    // Stop if subjects are null or empty 
    if (subjects == null || !subjects.Any())
        return Enumerable.Empty<T>();

    // Gather a list of all (selected) child elements of all subjects
    var subjectChildren = subjects.SelectMany(selector);

    // Jump into the recursion for each of the child elements
    var recursiveChildren = SelectRecursive(subjectChildren, selector);

    // Combine the subjects with all of their (recursive child elements).
    // The union will remove any direct parent-child duplicates.
    // Endless loops due to circular references are however still possible.
    return subjects.Union(recursiveChildren);
}

使用这种方法，将会比原来的代码产生更少的重复项。但是可能仍有重复项导致无限循环，联合操作只能防止直接父子之间的重复。

而且，项目的顺序将与你的不同 :)

编辑： 将最后一行代码改为三个语句，并增加了一些文档说明。

有趣...不过有点难读，呵呵。顺序其实并不重要，所以不用担心 :p - Svish
我已将单个语句拆分为子结果，这可能会使其更易于阅读/理解。基本上，我用LINQ替换了您的for循环。当然，您可以大胆尝试，将此方法简化为单行语句 :) - Yvo
1

使用聚合扩展...

    List<Person> persons = GetPersons(); 
    List<Person> result = new List<Person>(); 
    persons.Aggregate(result,SomeFunc);

    private static List<Person> SomeFunc(List<Person> arg1,Person arg2)
    {
    arg1.Add(arg2)
    arg1.AddRange(arg2.Persons);
    return arg1;
    }
我之前就在考虑这个问题。能否提供一些示例代码？ - Svish
有趣。但这个方法无法处理循环关系，是吗？ - Svish
你可以添加一个简单的 if(arg1.Contains(arg2))。 - Chen Kinnrot
除非我读错了代码，否则它只会下降一级 - 它不会递归到任意深度。我相信它等同于 foreach (var person in persons) { result.Add(person); result.AddRange(person.Persons); }。 - ToolmakerSteve
0

虽然在可能有大量数据时拥有IEnumerable很棒，但值得记住的是递归添加到列表的经典方法。

这可以非常简单，就像这样（我省略了选择器；只是演示递归添加到输出列表）：

class Node
{
    public readonly List<Node> Children = new List<Node>();

    public List<Node> Flatten()
    {
        var all = new List<Node>();
        Flatten(ref all);
        return all;
    }

    public void Flatten(List<Node> all)
    {
        all.Add(this);

        foreach (var child in Children)
            child.Flatten(all);
    }
}

用法：

Node rootNode = ...;
...
var all = rootNode.Flatten();
我有点困惑，为什么一个声望很高的SO用户建议在这里根本不需要使用ref。 ref给了Flatten方法自由更改参数为其他内容，而这显然在这里没有用到。 - ViRuSTriNiTy
1
@ViRuSTriNiTy - 谢谢 - 你是正确的。我不记得为什么使用了 ref，但在这里肯定是不需要的。（也许我是从允许“null”参数的代码中改编而来，在那种情况下用新实例替换了它。）已修复。 - ToolmakerSteve
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接