如何"展开""递归"结构

Question

不知道如何调用它,但是说你有一个类似下面的类:

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

Answer 1

我不相信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),那么你将永远递归.

Answer 2

我找到了这个问题,因为我正在寻找并考虑类似的解决方案 - 在我的案例中创建一个高效IEnumerable<Control>的ASP.NET UI控件.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到递归堆栈中的当前深度).