ホーム » 「値渡し」タグがついた投稿
タグアーカイブ: 値渡し
ソート処理の見積もりとポインタ処理
前回の授業では、再帰処理やソートアルゴリズムの処理時間の見積もりについて説明を行った。
ソート処理の見積もり
この際の練習問題の1つめは、「再帰方程式の理解度確認の回答」にて解説を示す。
最後の練習問題はここで説明を行う。
選択法とクイックソートの処理時間の比較
例として、データ数N=20件で、選択法なら10msec、クイックソートで20msecかかったとする。
これより、選択法の処理時間を、クイックソートの処理時間を
、とすると、
よって、
処理時間が逆転するときのデータ件数は、2つのグラフの交点を求めることになるので、
より、以下の式を解いた答えとなる。これは通常の方程式では解けないが電卓で求めると、N=53.1 ほどかな。(2020/05/26) 真面目に解いたら N=53.017 だった。
実際にも、クイックソートを再帰呼び出しだけでプログラムを書くと、データ件数が少ない場合は選択法などのアルゴリズムの方が処理時間が早い。このため、C言語などの組み込み関数の qsort() などは、データ件数が20とか30とか一定数を下回ったら、再帰を行わずに選択法でソートを行うのが一般的である。
ポインタ処理
ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。
値渡し(call by value)
// 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応する実引数で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後も main::a は 123 のまま。 foo( a ) ; // 124 }
このプログラムでは、aの値は変化せずに、124,124 が表示される。
言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?
// 大域変数を使う場合 int x ; void foo() { x++ ; printf( "%d¥n" , x ) ; } void main() { x = 123 ; foo() ; // 124 foo() ; // 125 }
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例 int i ; void foo() { for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } void main() { for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と foo() ; // 表示されない。 }
ポインタ渡し(call by pointer)
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。
// ポインタ渡しのプログラム void foo( int* p ) { // p はポインタ (*p)++ ; printf( "%d¥n" , *p ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( &a ) ; // 124 } // さらに125と増える。
C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は:結果を入れてもらう場所を伝え、関数側は:指定されたアドレスに結果を書む。
ポインタの加算と配列アドレス
ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。
// ポインタ加算の例 int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ; void main() { int* p ; // p∇ p = &a[2] ; // a[] : 11,22,33,44,55 // -2 +0 +1 printf( "%d¥n" , *p ) ; // 33 p[0] printf( "%d¥n" , *(p+1) ) ; // 44 p[1] printf( "%d¥n" , *(p-2) ) ; // 11 p[-2] p = a ; // p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p++ ; // → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 p += 2 ; // → → p∇ printf( "%d¥n" , *p ) ; // a[] : 11,22,33,44,55 }
ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。
*(p + 整数式) と p[ 整数式 ] は同じ意味
特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
struct Person { char name[ 10 ] ; int age ; } ; struct Person table[3] = { { "t-saitoh" , 55 } , { "tomoko" , 44 } , { "mitsuki" , 19 } , } ; void print_Person( struct Person* p ) { printf( "%s %d\n" , (*p).name , // * と . では . の方が優先順位が高い // p->name と簡単に書ける。 p->age ) ; // (*p).age の簡単な書き方 } void main() { for( int i = 0 ; i < 3 ; i++ ) { print_Person( &(table[i]) ) ; // print_Person( table + i ) ; でも良い } }
構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。
練習問題(2018年度中間試験問題より)
値渡しとポインタ渡し
前回はWeb提示資料と課題でガイダンスを行ったが、今日は遠隔授業形式での初回。前回のガイダンス資料を前半ざっと流し、後半はC言語をあまりやっていない学科の人向けのC言語の基礎。ただし、参照渡しについては電子情報の授業でも細かく扱っていない内容なので電子情報系学生の人はそこだけ注意してね。
オブジェクト指向のプログラムでは、構造体のポインタ渡しを多用するが、その基本となる関数との値の受け渡しの理解のため、以下に値渡し・ポインタ渡し・参照渡しについて説明する。
ポインタと引数
値渡し
// 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応する実引数で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後も main::a は 123 のまま。 foo( a ) ; // 124 }
このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?
// 大域変数を使う場合 int x ; void foo() { x++ ; printf( "%d¥n" , x ) ; } void main() { x = 123 ; foo() ; // 124 foo() ; // 125 }
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例 int i ; void foo() { for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } void main() { for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と foo() ; // 表示されない。 }
ポインタ渡し
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。
// ポインタ渡しのプログラム void foo( int* p ) { // p はポインタ (*p)++ ; printf( "%d¥n" , *p ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( &a ) ; // 124 } // さらに125と増える。
ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを使わないようにするために、参照渡しを利用する。
参照渡し
// ポインタ渡しのプログラム void foo( int& x ) { // xは参照 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( a ) ; // 124 } // さらに125と増える。
構造体のポインタ渡し
// 構造体のポインタ渡しのプログラム struct Person { int name[ 20 ] ; int age ; } ; // 構造体にデータを代入するための関数 void set_Person( struct Person* p , char nm[] , int ag ) { // ポインタ参照で書くと以下の通り strcpy( (*p).name , nm ) ; (*p).age = ag ; // アロー演算子を使うとシンプルに書ける。 // strcpy( p->name , nm ) ; // p->age = ag ; } // 構造体のデータを表示するための関数 void print_Person( struct Person* p ) { printf( "%s %d¥n" , p->name , p->age ) ; } // 関数名さえ処理の意図がつたわる名前を使えば、 // 値をセットして、表示する...ぐらいは一目瞭然。 // 構造体の中身を知らなくても、関数の中身を知らなくても、 // やりたいことは伝わる。...隠蔽化 void main() { struct Person tsaitoh ; // tsaitohに set して、 set_Person( &tsaitoh , "t-saitoh" , 55 ) ; // tsaitohを print する。 print_Person( &tsaitoh ) ; }
ポインタを使った処理
この後の授業で、ポインタを使ったプログラムが増えるので、ポインタの理解の確認
ポインタと引数
値渡し
// 値渡しのプログラム void foo( int x ) { // x は局所変数(仮引数は呼出時に // 対応する実引数で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後も main::a は 123 のまま。 foo( a ) ; // 124 }
このプログラムでは、aの値は変化せずに、124,124 が表示される。
でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?
// 大域変数を使う場合 int x ; void foo() { x++ ; printf( "%d¥n" , x ) ; } void main() { x = 123 ; foo() ; // 124 foo() ; // 125 }
しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。
// 大域変数が原因で予想外の挙動をしめす簡単な例 int i ; void foo() { for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } void main() { for( i = 0 ; i < 3 ; i++ ) // このプログラムでは、AA AA AA と foo() ; // 表示されない。 }
静的局所変数
大域変数を使わない方法としては、静的局所変数( static )を使う方法もある。
// 静的局所変数を使う場合 void foo() { static int x = 123 ; // x は foo の内部でのみ使用可 // x はプログラム起動時に作られ 123 で初期化される。 x++ ; printf( "%d¥n" , x ) ; } void main() { foo() ; // 124 foo() ; // 125 // ここで x = 321 といった代入はできない }
静的局所変数は、変数の寿命が大域変数と同じように、プログラム起動から終了までの間だが、参照できるスコープは所属するブロック内に限られる。
ポインタ渡し
C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。
// ポインタ渡しのプログラム void foo( int* p ) { // p はポインタ (*p)++ ; printf( "%d¥n" , *p ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( &a ) ; // 124 } // さらに125と増える。
ポインタを利用して引数に副作用を与える方法は、ポインタを正しく理解していないプログラマーでは、危険な操作となる。C++では、ポインタ渡しを使わないようにするために、参照渡しを利用する。
参照渡し
// ポインタ渡しのプログラム void foo( int& x ) { // xは参照 x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 // 処理後 main::a は 124 に増えている。 foo( a ) ; // 124 } // さらに125と増える。
ポインタ渡しを使う処理
// ポインタ渡しのプログラム void swap( int* pa , int* pb ) { int t = *pa ; *pa = *pb ; *pb = t ; } void main() { int a = 123 ; int b = 111 ; swap( &a , &b ) ; printf( "%d %d¥n" , a , b ) ; }
引数渡しについて
オブジェクト指向の授業では他学科出身の人も多いので、引数渡しの理解が浅いことから、別途説明を行う。
値渡し、ポインタ渡し、参照渡し
構造体の使い方の話では、関数との構造体のデータ渡しでポインタなどが出てくるので、 値渡し・ポインタ渡し・参照渡しの説明。(参照渡しは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が表示 }
参照型は、ポインタを使っていないように見えるけれども、機械語レベルでみればポインタ渡しの命令を自動的に生成してくれるだけ。