2

有一些递归算法可以很快填满堆栈。一种解决方案是使堆栈显式化，从而将算法转变为迭代算法。

但是我注意到拥有显式堆栈会使算法变得相当慢（这可能不应该让我感到惊讶）。是否有任何使显式堆栈更快的通用 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;
}
4

2 回答 2

1

对于最新版本 gcc 的幸运用户，还有另一种解决方案：-fsplit-stack.

拆分堆栈并不是一个新想法，当时 Lisp 就有它……它只是意味着编译器创建了一个程序，该程序不必预先设置其完整堆栈，而是能够根据需要对其进行扩展。因此堆栈变得不连续。

当然，这需要所有（或大多数）库都适应这种新的堆栈机制（因此需要重新编译整个软件堆栈）。忽略它的库可能仍会创建堆栈溢出异常，如果您避免在此类库中使用深度递归函数，这不是什么大问题。

使用这种机制，只要您有可用内存，堆栈就会增长以适应您的程序。

于 2012-10-24T14:43:57.360 回答
1

  1. 尝试尽可能少地从堆中分配内存。它很慢。

  2. 消除尾递归——对他们来说，你不需要递归调用。它看起来不像递归解决方案那样优雅，但它更快。有关如何完成此操作的示例，请搜索 Fibonacci 实现。有 2 个递归变体和一个非递归变体。

  3. 显式堆栈不会更快，因为函数调用和通过堆栈传递参数是一些最快的汇编指令，因为它们经常使用。

于 2012-10-24T14:53:02.850 回答