.NET 性能 : Deep Recursion vs Queue

Question

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

遍历图形的最佳方式是什么？

一个。排队“步骤”以避免深度递归

或

B.一个 DFS(深度优先搜索)，它可能会深入许多层次，有时会有一个“深”堆栈跟踪。

我想我要问的问题是:在 .NET 中执行会导致“深度”堆栈跟踪的 DFS 是否会影响性能？如果是这样，命中率是多少？我是否可以通过排队本应在 DFS 中递归处理的步骤来更好地使用某些 BFS？

抱歉，如果我不清楚。谢谢。

Answer 1

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

当我说通常时，这意味着有几个异常(exception):

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

您是否应该实现迭代或递归树遍历并不取决于 .NET 运行时是否会在一种情况下为您提供比另一种情况更好的性能，但您应该根据 Big-O(时间和内存)，特别是如果它用于大树。我不认为我需要提醒你递归解决方案的堆栈溢出的可能性，鉴于我们现在的位置......虽然 Tailcall 优化是可能的。

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