我怎样才能加速这个递归函数
本文关键字:递归函数 加速 | 更新日期: 2023-09-27 18:30:17
我有一个递归函数,可以从大约 2000 条记录的 IEnumerable 构建节点列表。该过程目前大约需要 9 秒才能完成,并且已成为一个主要的性能问题。该函数用于:
a) 按层次结构对节点进行排序
b) 计算每个节点的深度
这是一个精简的示例:
public class Node
{
public string Id { get; set; }
public string ParentId { get; set; }
public int Depth { get; set; }
}
private void GetSortedList()
{
// next line pulls the nodes from the DB, not included here to simplify the example
IEnumerable<Node> ie = GetNodes();
var l = new List<Node>();
foreach (Node n in ie)
{
if (string.IsNullOrWhiteSpace(n.ParentId))
{
n.Depth = 1;
l.Add(n);
AddChildNodes(n, l, ie);
}
}
}
private void AddChildNodes(Node parent, List<Node> newNodeList, IEnumerable<Node> ie)
{
foreach (Node n in ie)
{
if (!string.IsNullOrWhiteSpace(n.ParentId) && n.ParentId == parent.Id)
{
n.Depth = parent.Depth + 1;
newNodeList.Add(n);
AddChildNodes(n, newNodeList, ie);
}
}
}
重写它以最大限度地提高性能的最佳方法是什么?我已经尝试了 yield 关键字,但我不确定这会让我得到我正在寻找的结果。我也读过有关使用堆栈的文章,但我发现的示例都没有使用父 ID(它们使用子节点列表代替),所以我对如何处理它有点困惑。
递
归不是导致性能问题的原因。真正的问题是,在每次递归调用AddChildNodes
时,你遍历整个列表以找到当前父级的子级,所以你的算法最终是O(n^2)。
要解决此问题,您可以创建一个字典,该字典为每个节点 ID 提供其所有子节点的列表。 这可以通过列表的单次传递来完成。 然后,您可以从根 Id (") 开始,递归访问其每个子级(即"深度优先遍历")。这将只访问每个节点一次。所以整个算法是O(n)。代码如下所示。
调用GetSortedList
后,排序结果以result
为单位。请注意,如果您愿意,您可以在GetSortedList
中创建children
和result
局部变量,并将它们作为参数传递给 DepthFirstTraversal
。但这不必要地减慢了递归调用的速度,因为这两个参数在每个递归调用上始终具有相同的值。
您可以使用堆栈摆脱递归,但性能提升可能不值得。
Dictionary<string, List<Node>> children = null;
List<Node> result = null;
private void GetSortedList()
{
var ie = data;
children = new Dictionary<string,List<Node>>();
// construct the dictionary
foreach (var n in ie)
{
if (!children.ContainsKey(n.ParentId))
{
children[n.ParentId] = new List<Node>();
}
children[n.ParentId].Add(n);
}
// Depth first traversal
result = new List<Node>();
DepthFirstTraversal("", 1);
if (result.Count() != ie.Count())
{
// If there are cycles, some nodes cannot be reached from the root,
// and therefore will not be contained in the result.
throw new Exception("Original list of nodes contains cycles");
}
}
private void DepthFirstTraversal(string parentId, int depth)
{
if (children.ContainsKey(parentId))
{
foreach (var child in children[parentId])
{
child.Depth = depth;
result.Add(child);
DepthFirstTraversal(child.Id, depth + 1);
}
}
}