セグメンテーションエラーが消えない

Question

引数nから値を求める簡単なプログラムを作成しましたが、
以下のプログラムでセグメンテーション違反がでます。
大きな数字の用いた時にコアダンプが生じます。
lldbを用いてデバッグしたところ、
func関数の返り値のところでbreakしていました。
ここまではわかったのですが、ここから先の解決方法がわかりません。
ご回答よろしくおねがいいたします。

#define ffor(i,a,b) for (int i=(a);i<(b);i++)
#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#define SIZE 10000001
#define MOD 1000000007
#define INF 100000000
using namespace std;

int memo[SIZE];
int s = 10007;
int func(int n){
	if(n == 3) return 1;
	if(n <= 2) return 0;
	if(memo[n] != 0) return memo[n];

	return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

int main(){
	int n;
	cin >> n;

	cout << func(n) << endl;

	return 0;
}

追記
記入不足があり申し訳有りません。
SIZE以上の入力が出た時にコアダンプが出るという点は承知しております。
入力値が10^4程度だとエラーが出ないのですが、10^6くらいの値からエラーが出ます。

Answer 1

今回の場合は再起呼び出し回数が多すぎることが最初の原因なので、そっちのパッチが大事かなと思います。コールスタックは有限なので…数字を増やすとリニアに呼び出し回数が増えるタイプの再帰呼び出しは考え方を変えないといけないかなと。

幸い、今回の設計の場合は隙間なくnの値が取られるので、再帰的じゃなくて、下から計算すればいいんじゃないかと思います。

#define SIZE 10000001
using namespace std;

int memo[SIZE];
int s = 10007;
int func(int n){
    if(n == 3) return 1;
    if(n <= 2) return 0;
    if(memo[n] != 0) return memo[n];

    return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

// ここから
int position = 4;
int func_invoker(int n){
    for(; position < n; position++)
    {
        func(position);
    }
    return func(n);
}
// ここを追加

int main(){
    int n;
    cin >> n;

    // func_invokerに処理を渡す
    // cout << func(n) << endl;
    cout << func_invoker(n) << endl;

    return 0;
}

この関数は現状のサンプルでは参照透過なので、予め決まったnの値に対応する辞書を生成しておくことによってメモリスペースと計算量をトレードオフにできます。
ファイルに全部書き出しておいてそこから値を引っ張ってきてもいいですし、等間隔に辞書で計算結果をもっておくことによって計算量の最大を固定することもできます。

Comments

[waya]

このような書き方で解決もできるんですね！勉強になります。
一応確認なのですが、
これはposition=4から計算する事でmemo[n]に値が保存されて、それを利用して計算できるから
スタックオーバーフローが起きずに済むと言う解釈で大丈夫でしょうか？

[haru666]

そうです。
このメソッドは再帰呼び出しをしていますが、バッファ(memo[n])に計算結果を記録していて、記録済みの値の呼び出し時はネストがありません。そのため、下から呼び出していくと常に呼び出しの深さは１回にしかならないため、スタックが消費されません。

こういう書き方ができるかどうかは計算内容にもよりますが、nが整数値の場合は比較的やりやすいです。

[waya]

なるほど！わざわざ例まで出していただき、ありがとうございました！
簡単なプログラムですが、色々と勉強になりました・・・。考えてプログラムを書けるように頑張ります。

Answer 2

memo[n]って初期化していないが何が入っているのだろうか
それと、終わるまでがすごい長そうだけれど、スタックがすごい積まれそう。
そしてスタックオーバーフローにならないだろうか

tacsheavenさんも書いていますが、int memo[SIZE];は予定通り確保できない可能性がありますね
昔、自分もかなり大きな配列用意しようとしてうまくいかなかった記憶があります。
そこにアクセスした瞬間落ちたような(...ちょっと記憶があいまいです)

Comments

[waya]

グローバル変数として定義している場合は0に初期化されたと思います。
競技プログラミングのためにSIZEで値を定義してこの値で毎回プログラムを書いていましたが、やはり動的確保をした方が良さそうですね・・・。
スタックオーバーフローを起こしているようなので、別の書き方で取り組んでみます。
アドバイスありがとうございます！

[tacsheaven]

昔の SPARC 上の HP-UX で、確保してないはずの領域にアクセスできた、って逆の例もありました。
※int buffer[10] なのに buffer[15] とかに正常にアクセスできる

あとはまったのだと、確保する領域の計算を間違えて malloc(0) を発行したとき……これ、null が返ってこない（正常に確保できたように見える）くせに、アクセスした瞬間に segmentation fault 起こすという嫌な動きをしてくれたことが。

[waya]

逆の例、初めて聞きました。笑
やはり他の人のエラーを聞くと非常に勉強になりますね・・・！
配列の扱いでしょっちゅうエラーを起こしてしまうので慣れるまで頑張ります。

[tacsheaven]

あれ、HP-UX だったか Solalis だったか曖昧（汗　メモリ確保がブロック単位に切りあがってたようで、ブロックの末尾までは使える、という豪快なメモリ管理で（ｗ

[ardin]

そうか。グローバル変数だと0初期化でしたか。

>tacsheaven さん
確かにうまくいくこともありますね。
ただいつも上手くいくとは限らず、別のところでコード書き換えた際にだめになることもあり、
原因特定に時間がかかることも・・・
(つまり、たまたま空いていたのでアクセスしてもエラーにならないだけで、
次のビルド(またはコンパイル)時に埋まってしまってアウト)

Answer 3

スタックオーバーフローを起こしているのではないでしょうか。スタック領域の上限サイズは処理系にもよりますが、100万階層もの再帰呼び出しは多すぎのように思います。

Comments

[waya]

別の書き方で取り組んでみます。呼び出しが深すぎたようです・・・・。
アドバイスありがとうございましす！

Answer 4

Segmentation Fault が出たならば、たいていは配列の添え字オーバーです。
と考えると、そもそも memo[10000001] が確保しきれてない可能性があります。

単純計算で、int = 4byte の環境だと仮定して、38MB 超ですか。
ヒープ領域に確保されているはずですが、ヒープがそこまで大きくないのかもしれませんね。
malloc で動的に確保するようにして、失敗するかどうか確認してみるのもいいかもしれません。

（追記）
あともう一つ、スタック領域が足りない可能性がありますか。
memo[] は初期状態で 0 クリアされているでしょうから、その場合 func(X)を考えると、再帰の段数はX-3 になるはずです。（最初に func(X-1) を呼び出し、さらにそこから func(X-2) を呼び出し…となる）

Comments

[waya]

わかりやすい回答ありがとうございます！
スタックオーバーフローを起こしているようで、別の書き方で取り組んでみます。
アドバイスありがとうございます！

Answer 5

配列として定義する変数の長さの最大はOSやコンパイラによってまちまちです。10000001という配列の長さは確保できる保証はないです。一般的に巨大な配列を定義する場合、配列変数で定義するのではなく、動的メモリ確保でその大きさ分の領域を確保します。

int* memo;
int s = 10007;
int func(int n){
    if(n == 3) return 1;
    if(n <= 2) return 0;
    if(memo[n] != 0) return memo[n];

    return memo[n] = (func(n-1)+func(n-2)+func(n-3))%s;
}

int main(){
    int n;
    cin >> n;
    memo = new int[n]();

    cout << func(n) << endl;

    delete[] memo;
    return 0;
}

Comments

[waya]

競技プログラミングのために毎度この書き方で使用しておりましたが、
普段プログラムを書くときは動的確保を行なった方が良さそうですね・・・。徐々に直していきたいと思います。
アドバイスありがとうございます。

Answer 6

こんにちは。

大きな数字の用いた時にコアダンプが生じます。

SIZE以上の数字を指定するとコアダンプになってもおかしくないです。
nにはSIZE(10000001)未満の値を指定すれば大丈夫なはずです。

Comments

[waya]

記入漏れがあり申し訳有りません。
SIZE以下の入力でセグメンテーション違反が起きてしまいます。
例えば10^6でエラーが生じます。

[Chironian]

了解です。やってみました。スタックオーバーフローと思います。
再帰呼び出しが深くなりすぎてスタックが足りなくなっているようです。

再帰呼び出しは深さがあまり深くならないことを保証できるケースでのみ使用した方がよいです。
なので、このケースでは頑張ってループに展開した方がよいと思います。

[waya]

毎度わかりやすい回答ありがとうございます！
スタックオーバーフローを起こしているみたいですね・・・。書き方を変えて取り組んでみます。
最近なんとなくプログラミングの練習をして来たツケが回って来てエラーに苦労しています・・・。地道に穴を埋めていけるように頑張ります。

[Chironian]

ツケと言うよりは、これは誰もが一度は通る道かも。初期の頃に経験できたのであれば幸運ですよ。
頑張ってください。

Answer 7

大きな数字ってどのくらい? SIZEを超えてたらふっ飛ぶのはアタリマエだけど。

Comments

[waya]

10^6位からエラーが出ます。例えば999999でエラーが出ます。