C言語関係掲示板

過去ログ

No.1287 reallocで構造体データを順に保存したいがうまくいかない

[戻る] [ホームページ]
No.17064

reallocによる動的メモリ確保におけるデータの追加
投稿者---jun(2004/10/04 15:01:43)


はじめまして。単純な問題ですがどうしても困っていることがあります。
まず、
typedef struct seiseki {
       UINT    id;                /* ID           */
       UCHAR   name[NAME_MAX];    /* 名前         */
       USHORT  j_point;           /* 国語点数     */
       USHORT  m_point;           /* 数学点数     */
       USHORT  e_point;           /* 英語点数     */
       USHORT  t_point;           /* 三教科合計点 */
       struct seiseki *next;            /* 次データへのポインタ */
} SEISEKI;

という構造体を定義しています。そして、このSEISEKI型のデータをreallocによって確保したメモリに保存したいのですが、どうしてもうまくいきません。私の認識では、このSEISEKI型の変数1つで一人分のデータとするとまず、
SEISEKI *indata,*dummy;
indata =dummy= NULL;
このようにポインタ変数を定義しておいて、
indata=(SEISEKI *)realloc(indata,sizeof(SEISEKI)*(1));
とすると、まず一人分のデータが保存できるメモリが確保できて、
dummy=indata+(0);
として、このdummyのアドレスに一人目のデータを保存し、次に、
indata=(SEISEKI *)realloc(indata,sizeof(SEISEKI)*(2));
として、
dummy=indata+(1);
のアドレスに二人目のデータを保存できると考えているのですが、どこか間違っている点はございますでしょうか??

データの入力などは関数を用いていますが、ここでは、割愛させていただいています。メモリをmallocで確保すると動作するので。

コンパイラはLSI C-86を使用しております。
どうぞよろしくお願いします。



No.17066

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---REE(2004/10/04 15:20:29)


>どうしてもうまくいきません。

どううまくいかないのかを説明してください。

以下は推測です。

reallocでは、確保されているメモリの位置が変わることがあります。その場合、それまでその中の要素をさしていたポインタの値は不正になります。
もし、リスト構造を使用している場合、先頭の要素を指すポインタや、全ての要素のnextを修正しなければなりません。
リスト構造であれば、データが連続している必要は無いわけですので、要素ごとに新たにmallocをすることをお勧めします。




No.17070

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---jun(2004/10/04 15:43:40)


>どううまくいかないのかを説明してください。
どうもすみませんでした。うまくいかないのは、データがうまく入らないということでしたのですが、おそらく、推測されたとおりだと思います。データを一人ぶんずつファイルから読み込んで番号順にリスト構造にしているのですが、メモリをreallocによって確保しているため、一人ずつデータを読み込む過程でメモリの位置が変化し以前のリスト構造のポインタの値が不正になっていたんですね。どうもありがとうございました。

ここで、もうひとつ質問なのですが、
私がなぜmallocで実現できていることをreallocで行おうかとしているかと言うと、freeでメモリを開放する時にmallocでメモリを確保していると、私のこの場合読み込んだデータの件数回freeを行わなくてはいけなく、データの件数が多くなった場合、処理が遅くなるのではないかと感じたからです。私の場合、
<pre>void free_data(SEISEKI *p){/*データの先頭のアドレスを渡す*/

SEISEKI *dummyp;
while (p!=NULL){/*最後のデータのnextにはNULLが入っている*/
dummyp=p->next;
free(p);
p=dummyp;
}

return 1;
}
</pre>

という関数を使ってメモリを開放しているのですが。

この場合、毎回mallocでメモリを確保するか、reallocで再確保していくか、freeの処理を考慮に入れるとどちらが速いでしょうか??
また、mallocでメモリを確保するとぶつ切り状態でメモリが確保されるのでしょうか??できるだけ、以前に確保した次の領域が空いていればそこに確保するなどの考慮はなされるのでしょうか??



No.17071

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---シャノン(2004/10/04 15:54:10)


>この場合、毎回mallocでメモリを確保するか、reallocで再確保していくか、freeの処理を考慮に入れるとどちらが速いでしょうか??

レコード長は固定な様ですから、あらかじめファイルを通読しておき、
レコードが何件あるかを数えて、その分一気に malloc するのが最速
ではないでしょうか。
ファイルヘッダにレコード数なんか入ってると better ですね。

>また、mallocでメモリを確保するとぶつ切り状態でメモリが確保されるのでしょうか??できるだけ、以前に確保した次の領域が空いていればそこに確保するなどの考慮はなされるのでしょうか??

C 言語の規格では、そこまで規程されてはいないでしょう。
そのような実装がなされる可能性も、なされない可能性もあります。


No.17078

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---jun(2004/10/04 17:02:57)


そうですか。どうもありがとうございました。実に勉強になりました。

もうひとつ質問させてください。では、リスト構造にせずにデータの数だけ、reallocでメモリを確保して(一行読み込むごとに以前のメモリをreallocで拡張しながら)、単純にファイルから読み込んで保存していくとします。データの構造は先ほど書きましたが
typedef struct seiseki {
       UINT    id;                /* ID           */
       UCHAR   name[30];       /* 名前         */
       USHORT  j_point;           /* 国語点数     */
       USHORT  m_point;           /* 数学点数     */
       USHORT  e_point;           /* 英語点数     */
       USHORT  t_point;           /* 三教科合計点 */
} SEISEKI;

です。読み込むファイルの形式はCSV形式で、例えば

2,松井 大輔,89,78,67,234
3,中村 俊輔,34,75,49,158
4,中田 英寿,89,90,99,278
10,小野 伸二,89,78,73,240

のようになっているとします。(実際はもっと件数があります。)ここで、読み込む時には単純に上のデータから順に読み込んで、reallocでメモリを拡張して、拡張した部分に保存していき、画面に出力する際には、番号や各教科の点数でソートしてから、画面に表示したい場合、どのような種類のソートが適切で高速でしょうか??



No.17089

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---YuO(2004/10/05 01:07:43)


>読み込む時には単純に上のデータから順に読み込んで、reallocでメモリを拡張して、拡張した部分に保存していき、
>画面に出力する際には、番号や各教科の点数でソートしてから、画面に表示したい場合、
>どのような種類のソートが適切で高速でしょうか??

とりあえずqsortを使うのがよいでしょう。
配列の要素番号をソートすればよいので,高速なソートを使う必要はないです。


No.17080

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---REE(2004/10/04 17:06:19)


>この場合、毎回mallocでメモリを確保するか、reallocで再確保していくか、freeの処理を考慮に入れるとどちらが速いでしょうか??

毎回mallocの方が速いでしょう。
reallocで再確保する場合、内部でfreeとmallocの処理が行われ、
さらに、データのコピーも行います。

>また、mallocでメモリを確保するとぶつ切り状態でメモリが確保されるのでしょうか??できるだけ、以前に確保した次の領域が空いていればそこに確保するなどの考慮はなされるのでしょうか??

ぶつ切りでも連続していても、影響は無いと思いますが、なにが心配なのでしょうか?
もし、メモリの断片化を心配しているのであれば、reallocで再確保される方が、断片化しやすくなります。



No.17081

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---jun(2004/10/04 17:23:19)


どうもありがとうございます。mallocのほうが早いんですね。。。

>ぶつ切りでも連続していても、影響は無いと思いますが、なにが心配なのでしょうか?
データの数が多くなり、何回もmallocするとメモリを開放する際、(データがリスト構造でつながっているので、以前書いたとおり)
<pre>UCHAR free_data(SEISEKI *p){/*データの先頭アドレスを与える*/

SEISEKI *dummyp;
while (p!=NULL){
dummyp=p->next;/*nextに次のデータのアドレスが入っているので*/
free(p);
p=dummyp;
}

return 1;
}
</pre>

という関数で開放するのですが、これに時間がかかるのではないかという懸念があります。どうでしょうか??一発でfreeしたいがためにmallocをreallocするのは馬鹿らしいですか??

>もし、メモリの断片化を心配しているのであれば、reallocで再確保される方が、断片化しやすくなります。

これは、どのような理由からでしょうか??


No.17085

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---RAPT(2004/10/05 00:08:36)


reallocでメモリの再確保を行なうとして、そのメモリの連続性について、
自分でメモリ管理を行なうということですか?

そんな面倒なこと、OSにまかせて、自分はデータの管理にだけ気を配れば
いいと思いませんか?

1.最初の空きメモリ
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

2.メモリを5確保(■×5)
■■■■■□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

3.メモリを10、realloc(★×10)
■■■■■□□□□★★★★★★★★★★□□□□□□□□□□□□□□□□
  ↓
□□□□□□□□□■■■■■■■■■■□□□□□□□□□□□□□□□□

4.メモリを15、realloc(★×15)
□□□□□□□□□■■■■■■■■■■□★★★★★★★★★★★★★★★
  ↓
□□□□□□□□□□□□□□□□□□□□■■■■■■■■■■■■■■■

5.メモリを20、realloc(★×20)
★★★★★★★★★★★★★★★★★★★★■■■■■■■■■■■■■■■
  ↓
■■■■■■■■■■■■■■■■■■■■□□□□□□□□□□□□□□□


と、これはあくまでイメージですが、mallocされ、freeされたメモリブロックが
上記のイメージ図のようにすぐに再利用されるとは限りません。

速度が必要なら、スタックにアロケートするとか、mallocで継ぎ足した方が
早いかと思います。
→ある一定サイズのメモリブロックを確保し、そのポインタを保持。
→不足したら、また別個のメモリブロックを確保し、そのポインタを保持。
とか。



No.17090

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---hermit(2004/10/05 07:42:01)


昔のMSCの様なreallocですね(^^;
現状の VC++ もそうなってますか?
(伝統だから、まだそうかもしれないな・・・)

他の処理系の realloc では、追加できるメモリーエリアが後ろにあれば
そのままエリアを拡大する仕様のものが多いようですが、
MSC は、必ず移動するので、その系は注意が必要ってことかな。


No.17088

Re:reallocによる動的メモリ確保におけるデータの追加
投稿者---YuO(2004/10/05 01:07:41)


>どうもありがとうございます。mallocのほうが早いんですね。。。

条件次第です。
mallocの方が早いこともあれば,reallocの方が早いこともあります。
実際の環境で試してみないことにはわかりませんし,状況がかわれば結果も異なります。

末尾への追加のみが発生しているようなので,
ちゃんと考えられた実装であればmallocを使ったリスト構造より,
reallocを使った配列の方が早くなるのではないかと思います。
#std::vectorとstd::listにおける末尾への追加のコストから類推。


>という関数で開放するのですが、これに時間がかかるのではないかという懸念があります。どうでしょうか??

実際にやってみてはどうですか?

プロファイルせずに感覚で「時間がかかるだろう」と考える処理は,
実は大した問題でないことはよくあります。

実際にやってみて時間がかかっているのであれば,
原因を探って高速化するのは意味がありますが,
やりもせずに時間がかかるだろうと思って色々探っても,
見当違いの処理を行うだけになりますよ。


>>もし、メモリの断片化を心配しているのであれば、reallocで再確保される方が、断片化しやすくなります。
>これは、どのような理由からでしょうか??

実装次第なので何とも……。

領域の後ろが空いていればそのまま伸ばすことも可能なわけで,
そういう状態&実装の場合はreallocの方が断片化が起きません。

これも実際にやってみて,どうなるかを調べてみた方がよいでしょう。