2

スタックをすぐにいっぱいにする再帰アルゴリズムがいくつかあります。1 つの解決策は、スタックを明示的にして、アルゴリズムを反復的なものにすることです。

しかし、明示的なスタックを使用すると、アルゴリズムがかなり遅くなることに気付きました (これはおそらく驚くべきことではありませんでした)。明示的なスタックを高速化するための一般的な 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

  1. ヒープからメモリをできるだけ割り当てないようにしてください。とても遅いです。

  2. 末尾再帰を排除します-それらの場合、再帰呼び出しは必要ありません。再帰的なソリューションほどエレガントには見えませんが、より高速です。これがどのように行われるかの例については、Fibonacci implementations を検索してください。2 つの再帰的バリアントと非再帰的バリアントがあります。

  3. 関数呼び出しとスタックを介したパラメーターの受け渡しは、非常に頻繁に使用されるため、最速のアセンブラー命令の一部であるため、明示的なスタックでは高速になりません。

于 2012-10-24T14:53:02.850 に答える
1

最近のバージョンの gcc を使用している幸運なユーザー向けに、別の解決策があります-fsplit-stack。

分割スタックは新しいアイデアではありません。Lisp は当時それを持っていました... それは単に、コンパイラが完全なスタックを前もってセットアップする必要のないプログラムを作成し、代わりに必要に応じてそれを拡張できることを意味します。したがって、スタックは不連続になります。

もちろん、これにはすべて (またはほとんど) のライブラリをこの新しいスタック メカニズムに適合させる必要があります (したがって、ソフトウェア スタック全体を再コンパイルする必要があります)。それに気付かないライブラリでもスタック オーバーフロー例外が発生する可能性がありますが、そのようなライブラリで深く再帰的な関数を使用しないようにすれば、それほど問題にはなりません。

このメカニズムにより、利用可能なメモリがある限り、スタックはプログラムに合わせて拡張されます。

于 2012-10-24T14:43:57.360 に答える