☰

主流のOSにおけるC/C++プログラムの最大スタックサイズ 質問する

tag-icon • tag-icon c++ c operating-system stack-memory
主流のOSにおけるC/C++プログラムの最大スタックサイズ 質問する

100 x 100 配列で DFS を実行したいです。(配列の要素はグラフ ノードを表すものとします) 最悪の場合、再帰関数呼び出しの深さは最大 10000 になり、各呼び出しで最大 20 バイトかかる可能性があります。これは実現可能であり、stackoverflow の可能性はありますか?

C/C++ のスタックの最大サイズはどれくらいですか?


1) Windows上のcygwin
2) Unixの両方でgccを指定してください

一般的な制限は何ですか?

ベストアンサー1

Visual Studio では、デフォルトのスタック サイズは 1 MB だと思います。そのため、再帰の深さが 10,000 の場合、各スタック フレームは最大で約 100 バイトになり、DFS アルゴリズムには十分なはずです。

Visual Studio を含むほとんどのコンパイラでは、スタック サイズを指定できます。一部の (すべての?) Linux フレーバーでは、スタック サイズは実行可能ファイルの一部ではなく、OS の環境変数です。その後、 でスタック サイズを確認しulimit -s、たとえば で新しい値に設定できますulimit -s 16384。

こちらはリンクgcc のデフォルトのスタック サイズを使用します。

再帰なしの DFS:

std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

おすすめ記事