递归枚举的逻辑缩减
本文关键字：枚举 递归 | 更新日期: 2023-09-27 18:36:06
我发现自己经常编写递归IEnumerable<T>迭代器来实现与 XContainer.Descendants 提供的相同的"后代"模式。我一直实现的模式如下，给定一个带有名为 Children 的单级迭代器的Foo类型：
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 */ }
您可以使用显式堆栈（而不是隐式使用线程的调用堆栈）来存储正在使用的数据。 这甚至可以推广到一个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);
}
}
因为这不是递归的，因此不会不断创建状态机，所以它的性能会好得多。
旁注，如果您想要呼吸优先搜索，只需使用Queue而不是Stack即可。 如果您想要最佳优先搜索，请使用优先级队列。
要确保同级姐妹的返回顺序与从 selacor 的顺序返回的顺序相同，而不是相反，只需向 childrenSelector 的结果添加一个Reverse调用。
我认为这是一个很好的问题。对于为什么需要两个循环，我最好的解释是：我们需要认识到每个项目都转换为多个项目（自身及其所有后代）的事实。这意味着我们不映射一对一（如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);
}
采用IEnumerable<Foo>的版本必须在 root.Children() 上调用。
我认为所有这些重写都暴露了看待问题的不同方式。另一方面，它们都有两个嵌套循环。循环可以隐藏在帮助程序函数中，但它们仍然存在。
我会用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;
}
}
不是递归的，所以不应该吹堆栈。您总是在列表的前面为自己添加更多工作，因此您可以实现深度优先遍历。
Damien_the_Unbeliever 和 Servy 都提出了一种算法版本，该算法避免使用一种或另一种类型的集合来创建递归调用堆栈。Damien 使用 List 可能会导致列表开头的插入性能不佳，而 Servy 使用 of stack 将导致嵌套元素以相反的顺序返回。我相信手动实现单向链表将保持 Servy 的性能，同时仍然以原始顺序返回所有项目。唯一棘手的部分是通过迭代根来初始化前ForwardLink。为了保持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);
}
}
我提出了一个不同的版本，不使用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;
}
}
为了扩展我的评论，这应该有效：
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。孩子（），你肯定需要叫孩子。每个子项上的后代（）。我同意有两个"foreach"循环似乎很奇怪，但第二个循环实际上只是继续整体枚举，而不是迭代子级。
试试这个：
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())