仮想関数と純粋仮想基底クラス
前々回の講義では派生と継承の説明にて、次のようなプログラムを説明した。
派生と継承の復習
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char* s , int a ) { strcpy( name , s ) ; age = a ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス class Student : public Person { private: char dep[ 10 ] ; int grade ; public: Student( const char* s , int a , const char* d , int g ) : Person( s , a ) { strcpy( dep , d ) ; grade = g ; } void print() { // 継承でなくStudent版のprintを定義 Person::print() ; printf( "= %s %d\n" , dep , grade ) ; } } ; int main() { // 派生と継承の確認 Person tsaitoh( "tsaitoh" , 50 ) ; tsaitoh.print() ; Student naka( "naka" , 22 , "PS" , 2 ) ; naka.print() ; // Student版を実行 // 異なる型のデータをごちゃ混ぜにできないか? Person* table[2] ; table[0] = &tsaitoh ; table[1] = &naka ; for( int i = 0 ; i < 2 ; i++ ) { table[i]->print() ; } return 0 ; }
このプログラムのmain() では、tsaitohとnakaのデータを 表示させているが、tsaitohとnakaは、オマケの有る無しの違いはあっても、 元をたどれば、Person型。ごちゃまぜにできないだろうか?
int main() { : // 異なる型のデータをごちゃ混ぜにできないか? Person* table[2] ; table[0] = &tsaitoh ; table[1] = &naka ; for( int i = 0 ; i < 2 ; i++ ) { table[i]->print() ; } return 0 ; }
C++では、派生クラスは格下げして基底クラスのように振る舞うこともできる。 上記の例では、Studentのポインタ型である、&nakaは、 Personのポインタ型として振る舞うこともできる。
ただし、table[]に格納する時点で、Person型へのポインタなので、 table[i]->print() を呼び出しても、Personとして振る舞うため、 tsaitoh 50 / naka 22 が表示される。
仮想関数
上記のプログラムでは、Student型には、名前,年齢,所属,学年をすべて表示する Student::print() が宣言してある。 であれば、「naka 22」 ではなく、「naka 22 PS 2」と表示したくはならないか?
上記の例では、table[] に格納する段階で、格下げされているため、「naka 22」しか表示できない。 しかし、以下のように書き換えると、「naka 22 PS 2」と表示できる。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char* s , int a ) { strcpy( name , s ) ; age = a ; } virtual void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス class Student : public Person { private: char dep[ 10 ] ; int grade ; public: Student( const char* s , int a , const char* d , int g ) : Person( s , a ) { strcpy( dep , d ) ; grade = g ; } virtual void print() { // 継承でなくStudent版のprintを定義 Person::print() ; printf( "= %s %d\n" , dep , grade ) ; } } ; int main() { Person tsaitoh( "tsaitoh" , 50 ) ; Student naka( "naka" , 22 , "PS" , 2 ) ; // 異なる型のデータをごちゃ混ぜにできないか? Person* table[2] ; table[0] = &tsaitoh ; table[1] = &naka ; for( int i = 0 ; i < 2 ; i++ ) { table[i]->print() ; } return 0 ; }
上記の例の用に、printメソッドに virtual 宣言を追加すると、 C++では、tsaitoh,naka のデータ宣言時に、データ種別情報が埋め込まれる。 この状態で、table[i]->print() を呼び出されると、 データ種別毎のprint()を呼び出してくれる。 (この実装では、前回授業の関数ポインタが使われている)
ここで、学生さんから、「table[] の宣言をStudentで書いたらどうなるの?」という 質問がでた。おもわず『良い質問ですねぇ〜』と池上彰ばりの返答をしてしまった。
Student* table[] ; table[0] = &tsaitoh ; // 文法エラー // 派生クラスは基底クラスにはなれるけど、 // 基底クラスが派生クラスになることはできない。 table[1] = &naka ;
純粋仮想基底クラス
// 純粋仮想基底クラス class Object { public: virtual void print() = 0 ; // 中身の無い純粋基底クラスを記述しない時の書き方。 } ; // 整数データの派生クラス class IntObject : public Object { private: int data ; public: IntObject( int x ) { data = x ; } virtual void print() { printf( "%d\n" , data ) ; } } ; // 文字列の派生クラス class StringObject : public Object { private: char data[ 100 ] ; public: StringObject( const char* s ) { strcpy( data , s ) ; } virtual void print() { printf( "%s\n" , data ) ; } } ; // 実数の派生クラス class DoubleObject : public Object { private: double data ; public: DoubleObject( double x ) { data = x ; } virtual void print() { printf( "%lf\n" , data ) ; } } ; // 動作確認 int main() { Object* data[3] = { new IntObject( 123 ) , new StringObject( "abc" ) , new DoubleObject( 1.23 ) , } ; for( int i = 0 ; i < 3 ; i++ ) { data[i]->print() ; } return 0 ; } ;
この書き方では、data[]には、整数、文字列、実数という異なるデータが入っているが、 Objectという純粋仮想基底クラスを通して、共通な型のように扱えるようになる。 そして、data[i]->print() では、各型の仮想関数が呼び出されるため、 「123 abc 1.23」 が表示される。
ここで、Object の様な一見すると中身が何もないクラスを宣言し、 このクラスから様々な派生クラスを用いるプログラムテクニックは、 広く利用され、Objectのような基底クラスは、純粋仮想基底クラスなどと呼ばれる。
派生と継承
隠ぺい化の次のステップとして、派生・継承を説明する。
派生を使わずに書くと…
元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。
// 元となる構造体(Person) struct Person { char name[ 20 ] ; // 名前 int age ; // 年齢 } ; // 初期化関数 void set_Person( struct Person* p , char s[] , int x ) { strcpy( p->name , s ) ; p->age = x ; } // 表示関数 void print_Person( struct Person* p ) { printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct Person saitoh ; set_Person( &saitoh , "t-saitoh" , 50 ) ; print_Person( &saitoh ) ; }
パターン1(そのまんま…)
上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。
このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。
// 元のデータに追加要素(パターン1) struct PersonStudent1 { char name[ 20 ] ; // 名前 int age ; // 年齢 char dep[ 20 ] ; // 所属 int grade ; // 学年 } ; void set_PersonStudent1( struct PersonStudent1* p , char s[] , int x , char d[] , int g ) { strcpy( p->name , s ) ; // 同じことを書いてる p->age = x ; strcpy( p->dep , d ) ; // 追加分はしかたない p->grade = g ; } // 名前と年齢だけ表示 void print_PersonStudent1( struct PersonStudent1* p ) { // また同じ処理を書いてる printf( "%s %d\n" , p->name , p->age ) ; } void main() { struct PersonStudent1 naka1 ; set_PersonStudent1( &naka1 , "naka" , 22 , "PS" , 2 ) ; print_PersonStudent1( &naka1 ) ; }
パターン2(元データの処理を少し使って…)
パターン1では、同じような処理を何度も書くことになり、面倒なので、 元データ用の関数をうまく使うように書いてみる。
// 元のデータに追加要素(パターン2) struct PersonStudent2 { struct Person person ; char dep[ 20 ] ; int grade ; } ; void set_PersonStudent2( struct PersonStudent2* p , char s[] , int x , char d[] , int g ) { // Personの関数を部分的に使う set_Person( &(p->person) , s , x ) ; // 追加分はしかたない strcpy( p->dep , d ) ; p->grade = g ; } void print_PersonStudent2( struct PersonStudent2* p ) { // Personの関数を使う。 print_Person( &p->person ) ; } void main() { struct PersonStudent2 naka2 ; set_PersonStudent2( &naka2 , "naka" , 22 , "PS" , 2 ) ; print_PersonStudent2( &naka2 ) ; }
このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。
しかし、print_PersonStudent2() のような処理は、元データ構造が同じなのに、 いちいちプログラムを記述するのは面倒ではないか?
そこで、元データの処理を拡張し、処理の流用ができないであろうか?
基底クラスから派生クラスを作る
オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」「public/protected/private」基底クラス名を書く。
// 基底クラス class Person { private: char name[ 20 ] ; int age ; public: Person( const char s[] , int x ) { strcpy( name , s ) ; age = x ; } void print() { printf( "%s %d\n" , name , age ) ; } } ; // 派生クラス class Student : public Person { private: char dep[ 20 ] ; int grade ; public: Student( const char s[] , int x , const char d[] , int g ) : Person( s , x ) // 基底クラスのコンストラクタ { strcpy( dep , d ) ; grade = g ; } } ; void main() { Person saitoh( "t-saitoh" , 50 ) ; saitoh.print() ; Student naka( "naka" , 22 , "PS" , 2 ) ; naka.print() ; }
ここで注目すべき点は、main()の中で、Studentクラス"naka"に対し、naka.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「naka 22」が表示される。
さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。
class Student ...略... { ...略... void print() { Person::print() ; printf( "%s %d\n" , dep , grade ) ; } } ; void main() { ...略... Student naka( "naka" , 22 , "PS" , 2 ) ; naka.print() ; }
この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「naka 22 / PS 2」が表示される。
派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。
public だれもがアクセス可能。 protected であれば、派生クラスからアクセスが可能。 派生クラスであれば、通常は protected で使うのが一般的。 private 派生クラスでもアクセス不可。
数値の範囲とトラブル事例
先日の数値の範囲の説明で、浮動小数点型(float,double)などについても説明を行う。
16bitコンピュータの時代…
簡単な桁あふれの事例として、古いコンピュータ16bitの時代の事例。
// int は16bitとする。 // パソコン画面上の2点の距離を計算したい。 int x1 , y1 ; int x2 , y2 ; int r = (int) sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ) ;
このプログラムは、負の値の平方根を求めた…というエラーメッセージで止まってしまう。
これは、座標が200ドット離れていれば、2乗の和を求めた段階で、40000となるが、 16bit 符号付き整数であれば、最大数が32767 なので桁あふれして、負の数として扱われている。
2038年問題
次に、20XX年問題の説明。 2000年問題とは、古いプログラムで西暦末尾2桁で年を扱っていたプログラムが誤動作を 起こす可能性の問題。
同じように数値の範囲が原因となるものとして、2038年問題を紹介する。 OS unix では、時間を1970年からの経過秒数で表す。 この時、32bit(符号付きint型)であれば、2^31-1が扱える最大数であり、 (2^31-1) / (3600*24*365.22)を求めると、約68年となる。 つまり、32bit int であった場合は、2038年以降は桁あふれで時間を正しく扱えなくなる可能性がある。
しかし、計算の途中の段階で桁あふれして動かない事例はある。 以下の事例は、2004年に実際に発生したトラブルと同様の簡単なコードである。
// intは32bitとする // 2つの時間の中央時間を計算するコード int t1 , t2 ; int tm = (t1 + t2) / 2 ;
32bitの時間情報では、2004年以降は、 t1,t2の上位ビットが01XX……となっているため、 t1+t2 を計算すると最上位ビット(符号ビット)が1となり この後の計算は、負の値として扱われた。
上記のコードは、次のように記述するか、64bit化されたtime_t型で 記述すべきである。
// 32bitでも動く int tm = t1 + (t2 - t1) / 2 ; // 64bitのtime_t型 time_t t1 , t2 ; time_t tm = (t1 + t2) / 2 ; // △ time_t tm = t1 + difftime( t2 , t1 ) / 2 ; // ◎
248日問題
丁度ニュースで、「ボーイング787が248日以上連続稼働すると、電源停止で制御不能となる」というネタが 紹介されている。点検などがあるから、実際はあり得ない状況だとは思えるが、 これもint型の桁あふれが原因らしい。 あり得ないとはいえ、フライバイワイヤ(操縦桿を電気信号で制御)の最新機は、電源が落ちれば即墜落。 これは、10msec単位で、OSの経過時間をint型(32bit)で制御しているのが 原因らしい。10msec*(2^31)=248日で桁あふれが発生して、電源稼働経過時間を誤認するらしい。 これと同様の事象は、Windows Xpなどが出た頃にも発生している。 787ほど深刻な墜落はないにしても、サーバ機なら248日稼働ぐらいはよくある話。
浮動小数点型と演算順位の問題
float型やdouble型は、浮動小数点で実数の小さな値から大きな値まで扱える。
しかしながら、プログラム中の式の順序によっては、注意が必要となる。
int a[ 5 ] = { 10 , 10 , 10 , 10 , 11 } ; int s = 0 , size = 5 ; for( int i = 0 ; i < size ; i++ ) s += a[ i ] ; printf( "%lf¥n" , s / size ) ; // × %lf はdouble型、s/size はint型で異常な値が表示される。 printf( "%lf¥n" , (double)( s / size ) ) ; // × s/sizeはint型で、小数点以下が求まらない。 printf( "%lf¥n" , (double)s / (double)size ) ; // ◎
#define PI 3.141592 double x ; for( x = 0.0 ; x < 2*PI ; x += (1/6) * PI ) { printf( "%lf %lf¥n" , x , sin( x ) ) ; }
このプログラムは、1/6が整数型で行われるため(つまり0とPIを掛ける)、 xの値が変化しない。 これは、"x += (1.0/6.0) * PI" と書かなければならない。
隠蔽化の課題(複素数クラスを例に)
前回の隠蔽化の話を受け、実際のプログラムの例を課題に説明。 複素数クラスを(実部,虚部)で実装した後に、(絶対値,偏角)に直したら…
基本プログラム(実部と虚部)
複素数を扱うクラスを作るのであれば、基本的には以下の様なコードとなるだろう。 複素数どうしの簡単な加算・乗算を記載する。
class Complex { private: double re , im ; public: Complex( double x , double y ) { re = x ; im = y ; } // 上記コンストラクタは、以下のようにも書ける。 // Complex( double x , double y ) // : re( x ) , im( y ) // { メンバ以外の初期化... } void print() { printf( "%lf+j%lf¥n" , re , im ) ; } void add( Complex &z ) { re = re + z.re ; im = im + z.im ; } void mul( Complex &z ) { double x = re * z.re - im * z.im ; double y = re * z.im + im * z.re ; re = x ; im = y ; } } ; int main() { Complex a( 1 , 2 ) ; Complex b( 2 , 3 ) ; a.add( b ) ; a.print() ; a.mul( b ) ; a.print() ; return 0 ; }
Complexクラス内部をリファクタリング
しかし、前述プログラムでは、mul()メソッドは、add()メソッドよりは、 複雑なものとなっている。 しかし、複素数の乗算は、(絶対値と偏角)を用いれば、絶対値の乗算・偏角の加算で 処理は簡単に記述できる。そこで、クラス内部を乗算と偏角で処理をするように変更してみる。
class Complex { private: double r , th ; public: Complex( double x , double y ) { r = sqrt( x*x + y*y ) ; th = atan2( y , x ) ; // atan2は象限を考慮してくれる } void print() { printf( "%lf ∠ %lf¥n" , r , th / 3.141592 * 180.0 ) ; } void add( Complex &z ) { // ここは面倒な式になっちゃう } void mul( Complex &z ) { r = r * z.r ; th = th + z.th ; } } ; int main() { Complex a( 1 , 2 ) ; Complex b( 2 , 3 ) ; a.add( b ) ; a.print() ; a.mul( b ) ; a.print() ; return 0 ; }
ここで重要なポイントは、2つめの絶対値∠偏角のプログラムの呼び出し側 main() は、 1つめのプログラムとまるっきり同じである。
このように、オブジェクト指向の隠蔽化を行っていれば、当初のクラス設計が悪くて後で変更 したくなった場合、利用者側からの見た目の動作を変更せずに、内部のデータ構造や処理メソッドを 変更が可能となる。 このように、利用者側からの見た目を変更せずに処理の内部を変更すること、 リファクタリング と呼ぶ。これにより、プログラムの不備や問題点があっても、積極的にプログラムを 改良できることから、不備の少ない安全なプログラムを作れるようになる。
隠蔽化の課題
以上の2つのプログラムで複素数の計算メソッド、加算(add),除算(sub),乗算(mul),除算(div)…その他を (実部,虚部)、(絶対値,偏角)で記載し、適切に記述をすれば、呼び出し側main()を まるっきり同じものにできることを通して、隠蔽化についてレポートにまとめよ。
レポートでは、以下の点を記載すること。(レポートは、本科中間試験の頃までに提出が望ましい)
- 2つの方式でのプログラム例
- 上記プログラムに対する説明
- 上記プログラムが正しく動作していたことが判る結果
- この課題から判る考察
再帰関数の処理と再帰方程式
前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。
特殊な処理時間の見積もり
前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、Nが巨大となった時の、最大項を見つければ良いことから、
が、N→∞において 発散するのか収束するのかを求める方法にて説明する。
また、2つのアルゴリズムがNの増加で処理時間が変化する時の事例として、 「データ件数が10件で、最大選択ソートが10msec、クイックソートが20msec出会った場合、 データ100件では、どちらが速いか?、この結果から、 データ件数がいくつ以上であれば、どちらの方法が良いか?」 といった問題について説明する。
最大選択ソートであれば、 より、
であるとする。 一方、クイックソートは、
より、
であるとする。
より、
。
より、
。
これより、データ100件の場合には、 となる。 また、
となりクイックソートの方が速い。
さらに、 となるNを求めれば、N件以上は クイックソートが速い…といった件数を求められる。
再帰関数と再帰方程式
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。
// 階乗 int fact( int x ) { if ( x <= 1 ) return 1 ; else return x * fact( x-1 ) ; } // ピラミッド体積 int pyra( int x ) { if ( x <= 1 ) return 1 ; else return x*x + pyra( x-1 ) ; } // フィボナッチ数列 int fib( int x ) { if ( x <= 2 ) return 1 ; else return fib( x-1 ) + fib( x-2 ) ; }
これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、
で表せる。 これを代入によって解けば、
で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。
最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。
ハノイの塔
ハノイの塔は、3本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、
ということが予想される。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、
ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、
枚では、
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
C言語の構造体からオブジェクト指向に
前回の構造体の説明から、ポインタ渡しの説明を行った後、同様のプログラムをC++で書き換えることで、classやメソッドなどの説明を行う。
構造体でオブジェクト指向もどき
例えば、名前と電話番号の構造体で処理を記述する場合、 以下の様な記載を行うことで、データ設計者とデータ実装者で分けて 仕事ができることを説明。
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 ) ; } void main() { struct Person table[ 10 ] ; for( int i = 0 ; i < 10 ; i++ ) { readPerson( &table[i] ) ; printPerson( &table[i] ) ; } }
このプログラムの書き方では、mainの中を読むだけもで、 データ入力とデータ出力を行うことはある程度理解できる。 この時、データ構造の中身を知らなくてもプログラムが理解でき、 データ実装者はプログラムを記述できる。これをデータ構造の隠蔽化という。 一方、readPerson()や、printPerson()という関数の中身についても、 入力・出力の方法をどうするのか知らなくても、 関数名から動作は推測できプログラムも書ける。 これを手続きの隠蔽化という。
C++のクラスで表現
上記のプログラムをそのままC++に書き直すと以下のようになる。
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 ) ; } } ; void 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なので参照できない。 }
用語の解説:C++のプログラムでは、データ構造とデータの処理を、並行しながら記述する。 データ構造に対する処理は、メソッド(method)と呼ばれる。 データ構造とメソッドを同時に記載したものは、クラス(class)と呼ぶ。 そのclassに対し、具体的な値や記憶域が割り当てられたものをオブジェクト(object)と呼ぶ。
コンストラクタとデストラクタ
プログラムを記述する場合、そのデータ構造を使うにあたり、 初期値が代入を忘れその値を参照すると、予想外の動きの原因となってしまうことが多い。
そこでオブジェクト指向では、データ構造の初期化手続き(同様に処理が終わった後の事後手続き)を 明確に記載するための初期化のコンストラクタ(と事後処理はデストラクタ)の文法がある。
class Person { private: char name[10] ; int phone ; public: Person( char s[] , int tel ) { // コンストラクタ strcpy( name , s ) ; phone = tel ; } void print() { printf( "%s %d¥n" , name , phone ) ; } } ; void main() { // オブジェクト宣言とコンストラクタでの初期化 Person saitoh( "tsaitoh" , 272925 ) ; saitoh.print() ; }
コンストラクタを宣言する場合には、返り値無しのクラス名を関数名として記述する。 デストラクタを宣言する場合には、先頭に「~」をつけたクラス名で無引数で記述する。 簡単な例として、文字列をヒープ領域に保存する処理を示す。
// デストラクタが便利な例 class String { private: char* str ; public: // コンストラクタ String( char*s ) { // ヒープメモリ上に文字列を確保 str = (char*)malloc( strlen( s ) + 1 ) ; strcpy( str , s ) ; } // デストラクタ ~String() { free( str ) ; // freeしないとメモリーリークになる。 } void print() { printf( "%s" , str ) ; } } ; void main() { String s( "abcdefg" ) ; s.print() ; } // mainを抜ける段階でsは不要となる。 // ここで自動的にデストラクタ呼び出し~String()をしてくれる。
関数の値渡しと、整数型の数値の範囲
丁度、講義の前に別授業の課題に取り組んでいる学生を見ていたら、 次週に説明を行おうと思っていたN進数、小数点を含む2進数であった。 丁度、「計算機構成論」の補数、「数値計算」の小数点を含む2進数の講義で、 いつもになく、内容と説明時期が重複している…(^_^;
関数の値渡し
関数との引数の値渡しについて解説。 C言語では基本の値渡しメカニズムしかない。 引数で副作用(side effect)を返したい場合は、その代用としてポインタ渡しを利用する。 また、配列が引数の場合、値渡しのためのコピーを最小限とするため、 配列先頭アドレスによるポインタ渡しで行われることを説明する。
// 値渡し void foo( int x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 foo( a ) ; // 124 } // ポインタ渡し void foo( int* px ) { (*px)++ ; printf( "%d¥n" , *px ) ; } void main() { int a = 123 ; foo( &a ) ; // 124 foo( &a ) ; // 125 } // 参照渡し(C++の新しい文法で紹介のみ) void foo( int &x ) { x++ ; printf( "%d¥n" , x ) ; } void main() { int a = 123 ; foo( a ) ; // 124 foo( a ) ; // 125 } // 配列でのポインタ渡し void foo( int x[] ) { x[0]++ ; printf( "%d¥n" , x[0] ) ; } void main() { int a[1] = { 123 } ; foo( a ) ; // 124 foo( a ) ; // 125 }
整数型の数値範囲
整数型などの数値範囲について説明を行うために、2の補数表現を復習したあと、 数値の範囲について説明する。
type | range | unsigned | signed --------------+-----------+----------+--------------- char | 8bit | 0..255 | -128..127 short int | 16bit | 0..65535 | -32768..32767 int | 32bit | 0..2^32-1| -2^31..2^31-1 long int | ?32bit? | | long long int | gcc 64bit | 0..2^64-1| -2^63..2^63-1
数値範囲の大まかな計算のための2つの方法として、 や、 10進数での桁数の概算のために、
より、
といった計算を行う方法について説明。
次週は、16bitコンピュータで int が簡単に桁あふれする問題や、 2038年問題や2004年問題などを解説する予定。
変数の寿命とスコープ
先週のC言語の制御構文のシメとして、switch-case文の説明をしてから、 変数の寿命とスコープの説明を行った。
switch-case文の説明では、以下の例は期待通りの動きをしない…といった例も交えて説明。 ただし、double誤差問題や文字列のポインタ関連なので、以後の授業で改めて説明が必要だろう。
// double誤差問題 double x ; for( x = 0.0 ; x <= 1.0 ; x += 0.1 ) switch( x ) { case 0.3 : printf( "A" ) ; // 0.299999...と0.3は違う値になるかも break ; } // 文字列の比較の問題 char str[ 10 ] ; scanf( "%s" , str ) ; switch( str ) { // strの先頭番地と"yes","no"の先頭番地の比較 case "yes" : printf( "はい" ) ; break ; case "no" : printf( "いいえ" ) ; break ; }
変数の寿命とスコープ
最初に、以下の様なプログラムが期待通りに動かない説明をして、 大域変数を共用することの問題を話す。
int i ; // 大域変数(global variable) void foo() { // Aを2回表示 for( i = 0 ; i < 2 ; i++ ) printf( "A" ) ; } void main() { // foo(Aを2回表示)を2回呼び出すつもり for( i = 0 ; i < 2 ; i++ ) foo() ; }
こういったトラブルを避けるためには、局所変数を使えば良い。
局所変数を使って、目的の処理…。改良版はココをクリックで表示。
最近の構造型プログラム言語であれば、 変数には寿命(変数が、作られる/消える、タイミング)と、 スコープ(変数が使える範囲)がある。
#include <stdio.h> // 静的大域変数(スコープ全体,寿命:起動から終了) int x = 123; void foo() { // 動的局所変数(スコープ:foo内部,寿命:foo呼出から戻るまで) int y = 234 ; // 静的局所変数(スコープ:foo内部,寿命:起動から終了) static int z = 345 ; x++ ; y++ ; z++ ; printf( "%d %d %d¥n" , x , y , z ) ; } void main() { foo() ; // 124,235,346が表示 foo() ; // 125,235,347が表示 }
関数の引数
関数の引数の受け渡しの説明。
返り値の型 関数名( 仮引数の宣言 ) { 何らかの処理 ; // 関数に入ると仮引数が局所変数で作られ、 return 式 ; // 実引数が代入される。 } void main() { 関数名( 実引数 ) ; // 実引数は仮引数にコピーされる。 }
値渡し、ポインタ渡しなどの説明をしたいけど、時間なので次週に説明。 残り時間では、BCPL→B言語→C言語(K&R-C→ANSI-C)→C++といった C言語の変遷を簡単に紹介。
処理速度の分析とオーダ記法
今回は、情報処理センターの機種更新に伴うパスワード再発行やら、 授業アンケートの作業に前半の時間をとられ、そのまま演習室にて授業。
2分探索法の処理時間分析
最初に、先週説明の単純サーチ と、2重ループの最大選択法
との比較をしながら、 以前のBLOG資料を使って、 2分探索法の処理時間が
であることを説明する。
オーダ記法
次に、定番の説明であるけれど、 「単純サーチで、100件で1msecかかった。 データ10000件なら何秒かかる?」 同様に、「最大選択法のプログラムで、100件で10msecかかったら、10000件なら何秒?」 という質問から、オーダ記法の導入を説明する。
最後に、 ,
,
といった、Nが大きな値になった時に、式で大きな値となる主要な部分を抜き出したもの がオーダといった説明を行う。
次回の授業での予習ネタとして、以下の式のオーダについて考えておくように…
SQLite3でデータベース
卒研でデータベースを使いたい人もいるようだけど、 MySQLとかまで完璧なのが必要なければ、SQLite を使ったほうが楽。 ただし、データ型は実質すべてtext型になるけど、簡単なアプリベースなら 支障はないはず。
<?php // データ保存用の sqlite-data はあらかじめ作っておく。 // sqlite-data の書き込み許可 // (手抜) $ chmod 777 sqlite-data // (厳密) # chgrp sqlite-data // # chmod 774 sqlite-data // sqlite-data/.htaccess には"Require all denied"を書いて // ディレクトリ内をWeb的にアクセス禁止にする。 // サーバのPHPを使うと、エラーが見つからず苦労するかも // その時は、.htaccess ファイルに、以下の設定を記載しておく // "php_flag display_errors On" // 説明しやすいように実行だけ関数をつくる function exec_command( $db , $cmd ) { if ( ($db->exec( $cmd )) === FALSE ) { print $db->lastErrorMsg() ; } } // データベースを作って初期データを登録 function table_initialize( $db ) { exec_command( $db , "create table Person(name text,phone text) ;" ) ; exec_command( $db , "insert into Person (name,phone) values('t-saitoh','272925');" ) ; exec_command( $db , "insert into Person (name,phone) values('tomoko' ,'123456');" ) ; exec_command( $db , "insert into Person (name,phone) values('mitsuki' ,'234567');" ) ; } // データベースを作る if ( !file_exists( "./sqlite-data/sample.db" ) ) { // なにも無い状態 $db = new SQLite3( "./sqlite-data/sample.db" ) ; table_initialize( $db ) ; } else { // すでに作られている場合 $db = new SQLite3( "./sqlite-data/sample.db" ) ; } ?> <html> <head> </head> <body> <pre> <?php // 登録されているデータを全部表示 if ( ($query = $db->query( "select * from Person" )) !== FALSE ) { while( $res = $query->fetchArray( SQLITE3_NUM ) ) { printf( "| %-10s | %-10s |\n" , $res[0] , $res[1] ) ; } } ?> </pre> </body> </html>