計算機言語
I
第14
回ポインタへのポインタ
,
ポインタの配列この資料
: http://www.math.u-ryukyu.ac.jp/~suga/gengo/2019-1/14.pdf
レポートへのツッコミ
レポートでは
,
今回の授業で話そうとした内容が既に書かれていました.
その部分は,
授業の後半に述べ ます.
素朴なプログラムを書いた方へのツッコミを入れておきます
.
それは,
データの入れ替えを利用したバブル ソートで, seiseki_t
型の40
個の配列を整列させるものです.
そのときに,
「構造体は,
代入によるコピーが 可能」ということを使うとソースはすっきりとします.
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[40]
は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[40];
int i;
if ((fp=fopen("input.data","r"))==NULL){
fprintf(stderr, "
ファイルを開けません.\n");
exit(1);
}
for (i=0; i< 40; 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< 40; 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=39; 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(n log n)
である.(
最悪はO(n
2).
バブルソートは,
これが常にO(n
2))
•
再帰的なプログラムのため,
データ量が少ないと,
再帰呼び出しのオーバーヘッドで却って遅くなる.
C
では,
標準ライブラリ関数として, qsort()
というものが用意されています.
その内容は,
必ずしもquicksort
の実装ではなく処理系依存ですが,
多くの場合, quicksort
の最後の欠点を少し改善したプログラムが実装されているようです
. (
ソート数が少なくなった時点で,
再帰をやめて別のアルゴリズムを使うようにし ている).
qsort()
の使い方は,
マニュアルコマンドでわかりますが,
その読み方を少し解説します.
Bash 3-2$ man 3 qsort
次のプログラムは
, qsort()
を用いて, seiseki_t data[40];
をscore
の小さい並べ替えた例です.
比 較関数compare
については,
白板で解説します.
compare()
にカウンタを入れて,
私のデータで計測したところ, 166
回のデータ比較で並び替えが終了しました
.
バブルソートだと, 40 × 39
2 = 780
回のデータ比較が必要ですから, 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[40];
int i;
if ((fp=fopen("data.txt","r"))==NULL){
fprintf(stderr, "Cannot open file\n");
exit(1);
}
for (i=0; i< 40; 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< 40; 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
月29
日(
月) 10:00 AM(JST)
行列のサイズ
m, n
を入力から受け取って, m × n
行列を作成するプログラムを書け.
プログラムは,
次の仕 様にすること.
•
行列のサイズm, n
は標準入力から受け取る.
•
行列の成分は, int
型にする.
•
行列のサイズが決まれば,
各行単位で,
行ベクトルの入力をするようにし,
それをメモリ内に保持する.
•
最後に上で入力した行列を出力する.
•
出力は,
行単位でする.
例えば,
行列(
1 2 3
4 5 6
)
の出力は
1 2 3 4 5 6
となるようにする
.
件名
