計算機言語
II
第7
回C
の特徴を利用するhttp://www.math.u-ryukyu.ac.jp/~suga/gengo/2018-2/07.pdf
教科書
p. 321, List 12–7
は,
「熟練したC
プログラマは,
このようさソースを書かない」感が満載なので,
今回はそれを解説します
.
1
ポインタの復習と補足C
のプログラムでは,
識別子があるものは実行時にはオブジェクトと呼ばれる形でメモリの中に存在し,
そ のメモリ上の場所を表す総称として「ポインタ」という言葉を用いることを学習しました,
さらに
,
ポインタを値に取る変数「ポインタ型変数」が利用できることも勉強しました.
void
型ポインタポインタというのは
,
実行時のアドレスですから,
その値が指す場所にどのようなオブジェクトがあっても,
アドレスという値のデータ量は一定(
アドレス値が取りうる範囲が保持できれば良い)
です.
ちなみに,
この講 義で用いている処理系では,
ポインタが占めるデータ量は, 64bit = 8 byte
です.
従って,
ポインタ型変数と は,
「アドレスを保持するメモリ量を持つ変数でそこにはアドレスが代入される」というものです.
ところで
,
「その値が指すオブジェクトにはよらない,
アドレスを保持するためだけ変数で,
そこにはアドレ スが代入される」という変数型があっても良いわけです.
また,
そのような変数型がある方がプログラミング において便利です. C
では,
そのような変数型が定義できます. C
では,
そのようなポインタ型変数は, void
型 ポインタ変数と呼ばれ,
次のように宣言されます.
void *p;
上では
, p
は実行時のアドレスを保持するメモリ量を持つ変数です.
このような変数に値を代入する際には,
そ のポインタが何を指しているかをキャストして代入します.
また,
ポインタ型であれば,
どのようなものを指す ポインタであろうと,
指すオブジェクトのポインタであるとキャストして代入することができます.
簡単な例を挙げておきます
. *(int *)p
は, p
はint
型ポインタ(int *)
であると見て(
キャストして),
そ のポインタが指す値(
先頭の*
の意味)
を取り出すと読みます.
代入文も同様です.
/* Void
型ポインタの例, voidptrtest.c */
#include <stdio.h>
int main() {
void *p;
int a = 1;
double b = 2.346;
p = (int *) &a;
printf("p=%p, *p = %d\n", p, *(int *)p);
p = (double *) &b;
printf("p=%p, *p = %lf\n", p, *(double *)p);
return 0;
}
ポインタへのポインタ
ポインタ型変数があるとします
.
例えば, int *p
という宣言があるとします.
プログラム実行時には, p
の 値は, p
のアドレスを&p
を利用して参照されます.
すなわち, &p
はポインタ型変数p
へのポインタなのです.
このポインタへのポインタを変数にすることもできます
.
宣言で, int **p
とすれば良いのです. p
にはポ インタ値が代入されますが,
それが指す値は*p
のアドレスで, *p
にはint
型へのポインタ値が代入されてお り, **p
はint
型の値です.
プログラム例を挙げておきます.
#include <stdio.h>
int main() {
int a=1;
int *p ; int **q;
p=&a;
q=&p;
printf("q=%p, *q=%p, **q=%d\n", q, *q, **q);
return 0;
}
このようなものを考える理由は
,
「より効率の良いプログラムを書く」ためです.
最後に,
これを利用した例 を述べる予定です.
2
計算量コンピュータは「計算」をしているわけですが
,
その計算を実行するのにどの程度の計算回数が必要である か,
というのを問題にします.
f (n), g(n)
を自然数n
の(
正の値をとる)
関数とします.
n
lim
→∞f (n) g(n) = C
のとき
, f (n) = O(g(n))
と書き, O–
記法と言います. f (n) ≤ O(g(n))
も同様に定義されます. n
が入力デー タの量(
長さが), f (n)
が処理を終えるための計算回数とします.
計算量を問題にするときには,
多くの場合, g(n)
として, n
k(
多項式オーダー), 2
n(
指数オーダー) log n(
対数オーダー)
とこれらの積が現れます.
計算機科 学の分野では,
指数や対数の底は2
と取るのが通常ですが,
底の変換公式より, 1
より大きい数であれば,
どの ような底でも本質に影響は出ません.
現時点での
PC
では, 1
秒あたりの計算量が,
最も高性能なもので,
オーダーとしは1000
3くらいです.
データ量を
n = 1000
とするとn
5程度の計算なら頑張ればできますが, n
6の計算はかなり大変になり, n
7の計算は現実的には難しくなります
.
2.1
整列アルゴリズムと計算量p. 321, List 12–7
で用いられている整列アルゴリズムは,
バブルソート(bubble sort)
と呼ばれているものです
(p. 219
も参照). 2
重のfor
ループがあり, n
個のものを整列させるためには,
外側のループで, i=0
からi=n-1
まで,
内側のループでj=n-1
からi+1
までの合計n(n − 1)/2
回の比較演算と大小関係が異なる時の交換演算が行われます
.
つまり,
この整列法の計算量は,
元の要素の形態にかかわらず, O(n
2)
です.
データの整列をコンピュータで行うというのは
,
コンピュータが生まれた時から実行され続けています.
バ ブルソートはプログラムとして最も古くからあり,
素朴でわかりやすいものです.
しかし,
整列処理は,
コン ピュータの中で頻繁に実行されるため,
これよりも計算量の少ない整列アルゴリズムが多く発見されています.
プログラミングでバブルソートを使うことは稀です.
知られている整列アルゴリズムは
10
種を超え,
それらのアルゴリズムとその特徴を述べる時間はありませ ん.
元データの形に従って,
異なるソートアルゴリズムを用いることも普通です.
すなわち,
どのようなデータ に対しても効率的かつ速く整列するアルゴリズムは,
今のところ見つかっていません.
整列アルゴリズムは次 の基準で比較されます.
•
計算量はどれくらいか?
•
メモリ消費量はどれくらいか?
•
安定か?(
同じ値のデータが複数個あった場合に,
元の順を保持するか否か)
整列アルゴリズムの中で
,
メモリの消費量も少なく,
どのようなデータに対しても比較的高速に整列するこ とができるアルゴリズムとして, Hoare(
ホア)
が1960
年に発表したクイックソート(quick sort)
というもの的計算量は
O(n log n)
になることが知られています(
データの並び方が悪いときの最悪計算量は, O(n
2)).
比較的汎用的に使える整列アルゴリズムなので
, C
ではライブラリ関数として, quick sort(
の改良版)
がqsort
という名前で実装されています. man
コマンドでその使い方を見るには,
次のようにします. (man
コマ ンドのキーワード検索man -k
をも覚えておいてください.)
man 3 qsort
関数の引数に関数の計算値を利用する
上の
man
コマンドを実行すると, qsort
関数のプロトタイプが次のように表示されます. void qsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
出てきた内容を読むと
, qsort
は値を返さない関数で, *base
は整列されるデータの先頭へのポインタ, nmemb
は整列されるデータの個数, size
は整列されるデータ1
つの(
メモリ内での)
大きさ,
最後が,
整列の基準と なる大小関係を与える関数compar
で, <, =, >
に従って,
負のint
値, 0,
正のint
値を与える関数にします.
すなわち, qsort
は,
その関数の引数として,
関数compar
の計算結果を利用します(
数学での合成関数みたい なもの).
このような,
引数としての関数値を利用するには,
返り値の型とともにその関数へのポインタ型を引 数に利用すれば良いように, C
は設計されています. int *(compar)
はint
型を返す関数へのポインタとい う意味です.
また,
関数compar
は,
大小関係の定義を与えますから,
利用する際にプログラマが指定します.
man 3 qsort
を読むと,
これを利用するには, stdlib.h
をinclude
する必要があります.
ありがたいこと に, man 3 qsort
では, qsort
の使い方の例も出力されます.
3
構造体のコピー(
代入)
教科書
p. 321, List 12–7
のダメな点のひとつに,
構造体のコピーがあります.
関数sort_by_height
の中で用いる関数
swap
が構造体のコピーを繰り返し利用しています.
前回の講義で
,
構造体は関数の引数や返り値にでき,
さらにコピーもできると述べました.
しかし,
実際のプ ログラミングにおいては,
構造体を関数引数にしたり,
返り値にしたり,
コピーしたりは,
「その操作を用いる 以外に処理方法がない」という場面以外では用いません.
プログラムで定義されている
Student
という構造体は, 80
バイト程度のデータになります.
これをコピー(
代入)
するのは,
コンピュータ的には,
そこそこ手間なことなのです.
次のページの例は
, Student
というデータを,
「ポインタを利用してコピーを入れ替える」という関数swap1
と,
「ポインタへのポインタを利用して指す場所を入れ替える」という関数swap2
を描いてみたものです.
教科書では
, swqp1
を利用しています.
main()
が無いので, cc
コマンドは失敗しますが, cc -c -S swaptest.c
でアセンブリ言語のソースを出 さして,
それを読むとその違いがわかります.
/* swaptest.c */
#define NAME_LENGTH 64
typedef struct student { char name[NAME_LENGTH];
int height;
double weight;
int scholarship;
} Student;
void swap1(Student *x, Student *y) {
Student temp=*x;
*x=*y;
*y=temp;
}
void swap2(Student **x, Student **y) {
Student *temp;
temp = *x;
*x = *y;
*y = temp;
}
まとめ
(List 12–7
の問題点)
Lis1 12–7
の残念なところは,
次の点です.
•
整列の際に構造体のコピーを利用しているが,
それをポインタ利用に変更すれば,
コピーに対する処理 が軽くなる.
•
整列アルゴリズムとして,
バブルソートを利用しているが,
これは一般的にあまり効率が良くない. C
はOS
の開発のために作られましたから, CPU
効率の高いプログラムを書くことがでる仕組みがあります
. List 12–7
は,
それを全く利用していないのです.
処理するデータ量が5
つですから, List 12–7
の非効率性は実行時には見えませんが
,
これが10000
個のデータだと,
差が見えるようになります.
ただし
, 10000
個のデータをプログラム内に書き込むことは現実的ではないので,
以下の例では,
データ入力の部分は無視しました
. (1
ページにするために改行を減らしました.
各自,
適宜付け加えてください.)
/* List 12-7m.c */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NUMBER_OF_DATA 5
#define NAME_LENGTH 64 typedef struct student {
char name[NAME_LENGTH];
int height;
double weight;
long scholarship;
} Student;
Student sato = { "Sato", 179, 61.2, 80000 };
Student sanaka = { "Sanaka", 175, 62.5, 73000 };
Student takao = { "Takao", 173, 86.2, 0 };
Student mike = { "Mike", 165, 72.3, 70000 };
Student masaki = { "Masaki", 179, 77.5, 70000 };
int compare(const void *a, const void *b) {
return (*(Student **)a)->height - (*(Student **)b)->height;
}
int main(void) {
int i;
Student *student[NUMBER_OF_DATA];
student[0] = &sato; student[1] = &sanaka; student[2] = &takao;
student[3] = &mike; student[4] = &masaki;
for ( i=0 ; i < NUMBER_OF_DATA; i++){
printf("%-6s %6d%6.1f%7d\n", student[i]->name, student[i]->height, student[i]->weight, student[i]->scholarship);
}
qsort(student, NUMBER_OF_DATA, sizeof(student[0]), compare);
for ( i=0 ; i < NUMBER_OF_DATA; i++){
printf("%-6s %6d%6.1f%7d\n", student[i]->name, student[i]->height, student[i]->weight, student[i]->scholarship);
}
return 0;
}
上のプログラムの解説
qsort
の使い方qsort
はバブルソートと同じで「比較と交換」を用いてデータを整列します.
整列されるデータは,
配列の形で
*base
に先頭へのポインタが渡されます. qsort
の中で,
比較関数compar
が呼ばれるのですが, compar
への引数には,
整列対象である配列の2
つの要素へのポインタが渡されます.
比較関数compar
それらの渡 されたポインタ値から,
比較すべき対象にアクセスし,
その大小関係を与える値を返すようにします. qsort
は,
その値から要素を交換するか否かを決め,
交換する必要があるときには,
配列の要素の交換を実行します. qsort
の3
番目の引数size
は,
どれだけの大きさのデータを交換するかを決定するために必要なのです.
Student *student[NUMBER OF DAGA]
こ れ は
, Student
型 へ の ポ イ ン タ を 値 と す るNUBMER_OF_DATA
個 の 配 列 の 宣 言 で す.
す な わ ち, student[0], student[1], ..., student[4]
は,
構造体Student
を指すポインタの値が入ります.
プロ グラムでは,
このポインタ値を入れ替えることにより整列を実行します.
初期化時に入力された5
つの構造体 の場所は,
プログラム実行中は変わりません.
関数
compare
わかりづらいのは
,
この関数の実行部分です.
return (*(Student **)a)->height - (*(Student **)b)->height;
qsort
は,
第一引数にstudent
が代入されます.
したがって, student[i]
はStudent
へのポインタで,
関数compare
の引数には, student[i]
へのポインタが代入されます.
すなわち, compare
はポインタへのポインタ を受け取ります.
(*(Student **)a)->height
は, a
を 構 造 体Student
の ポ イ ン タ へ の ポ イ ン タ と キ ャ ス ト し((Student **)
の 部 分)
そ れ が 指 す 値(*(Student **)
の 部 分)
は, Student
へ の ポ イ ン タ な の で,
矢 印演算子を利用して, Student
構造体のheight
メンバの値をアクセスすると読みます.
補足
教科書
p.319, List 12–6
は構造体を返す関数の例です.
しかし,
上でも述べたように,
構造体を返すとかコピーするとかは特別な事情がない限りプログラムすることはありません
.
「必要とあれば構造体のコピーや関 数の引数,
返り値が利用できる」という事実だけ,
知っておいてください.
レポート問題
:
締め切り11
月22
日(
木)
送り先は
, [email protected]
1.
教科書,
演習12-4.
上のList 12-7m
を利用すること.
文字列の比較は,
ライブラリ関数strcmp
を用いる
