動的メモリ利用の目的

情報分野を学習中の大学生です。
C言語の動的メモリ利用について質問させて頂きます。

先日、基数ソートを実装している際に、動的メモリを利用しました。
ソートデータ数の都合上（最大10桁100万個）、確保すべきバッファ領域が膨大だったためです。
※実際に必要だったバッファ：buf[0][0] - buf[9][1000000-1]

ここで私が動的メモリを利用した動機は「バッファ領域でかすぎるからメモリ圧迫するし動的メモリのほうがいいかな？」といったものです。

コードを書いているうちに、この認識の正誤と、どういったケースで動的メモリを扱うべきか気になりました。

御回答宜しくお願いします。

No.3 ベストアンサー 回答者： hanabutako 回答日時： 2012/07/20 01:22

> 「バッファ領域でかすぎるからメモリ圧迫するし動的メモリのほうがいいかな？」

その理由で動的なメモリーの割り当てを利用するというのは、誤りです。

普通、それのことはバッファ領域ではなく、スタックというように思います。バッファという言葉には何かのデータの一時置き場という意味しかないので、スタック上に取るのもヒープ上に取るのも自由です。少量のものはスタックにとり、大量のものはヒープにとるのが普通でしょう。

ただ、ヒープに取るものは必ずしも動的にメモリーを割り当てる必要はありません。例えば、グローバル変数に取れば自動的にヒープに容量が割り当てられます。
たしかに、一般にスタックの伸びしろのほうがヒープよりも少なめになっていますが、必ずしもそれが正しいとはいえません。例えば、Unix系のOSだとlimitなどで簡単にスタックやヒープのサイズを変更できます。もちろん、動的に割り当てられるメモリーもヒープ上に取られますので、そういう使い方も可能ではありますが。

> どういう時に動的なメモリー割り当てを利用するか？

配列と変数と式だけのToyプログラムを書いているうちは特に動的なメモリーの割り当ては必要ないと思います。

実用的なプログラムは普通のユーザーから様々な入力をとり、それを複数の関数で処理します。スタック上に取られている変数だと、その関数を抜けたら開放されてしまうので、複数の関数で処理を行うのが大変困難です。そして、どれだけの容量を確保したらいいかもユーザーが具体的に指示するまでわかりません。例えば、ソートをする場合でも10個のデータをソートするのか10万個のデータをソートするのかで必要なメモリーは大いに違います。ヒープに予め確保しておくと、無駄ですし、想定よりも大きなデータが来た時に処理できません。(ちなみに、普通のOSはデマンドページングをするので、10万個分のメモリーをヒープにとって、10個しか来なくても、実際にメモリーを使う量は微々たるものですが)

また、モジュール化/カプセル化とデータ抽象化を学ぶと動的なメモリーの割り当ての必要性に気づくでしょう。この場合、あなたが書いたライブラリーが呼ばれた時に一度にすべての処理をするのは不可能なので、ライブラリーの利用者の指示に従ってすこしずつ処理を進めますが、その中間状態を保存しておくのにスタックは不向きです。また、その場合、どれだけメモリーを用意したらいいのかわからないので、ライブラリーの利用者が特定の関数を呼び出した時に動的なメモリーの確保を行います。
例えば、ファイルの入出力に使われるfopenは内部で動的なメモリーの確保を行っています。利用者は同時に読み書きするファイルの個数分fopenを呼び出します。そして、ファイルの読み書きをするfscanfやfprintfの実行に必要な様々なデータはその動的に確保されたメモリーに入っています。
複数の人で開発している場合も同じ事です。他の人が自分が書いた部分でどの程度メモリーを必要とするか不明なので、必要な分だけ動的に割り当てるようにします。

mallocなどで動的にメモリーが割り当てられる場合、その領域は重複しないので、確保したコードの専用領域として使えます。一つのプログラムが同時に複数の処理を行うマルチスレッドプログラムでは、一つ一つのスレッド (処理を行う一つ一つの単位) が別々の処理を行います。この時、スレッドに動的に割り当てられたメモリーは御行儀よく使えばそのスレッドからしか読み書きされないので、他のスレッドのことを考えずにプログラムを書けるようになります。
これが、逆に動的に割り当てられたメモリーではなく、グローバル変数になっていると、他のスレッドが変更を加える可能性があるので処理が終わるまでロックを取るなどをする必要があり、面倒くさく、性能にも悪い影響を与えます。

と、説明してきましたが、まとめると次の3つですね。
- 複数の関数が同一のデータを取り扱い、プログラムの動作によって必要となるメモリーの量や種類が多いに変わるとき
- データの抽象化をしたいとき
- マルチスレッドのプログラムを書いていて、グローバル変数を使いたくないとき

No.2 回答者： hashioogi 回答日時： 2012/07/19 18:25

JPEG画像をビットマップに変換するような処理を考えます。

デジカメの種類によって画像サイズが異なりますから予め固定的な領域を確保しておくわけにはいきません。最大でこのサイズまでしか扱わないという制限を設けておけば別ですが。

No.1 回答者： Tacosan 回答日時： 2012/07/19 16:10

100万個ともなれば動的にメモリを確保すべきだとは思うけど, 連結リストを使えばそんなにメモリをたくさん必要ともしない.