引数渡しと構造体からオブジェクト指向へ
値渡し、ポインタ渡し、参照渡し
構造体の使い方の話では、関数との構造体のデータ渡しでポインタなどが出てくるので、 値渡し・ポインタ渡し・参照渡しの復習。(参照渡しはC++で導入された考え方)
値渡し
C言語の基本は、値渡し。呼び出し側の実引数は、関数側の仮引数に値がコピーされる。 このため、呼び出し側の変数(下の例ではa)の中身は変化しない。 よって、関数の呼び出しで呼び出し側の変数が勝手に中身が変わらないので、予想外の変数の中身の変化が無く分かりやすい。
// 値渡し(call by value)の例 void foo( int x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124が表示 foo( a ) ; // 124が表示 }
ポインタ渡し
しかし、上の例では、foo()の呼び出しで、変数aの中身が変化してくれたほうが都合が良い場合もある。 この場合は、C言語ではポインタを使って記述する。 このように、関数を呼び出して、手元の変数が変化することは、副作用と呼ばれる。 副作用の多いプログラムは、変数の値の管理がわかりにくくなるので、副作用は最小限に記述すべき。
// ポインタ渡し(call by pointer)の例 void foo( int *px ) { (*px)++ ; printf( "%d¥n" , (*px) ) ; } void main() { int a = 123 ; foo( &a ) ; // 124が表示 foo( &a ) ; // 125が表示 }
参照渡し
しかし、ポインタを多用すると、ポインタを動かしてトラブルも増えることから、ポインタはあまり使わない方が良い。 そこで、C++では参照型というものがでてきた。
// 参照型(call by reference)の場合 void foo( int &x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124が表示 foo( a ) ; // 125が表示 }
参照型は、ポインタを使っていないように見えるけれども、機械語レベルでみればポインタを使ったものと同じ。
構造体でオブジェクト指向もどき
例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ利用者で分けて 仕事ができることを説明。
// この部分はデータ構造の設計者が書く // データ構造を記述 struct Person { char name[10] ; int phone ; } ; // データに対する処理を記述 void readPerson( struct Person* p ) { // ポインタの参照で表記 scanf( "%s%d" , (*p).name , &(*p).phone ) ; } void printPerson( struct Person* p ) { // アロー演算子で表記 printf( "%s %d¥n" , p->name , p->phone ) ; } // この部分は、データ利用者が書く int main() { // Personの中身を知らなくてもいいから配列を定義(データ隠蔽) struct Person table[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { // 入力して、出力する...という雰囲気で書ける(手続き隠蔽) readPerson( &table[i] ) ; printPerson( &table[i] ) ; } return 0 ; }
このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
#include <stdio.h> // この部分はクラス設計者が書く class Person { private: // クラス外からアクセスできない部分 // データ構造を記述 char name[10] ; // メンバーの宣言 int phone ; public: // クラス外から使える部分 // データに対する処理を記述 void read() { // メソッドの宣言 // pのように対象のオブジェクトを明記する必要はない。 scanf( "%s%d" , name , &phone ) ; } void print() { printf( "%s %d¥n" , name , phone ) ; } } ; // ← 注意ここのセミコロンを書き忘れないこと。 // この部分はクラス利用者が書く int main() { Person table[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { table[i].read() ; // メソッドの呼び出し table[i].print() ; // オブジェクト.メソッド() } // 文法エラーの例 printf( "%d¥n" , table[0].phone ) ; // phoneはprivateなので参照できない。 return 0 ; }
用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
制御構文について
プログラムの基本は、処理の順序を正しく理解していること。
まずは理解度確認
では、過去の電子情報3年プログラム応用のテスト問題から、以下のプログラムの実行順序を答えて下さい。
制御構文とフローチャート
構文の入れ子
繰り返し処理とオーダ記法
先週に、単純繰り返し処理の時間分析をやったので、次のステップに。
2分探索法の処理時間
データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。
// 2分探索法 O(log N) int a[ 1000 ] ; int size ; // データ数 N int L = 0 ; // L=下限のデータの場所 int R = size ; // R=上限のデータ+1の場所 while( L != R ) { int M = (L + R) / 2 ; // 計算は整数型で行われることに注意 if ( a[M] == key ) // 見つかった break ; else if ( a[M] < key ) // |L |M. |R L = M + 1 ; // |----------|-+---------| else // |L---------|M| R = M ; // |M+1------|R }
上記のようなプログラムの場合、処理に要する時T(N)は、
# Mは繰り返し回数
処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、
となることから、 の関係が成り立つ。よって、は、以下のように表せる。
単純なソート(最大選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
int a[ 1000 ] ; int size ; for( int i = 0 ; i < size - 1 ; i++ ) { int tmp ; // i..size-1 の範囲で一番大きいデータの場所を探す int m = i ; for( int j = i + 1 ; j < size ; j++ ) { if ( a[j] > a[m] ) m = j ; } // 一番大きいデータを先頭に移動 tmp = a[i] ; a[i] = a[m] ; a[m] = tmp ; }
このプログラムの処理時間T(N)は…
となる。
オーダー記法
ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、赤字の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。
単純サーチ | |
2分探索法 | |
最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。
単純サーチ | オーダーNのアルゴリズム | |
2分探索法 | オーダー log N のアルゴリズム | |
最大選択法 | オーダー N2 のアルゴリズム |
練習問題
- コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか? - の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このようなアルゴリズムの例を答えよ。
- の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?