２次元配列の動的確保について

質問

共分散行列を２次元配列に格納しようとしているのですが、
その要素は、左下半分と右上半分が同じになるため
対角要素と、どちらか半分だけを格納してメモリを節約したいと考えています。
以下のように動的確保することでメモリは節約できているでしょうか？

if( (a = (double **)malloc(sizeof(double *) * (N) ))==NULL ){
fprintf(stderr, "error malloc for a\n");
exit(0);
}

for( i=0; i<NN; i++ ){
if( ( a[i] = (double *)malloc(sizeof(double) * (i+1) ))==NULL ){
fprintf(stderr, "error malloc for a\n");
exit(0);
}
}

*節約しない場合は、i+1 が　N　になります。

確保できているのなら、どのように参照すればいいのでしょうか？データの並び（？）は、a[0][0],a[1][0],a[1][1],a[2][0],a[2][1],a[2][2],,,というように並んでいるでしょうか？
例えば、a[0][1]を参照しようとすると、シグメンテーションフォルトなど起こりうるでしょうか。必要であれば、上プログラム内Nは、3000程度と考えてください。
そして、もし他にメモリを節約する上で良い方法があれば、ご教授していただけたらと思います。

よろしくお願い致します。

回答No.5

ranx · ベストアンサー

> a[0][0]の次にa[1][0]が、a[1][1]の次にa[2][0]が、、、、a[i][i]の次に、a[i+1][0]が並んでいると考えてよろしいですか？
ということですが、
inthefloiさんの
> データの並びは、予想しているとおりに確保されています。
については、私は意見が異なります。ここら辺私が勉強したのはずい分と前の話ですから
ひょっとすると最近は違うのかもしれませんが、
私が見たmalloc()のコードでは、一回のアロケーション毎に管理データを作っていました。
ですから、このアルゴリズムでは、
　a[0] = malloc(...)
　a[1] = malloc(...)
　a[2] = malloc(...)
　　　:
という具合に呼んだら
　|a[0]管理データ|a[0][0]|a[1]管理データ|a[1][0]|a[1][1]|a[2]管理データ|a[2][0]|a[2][1]|a[2][2]|
とう具合に配置されると思います。
したがって、単純にデータのみが並んでいると考えることはできないということになります。
情報が古い分、「自信なし」です。

お礼

ご回答ありがとうございます！
上のinthefloiさんのご回答でも、そのようにおっしゃってますので、
自信持っていただいてよさそうです？

管理データの長さは、、と考えるよりも
素直に１次元配列に入れた方が良さそうですね。

勉強になりました。

回答No.6

noname#30727

＞データの並びについてですが、a[0][0]の次にa[1][0]が、a[1][1]の次にa[2][0]が、、、、a[i][i]の次に、a[i+1][0]が並んでいると考えてよろしいですか？

すいません。並びの部分をちゃんと読まずに、コードを見て、予想どおりと書いてしまいました。
malloc を繰り返した場合、それぞれが確保したメモリは連続しません。連続している事を前提とされるのでしたら、最初に ranx さんが書かれている通り、要素数 N*(N+1)/2 で malloc するしかありません。

その後、あえてテーブルを作るのであれば、参照するときのインデックス計算をあらかじめするだけです。

t = (double *)malloc(sizeof(double) * (N * (N + 1) / 2));
a = (double **)malloc(sizeof(double *) * N);
for (i = 0; i < N; i++) {
a[i] = &t[i * (i + 1) / 2];
}

お礼

三度の登場ありがとうございます！

一度にたくさんの質問を詰め込んでしまったので
そのような誤解をされるのも不思議ではありませんね。。
以後気を付けたいと思います。

後半部のコードは参考にさせていただきます。
また、質問出してたらよろしくお願いします！

回答No.4

noname#30727

＞#define COVXY(a,x,y)((x<=y?a[y][x]:a[x][y]))
＞では、まずいでしょうか？

これは、私の趣味の問題かもしれません。
COVXYを左辺値としても有効にしたかったという事です。
右辺値としてだけ使うのならば、それでいいと思います。

＞もし参照した場合はどうでしょうか。

OSやコンパイラによって結果は違うでしょうが、参照する場所が、OSから見て参照できない場所であれば、OSに怒れれるでしょう。ランタイムに悪影響があるか、何事もないか、別の場所が書き換えられなど、何が起こるかはわかりません。

＞その他の疑問に関しては肯定していただけたと考えてよろしいですか？

データの並びは、予想しているとおりに確保されています。
メモリの節約という意味では微妙です。malloc の仕様や、OSの仕様によりますが、ほとんどの場合、節約はできているでしょう。
ranx さんが書かれているように、１度で確保すれば、確実に節約できます。

お礼

再度ご回答くださいましてありがとうございます！

確かに、おっしゃる定義の仕方の方が便利ですね。
勉強になりました。

データの並びについてですが、a[0][0]の次にa[1][0]が、a[1][1]の次にa[2][0]が、、、、a[i][i]の次に、a[i+1][0]が並んでいると考えてよろしいですか？
補足になるのですが、配列aを、並列プログラム内で、Bcast（全ジョブに転送）しようとしているのですが、その時に、先頭アドレスと、要素数を引数として与えなければなりません。この場合、データの並びが考えている通りだとすれば、要素数は、N*(N+1)/2で良いと思うのですが、いかがでしょうか。

もしよろしければ、もう少しお付き合いしていただけたら感激です。

回答No.3

ranx

最後の部分のみ訂正。
a = (double*)malloc(sizeof(double)*n*(n+1)/2))
#define COVXY(a,x,y) ((x<=y)?a[(x)*((x)-1)/2+(y)]:a[(y)*((y)-1)/2+(x)])

お礼

ご回答ありがとうございます。
お礼が遅くなり申し訳ありませんでした。

分かっていただけていたらいいのですが、
for文内のＮＮ⇒Ｎに訂正です。

ここで、ranxさんがおっしゃるnはＮと考えていいですね。
一次元配列でとる方が安全ですか。
プロフェッショナルな方は、
２次元配列はあまり用いないのでしょうか？

回答No.2

ranx

とりあえず、Cとして（C++ではないものとして）お答えします。

> メモリは節約できているでしょうか？

一般的に言えば節約できていると推測されますけれど、アロケーションのアルゴリズムに依存するので、
確定的なことは言えないと思います。

> どのように参照すればいいのでしょうか？
inthefloiさんのやり方が合理的だと思います。

> データの並び（？）は、a[0][0],a[1][0],a[1][1],a[2][0],a[2][1],a[2][2],,,というように並んでいるでしょうか？
a[2][0],a[2][1],a[2][2]などはこの順に並んでいます。が、a[1][1]の次にa[2][0]が来るという保証はありません。

> a[0][1]を参照しようとすると、シグメンテーションフォルトなど起こりうるでしょうか
起こりえます。

> もし他にメモリを節約する上で良い方法があれば
a = (double**)malloc(sizeof(double)*n*(n+1)/2))
#define COVXY(a,x,y) a[(x)*((x)-1)/2+(y)]
なんてやり方も考えられますね。

回答No.1

noname#30727

＞a[0][1]を参照しようとすると

パフォーマンスの低下は仕方ないですが、アクセスの仕方を工夫してやればいいのじゃないかと思います。

#define COVXY(a, x, y) (*(x <= y ? &a[y][x] : &a[x][y]))

COVXY(a, 10, 32) = 1.0;

お礼

ご回答ありがとうございます。

この場合、
#define COVXY(a,x,y)((x<=y?a[y][x]:a[x][y]))
では、まずいでしょうか？

おっしゃるように工夫をすればa[0][1]などを参照せずに済むとは思うのですが、
もし参照した場合はどうでしょうか。
その他の疑問に関しては肯定していただけたと考えてよろしいですか？