計算機言語 I 第 14 回
ポインタへのポインタ , ポインタの配列
この資料: http://www.math.u-ryukyu.ac.jp/~suga/gengo/2021/14.pdf
レポートへのツッコミ
データの入れ替えを利用したバブルソートで,seiseki_t型の41個の配列を整列させるときに,「構造体 は,代入によるコピーが可能」ということを使うとソースはすっきりとします.
void swap(seiseki_t *x, seiseki_t *y) {
seiseki_t temp;
temp = *x;
*x = *y;
*y = temp;
}
という関数swap()を用意しておくと, int型の値を入れ替える時と同様に,
swap(&x, &y);
で,seiseki_t型の変数, x, yの値が入れ替わります.
ただし,構造体のコピーは, CPUの動作としては, 各メンバ単位でひとつひとつコピーしますので,動作が 遅くなります. したがって,上のようなプログラムは, できる限り書かないようにしますし,そのための工夫の 方法を述べるのが, 今回の授業の目的のひとつです.
ポインタへのポインタ
「ポインタ型変数」も識別子である. という認識は重要です. 識別子なら, C の言語規則から, プログラム実 行中にはそのアドレスが定まるのです.
表題のポインタへのポインタとは,ポインタ型変数を指すポインタのことです. 当然,この値を変数値として 持つ変数を使うことができ,ポインタ型変数のアドレスを保持する変数が考えられます. これは,現実のプログ ラムでは,「ポインタ型変数の配列」の先頭要素を指すポインタとしてよく利用されます. 実際, 教科書の例で は,行列を2重配列ではなく,「行ベクトルの並び」として実現する方法が書かれています.
このような変数を考える理由は,主に次の 2つです.
• 2重配列のような変数を動的に確保するのに都合が良い.
• ある種のプログラムの実行速度を改善する.
教科書には,上の例が書かれています. 例えば,m×n行列の計算をするプログラムを書くとして,「m, n(行 列のサイズ)が実行時にしか決まらない」とします. これをプログラムする一つの方法は,m×nの一次元配
列をmalloc()で確保して,それを行列のように扱うプログラムを書くことです. しかし, これはプログラム
が複雑になるとともに,下にある実行速度に影響するプログラムになったりします.
そこで,教科書にあるように,n次元の行ベクトルがm個並んだものとして, 行列を定めます. すなわち,ポ インタ型変数の配列 p[m]を準備し,p[i]は,第i+ 1行の行ベクトルを指すポインタとするのです. この時, 識別子pは配列変数p[m]の先頭要素p[0] へのポインタを保持しますから,ポインタへのポインタとなるわ けです.
このようにして書かれたのが, 教科書,プログラム 10.5です. プログラムの中で,sizeof(double *)の部 分は,double型ポインタの大きさの意味になります. double型の大きさではありません.
教科書,プログラム10.6は,あまり意味のない工夫なので, 飛ばしてください. 教科書,プログラム 10.7は, 実行してみてください. ポインタ配列のアドレス増の様子は,重要です.
ーーーーーーーーーーーーー
さて,上で挙げたポインタ配列を使うふたつめの理由について述べます.
「ある種のプログラムの実行速度を上げる」例として,「要素の入れ替え」があります. 例えば,連立一次方程 式を解くプログラムを書くとします(工学系ではよくある話). 連立一次方程式の解法は, 皆さんが1年次の時 に線型代数学で学んだ「掃き出し法」をプログラムします. 解の公式であるクラメルの公式はプログラミング では全く使えません. 掃き出し法のひとつの操作に「行を入れ替える」というものがあります. これを2次元 配列で実装すると, とても遅いプログラムになりますが,上のようなポインタ配列で実装すると,コンピュータ の速度は劇的に速くなります.
前回のレポート問題について : 「ポインタのポインタ」の応用
上の事を前回のレポート問題で実装してみます. seiseki_t型の構造体を入れ替えるのではなく, それらへ のポインタの指す値を入れ替えることにより,整列を実行するわけです.
プログラムでは, data[41]はseiseki_t型へのポインタを保持するポインタ変数の配列にします. 従っ て,各個人のデータを読むたびに, seiseki_t型のためのメモリをmalloc()で確保し,そこへのアドレスを
data[i]に代入していきます. 整列アルゴリズムは,単純なバブルソートにしました.
注意して欲しいのは,構造体へのポインタに対する矢印演算子 -> です. aが何らかの構造体へのポインタ なら, a -> memberは,aが指す構造体内のmemberという変数値を参照します.
また,要素を入れ替えるswap()では,まさにポインタへのポインタが引数となります.
#include <stdio.h>
#include <stdlib.h>
typedef struct seiseki{
char number[10];
int score;
} seiseki_t;
void swap(seiseki_t **x, seiseki_t **y);
void sort(seiseki_t *x[]);
int main() {
FILE *fp;
seiseki_t *data[41]; /* seiseki_t へのポインタ 41 個の配列 */
int i;
if ((fp=fopen("input.data","r"))==NULL){
fprintf(stderr, "ファイルを開けません.\n");
exit(1);
}
for (i=0; i< 41; i++){
if ((data[i] = (seiseki_t *) malloc(sizeof(seiseki_t))) == NULL){
fprintf(stderr, "メモリを確保できません.\n");
exit(1);
}
fscanf(fp, "%s%d", data[i]->number, &(data[i]->score));
}
fclose(fp);
sort(data);
for (i=0; i< 41; i++){
printf("%s %d\n", data[i]->number, data[i]->score);
}
return 0;
}
void swap(seiseki_t **x, seiseki_t **y) {
seiseki_t *temp;
temp = *x;
*x = *y;
*y = temp;
}
void sort(seiseki_t *data[]) /* 単純なバブルソート */
{
int i, j;
for (i=40; i > 0; i--){
for (j=0; j < i ; j++){
if (data[j]->score < data[j+1]->score){
swap(&data[j], &data[j+1]);
} } } }
ライブラリ関数qsort()
今の形のコンピュータが実用に使われるようになった当初から, データの整列処理に多く利用されることが 判明しました. そのため,様々な整列アルゴリズムが開発されています.
整列アルゴリズムは,次の観点で比較されています.
• 整列のための計算量(整列の速さ)
• 整列に必要なメモリ.
• 安定性(同じ値であったとき,元のデータの並びを変化させる可能性があるか否か.)
これらすべで良い結果が得られるアルゴリズムは,いまだに発見されていません(おそらく無いと思います が,無い事を証明できるかは知らない.). しかし,概ね効率がいいと知られているアルゴリズムがいくつかあり, その中でもHoare(ホア)が1960年に開発したquicksortというものがあります. 特別に速い整列方法(デー タの形によっては, 特別な方法がある)がない場合とか,データサイズが大きすぎて 1次記憶に収まりきらな いなどを除けば,これを利用するのが普通です. quicksort の特徴は,次です.
• データは 1次記憶上に全てあることを想定し,データサイズ程度の記憶容量しか必要としない.
• 安定ではない.
• 平均的な計算量はO(nlogn)である.(最悪はO(n2). バブルソートは,これが常にO(n2))
• 再帰的なプログラムのため,データ量が少ないと,再帰呼び出しのオーバーヘッドで却って遅くなる.
C では, 標準ライブラリ関数として, qsort()というものが用意されています. その内容は, 必ずしも
quicksort の実装ではなく処理系依存ですが, 多くの場合, quicksortの最後の欠点を少し改善したプログラム
が実装されているようです. (ソート数が少なくなった時点で,再帰をやめて別のアルゴリズムを使うなど).
qsort()の使い方は,マニュアルコマンドでわかりますが,その読み方を少し解説します.
Bash4-4$ man 3 qsort
次のプログラムは, qsort()を用いて,seiseki_t data[41];をscore の小さい並べ替えた例です. 比 較関数compareについては,別途解説します.
compare()にカウンタを入れて,私のデータで計測したところ, 166回のデータ比較で並び替えが終了しま
した. バブルソートだと, 41×40
2 = 820回のデータ比較が必要ですから, qsort()の方が効率よく整列を実
行している事がわかります.
#include <stdio.h>
#include <stdlib.h>
typedef struct seiseki{
char number[10];
int score;
} seiseki_t;
int compare(const void *x, const void *y);
int main() {
FILE *fp;
seiseki_t *data[41];
int i;
if ((fp=fopen("data.txt","r"))==NULL){
fprintf(stderr, "Cannot open file\n");
exit(1);
}
for (i=0; i< 41; i++){
if ((data[i] = (seiseki_t *) malloc(sizeof(seiseki_t))) == NULL){
fprintf(stderr, "Cannot allocate memory\n");
exit(1);
}
fscanf(fp, "%s%d", data[i]->number, &(data[i]->score));
}
fclose(fp);
qsort(data, sizeof(data)/sizeof(data[0]), sizeof(data[0]), compare);
for (i=0; i< 41; i++){
printf("%s %d\n", data[i]->number, data[i]->score);
}
return 0;
}
int compare(const void *x, const void *y) {
return (*(seiseki_t **)x)->score - (*(seiseki_t **)y)->score;
}
レポート問題 : 締め切り , 7 月 26 日 ( 月 ) 10:00 AM(JST)
行列のサイズm, nを入力から受け取って, m×n行列を作成するプログラムを書け. プログラムは, 次の仕 様にすること.
• 行列のサイズm, nは標準入力から受け取る.
• 行列の成分は,int型にする.
• 行列のサイズが決まれば,各行単位で,行ベクトルの入力をするようにし,それをメモリ内に保持する.
• 最後に上で入力した行列を出力する.
• 出力は,行単位でする. 例えば,行列 (
1 2 3
4 5 6
)
の出力は
1 2 3 4 5 6
となるようにする.
件名: gengo2021 report14.
