.net - .NET 性能：深度递归与队列

Question

我正在编写一个需要遍历大型对象图的组件，有时深度为 20-30 级。

走图的最高效方式是什么？

A. 将“步骤”排入队列以避免深度递归

或者

B. 一个 DFS（深度优先搜索），它可能会深入许多级别，并且有时会有一个“深”的堆栈跟踪。

我想我要问的问题是：在 .NET 中执行 DFS 是否会导致“深度”堆栈跟踪的性能下降？如果是这样，打击是什么？通过排队在 DFS 中递归处理的步骤，我会更好地使用一些 BFS 吗？

对不起，如果我不清楚。谢谢。

Answer 1

运行时中没有什么会导致深堆栈中的代码执行比浅调用堆栈中的慢。没有理由这样做，因为通常代码执行不会触发堆栈遍历。

当我说通常时，这意味着有几个例外：

• 安全/证据检查通常会遍历调用堆栈以确定当前的安全上下文
• 当然，抛出和捕获异常（你不想在树遍历中这样做，除了中止它）

您是否应该实现迭代或递归树遍历并不取决于 .NET 运行时是否会在一种情况下为您提供比另一种情况更好的性能，但您应该根据 Big-O（时间和内存）做出决定，特别是如果它用于大树。考虑到我们所处的位置，我认为我不需要提醒您使用递归解决方案可能会导致堆栈溢出……尽管可以进行尾调用优化。

在你为你的树和遍历目的 Big-O 明智地选择了最快的遍历之后，你可以开始担心优化你的实现了。

Answer 2

请参阅为什么 .NET/C# 不针对尾调用递归进行优化？. 显然，.NET 在 x86-64 上执行尾递归优化，所以如果这是您的架构，并且您的代码适合这种优化，请坚持使用递归。

Answer 3

您正在混合两个在某种程度上应该分开的概念：

• 数据结构的迭代与使用调用堆栈成为您的结构的递归函数。

• 广度优先与深度优先遍历。

它们是连接的，只要递归函数倾向于实现深度优先。但是，在使用队列时，没有什么限制您使用广度优先。

如果您想要广度优先，请使用 FIFO 队列，如果您想要深度优先，请使用 LIFO 队列。无论哪种方式，您都可以节省函数调用开销（可能相当小，如果队列上的方法没有被优化器内联，调用方法可能会更昂贵）和系统调用堆栈上的堆栈空间使用。