0

この関数は、より小さな配列でうまく機能します。しかし、「int」の非常に大きな配列が与えられると、惨めに失敗します。調べたところ、内部ループのすべての変数を保持するのに十分なスペースを割り当てることができないため、メモリ不足のスタックが問題の原因であることがわかりました。では、これを回避するにはどうすればよいでしょうか。

void subsetSums(vector<int> arr, int l, int r, int sum=0) { 
    if(l > r){
        cout << sum << ", ";
        return;
    }
    subsetSums(arr, l+1, r, sum+arr[l]);
    subsetSums(arr, l+1, r, sum);

}
    int main(){
    vector<int> arr(500000, 1);
    subsetSums(arr, 0, arr.size()-1);
    return 0;
}

今のところ、これを「ホットフィックス」したいだけです。そうすれば、この問題の最適解が見つかるかもしれません。

4

1 に答える 1

0

次の 3 つのことを行うことができます。

  1. スタックの使用量を減らす

関数呼び出しごとにベクトルと 'r' のコピーを渡す代わりに、これらがまったく変更されない場合は、これらをメンバーとして持つ構造体を作成し、構造体への参照をパラメーターとして渡すことができます。グローバル変数を恐れていない場合は、これらの変数をグローバルにして、関数パラメーターとして渡さないようにすることができますが、その場合、スタイル ポリスがあなたを連れ去ろうとするかもしれません。

また、一部のコンパイラでは、最適化されていないビルドまたはデバッグ ビルドがより多くのスタックを使用するため、リリース ビルド ターゲットを試すか、最適化をオンにしてください。

  1. スタックサイズを増やす

これを行う方法は、コンパイラとプラットフォームによって異なります。gcc と Linux を使用してこれを行う方法は次のとおりです。GNU コンパイラでのコンパイル中に Linux で C++ アプリケーションのスタック サイズを変更する

  1. 非再帰アルゴリズムへの変更

多くの場合、再帰的なアルゴリズムと同じことを行うための、より高速でメモリ効率の良いアルゴリズムがあります。この場合は明らかです。これは通常、実際の製品コードで行うことです。

于 2019-07-23T03:59:30.873 に答える