有一些递归算法可以很快填满堆栈。一种解决方案是使堆栈显式化,从而将算法转变为迭代算法。
但我注意到,显式堆栈会使算法变慢很多(这可能不会让我感到惊讶)。是否有任何通用的 C++ 准则可以使显式堆栈更快?它们是否有可能比原始的递归算法运行得更快?
编辑:我为其编写的显式堆栈的函数如下。我还粘贴了迭代代码。由于某种原因,使用 std::vector
而不是 std::stack
更快,这非常令人惊讶。
// A(m, n) = n + 1 if m = 0
// = A(m - 1, 1) if m > 0 and n = 0
// = A(m - 1, A(m, n - 1)) if m, n > 0
int A(int m, int n, long& iterations,
std::vector<std::pair<int, int> >& stack)
{
stack.push_back(std::make_pair(m, n));
long result = 0;
bool result_available = false;
while (stack.size() > 0)
{
iterations += 1;
if (result_available) {
stack.back().second = result;
result_available = false;
}
m = stack.back().first;
n = stack.back().second;
stack.pop_back();
if (m == 0) {
result = n + 1;
result_available = true;
}
else if (m > 0 && n == 0) {
stack.push_back(std::make_pair(m - 1, 1));
}
else if (m > 0 && n > 0) {
stack.push_back(std::make_pair(m - 1, n));
stack.push_back(std::make_pair(m, n - 1));
}
}
return result;
}
最佳答案
尝试尽可能少地从堆中分配内存。速度很慢。
消除尾递归 - 对于它们,您不需要递归调用。它看起来不像递归解决方案那么优雅,但速度更快。有关如何完成此操作的示例,请搜索斐波那契实现。有 2 种递归变体和一种非递归变体。
使用显式堆栈不会更快,因为函数调用和通过堆栈传递参数是最快的汇编指令,因为它们经常使用。
关于c++ - 使显式堆栈算法更快,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13049321/