0

我有一个应用程序可以最大限度地利用递归函数。基本上它是一个字符串解析器，它使用哈希映射作为其数据结构。我们正面临一个问题，其中复杂和长字符串的性能受到严重打击。我们不敢碰散列函数，害怕回归。观察到的是大量递归函数调用，我们怀疑这会导致性能问题。该应用程序是基于 VS 2008 开发的 C++(Windows)

堆栈保留大小和堆栈提交大小的增加会提高应用程序性能吗？或者它会避免我们遇到但不经常遇到的内存不足问题吗

4

2 回答 2

3

堆栈保留大小和堆栈提交大小的增加会提高应用程序性能吗？

几乎可以肯定，它不会对性能产生明显的影响。

它会避免我们遇到的内存不足问题吗？

不，如果您用完堆栈空间，那么您会收到堆栈溢出错误而不是内存不足。

于 2012-11-21T09:39:51.803 回答
1

堆栈使用本身不会显着影响性能。进行函数调用（恰好是递归调用）的成本可能是哈希函数运行时的重要组成部分，如果是这样，迭代版本可能会更快。

在 C++ 中最大限度地使用递归可能效率低下并且也有些危险，因为堆栈大小是有限的。例如，

size_t hash(const std::string &s) {
    if (s.size() == 0) return 0;
    return s[0] + 31 * hash(s.substr(1));
}

由于两个原因（调用开销和分配字符串负载的可能性），这可能效率低下，并且在传递足够长的字符串时也会因堆栈溢出而崩溃。

我们不敢碰散列函数，害怕回归。

即使除了性能之外，散列映射中使用的散列函数也应该被隔离以便于维护——一份代码副本，并且在其他任何地方都没有使用任何特定散列算法的假设。

如果你能隔离散列函数，那你就敢碰它。这样，您可以轻松比较不同的哈希算法和不同的实现（包括递归/非递归），看看它们是否解决了您的整体性能问题。

如果你不能隔离散列函数，那么你就学到了关于代码设计的一课。但是，您可能仍然可以替换它，并在不知道代码是否仍然正确的情况下了解它是否会影响性能。如果您可以使其更快，那么值得尝试使其正确（通过修改其余代码以隔离散列函数然后替换它）。如果你能想出的最好的散列函数不是更快，那么它是否正确并不重要，因为没有理由使用它。

于 2012-11-21T09:54:20.157 回答