c# - 将 LINQ Select 中的递归方法组转换为迭代方法

Question

我有一个看起来像这样的类:

public class SourceObject
{
    public string Id { get; set; }
    public List<SourceObject> Children { get; set; }

    public SourceObject()
    {
        Children = new List<SourceObject>();
    }
}

如您所见，它有一个属性，其中包含同一类的更多实例的列表。我为这个类处理的数据意味着 child 的数量在运行时之前是未知的，并且生成的对象图的整体“深度”也是未知的。

我需要创建一个从 SourceObject 的对象图到 DestinationObject 的类似形状图的“映射”(类似于 AutoMapper 从一个对象映射的方式给另一个)。

我有一个方法可以从我的源图映射到我的目标图，但是，这个方法使用递归:

// Recursive way of mapping each Source object to Destination
public static DestinationObject MapSourceToDestination(SourceObject source)
{
    var result = new DestinationObject();
    result.Id = source.Id;
    result.Children = source.Children.Select(MapSourceToDestination).ToList();
    return result;
}

当源对象图的大小不太大或不太深时，此方法工作正常，但是，当源对象图非常大时，此方法将抛出 StackOverflow 异常。

我已经设法创建此函数的替代版本，它使用类似于 this answer 中描述的技术删除递归并将其替换为队列/堆栈。 ) 但是，我注意到 Queue/Stack 也可以变得非常大，我不确定我的实现是否最有效。

是否可以将递归函数转换为纯粹使用源对象图迭代的函数(即删除递归，理想情况下，使用队列/堆栈)？

Answer 1

我仍然相信大小为树的最大深度的堆栈是最优的通用解决方案。

但有趣的是，数据结构和具体过程包含所有必要的信息来实现转换，而无需显式堆栈，仅基于Children.Count。让我们看看我们需要什么:

(1) 是否有更多的源 child 需要处理:source.Children.Count != target.Children.Count)

(2) 哪个是下一个要处理的源 child :source.Children[target.Children.Count]

(3)当前处理的子索引是多少:target.Children.Count - 1

请注意，上述规则适用于处理过程中的任何级别。

实现如下:

public static DestinationObject MapSourceToDestination(SourceObject source)
{
    // Map everything except childen
    Func<SourceObject, DestinationObject> primaryMap = s => new DestinationObject
    {
        Id = s.Id,
        // ...
        Children = new List<DestinationObject>(s.Children.Count) // Empty list with specified capacity
    };

    var target = primaryMap(source);

    var currentSource = source;
    var currentTarget = target;
    int depth = 0;
    while (true)
    {
        if (currentTarget.Children.Count != currentSource.Children.Count)
        {
            // Process next child
            var sourceChild = currentSource.Children[currentTarget.Children.Count];
            var targetChild = primaryMap(sourceChild);
            currentTarget.Children.Add(targetChild);
            if (sourceChild.Children.Count > 0)
            {
                // Move one level down
                currentSource = sourceChild;
                currentTarget = targetChild;
                depth++;
            }
        }
        else
        {
            // Move one level up
            if (depth == 0) break;
            depth--;
            currentSource = source;
            currentTarget = target;
            for (int i = 0; i < depth; i++)
            {
                int index = currentTarget.Children.Count - 1;
                currentSource = currentSource.Children[index];
                currentTarget = currentTarget.Children[index];
            }
        }
    }

    return target;
}

唯一棘手(并且部分效率低下)的部分是向上移动的步骤(这就是通用解决方案需要堆栈的原因)。如果对象有 Parent 属性，它会很简单:

currentSource = currentSource.Parent;
currentTarget = currentTarget.Parent;

由于缺少此类属性，为了找到当前源项和目标项的父项，我们从根项开始，向下移动通过当前正在处理的索引(请参阅 (3))，直到达到所需的深度。