複素数クラスによる演習
コンストラクタ
プログラミングでは、データの初期化忘れによる間違いもよく発生する。これを防ぐために、C++ のクラスでは、コンストラクタ(構築子)がある。データ構造の初期化専用の関数。
// コンストラクタ #include <stdio.h> #include <string.h> class Person { private: char name[ 20 ] ; int age ; public: void print() { printf( "%s %d¥n" , name , age ) ; } Person() { // コンストラクタ(A) name[0] = '¥0' ; // 空文字列 age = 0 ; } Person( const char str[] , int ag ) { // コンストラクタ(B) strcpy( name , str ) ; age = ag ; } ~Person() { // デストラクタ print() ; // 内容の表示 } } ; int main() { Person saitoh( "t-saitoh" , 55 ) ; // (A)で初期化 Person tomoko() ; // (B)で初期化 saitoh.print() ; // "t-saitoh 55" の表示 tomoko.print() ; // " 0" の表示 return 0 ; // この時点で saitoh.~Person() // tomoko.~Person() が自動的に } // 呼び出される。
コンストラクタと反対に、デストラクタは、データが不要となった時に自動的に呼び出される関数。
このクラスの中には、引数無しのコンストラクタと、引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)
デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。
複素数クラスの例
隠蔽化と基本的なオブジェクト指向の練習課題として、複素数クラスをあげる。ここでは、複素数の加算・乗算を例に説明をするので、減算・除算などの処理を記述することで、クラスの扱いに慣れてもらう。
直交座標系
#include <stdio.h> #include <math.h> // 直交座標系の複素数クラス class Complex { private: double re ; // 実部 double im ; // 虚部 public: void print() { printf( "%lf + j%lf¥n" , re , im ) ; } Complex( double r , double i ) { re = r ; im = i ; } Complex() { // デフォルトコンストラクタ re = im = 0.0 ; } void add( Complex z ) { // 加算は、直交座標系だと極めてシンプル re = re + z.re ; im = im + z.im ; } void mul( Complex z ) { // 乗算は、直交座標系だと、ちょっと煩雑 double r = re * z.re - im * z.im ; double i = re * z.im + im * z.re ; re = r ; im = i ; } double get_re() { return re ; } double get_im() { return im ; } double get_abs() { // 絶対値 return sqrt( re*re + im*im ) ; } double get_arg() { // 偏角 return atan2( im , re ) ; } } ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね int main() { // 複素数を作る Complex a( 1.0 , 2.0 ) ; Complex b( 2.0 , 3.0 ) ; // 複素数の計算 a.print() ; a.add( b ) ; a.print() ; a.mul( b ) ; a.print() ; return 0 ; }
極座標系
上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。
// 局座標系の複素数クラス class Complex { private: double r ; // 絶対値 r double th ; // 偏角 θ public: void print() { printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ; } Complex() { r = th = 0.0 ; } // 表面的には、同じ使い方ができるように // 直交座標系でのコンストラクタ Complex( double x , double y ) { r = sqrt( x*x + y*y ) ; th = atan2( y , x ) ; // 象限を考慮したatan() } // 極座標系だと、わかりやすい処理 void mul( Complex z ) { // 極座標系での乗算は r = r * z.r ; // 絶対値の積 th = th + z.th ; // 偏角の和 } // 反対に、加算は面倒な処理になってしまう。 void add( Complex z ) { ; // 自分で考えて } // double get_abs() { return r ; } double get_arg() { return th ; } double get_re() { return r * cos( th ) ; } double get_im() { return r * sin( th ) ; } } ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;
このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。
このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。
メソッドのプロトタイプ宣言
class 構文では、{} の中に、要素の定義や、メソッドの記述を行うと説明してきたが、メソッド内の処理が長い場合もある。
この時に、すべてを {} の中に書こうとすると、全体像が見渡せない。こういう時には、以下のように、メソッドのプロトタイプ宣言と、メソッドの実体の記述を別に記載する。
class Complex { private: double re , im ; public: Complex( double r , double i ) ; // メソッドのプロトタイプ宣言 void print() ; } ; // メソッドの実体 Complex::Complex( double r , double i ) { re = r ; im = i ; } void Complex::print() { printf( "%lf + j %lf" , re , im ) ; }
ゲッター/セッター (経験者向け解説)
それぞれのクラス宣言では、get_re() , get_im() , get_abs() , get_arg() というメソッドを記載した。このように記述しておくと、クラス外で re , im といったメンバを public 指定をせずに、リファクタリングしやすいクラスにすることができる。(re, im を public にしてしまうと、クラス外でオブジェクトへの代入が可能となる。)
PHPなどの private や public の機能のないオブジェクト指向言語では、get_xx() といった要素の参照しかできないメソッドを作ったうえで、クラス外でメンバ参照をしないというマナーを徹底させることで、public 機能の代用し、隠蔽化を徹底させることも多い。
この場合、参照専用の get_xx() と同じように、要素に値を設定するためのメソッド set_xx( 値… ) を作るとプログラムの意味が分かりやすくなる。こういったクラスの参照や代入のメソッドは、getter(ゲッター),setter(セッター)と呼ぶ。
ゲッターやセッターメソッドでは、要素を参照(あるいは代入)するだけといった極めて単純な関数を作ることになる。この場合、関数呼び出しの処理時間が無駄になる。この対処として、C++ には inline 関数機能がある。関数(メソッド)の前に、inline を指定すると、コンパイラは関数呼び出し用の命令を生成せず、それと同じ処理となる命令を埋め込んでくれる。(開いたサブルーチン)
class Complex { private: double re , im ; public: : inline void get_re() { return re ; } } ;
const 指定 (経験者向け解説)
C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。
void foo( const int x ) { x++ ; // 定数を書き換えることはできない。 printf( "%d\n" , x ) ; } int main() { const double pi = 3.141592 ; // C言語で #define PI 3.141592 と同等 int a = 123 ; foo( a ) ; return 0 ; }
前に説明した、getter メソッドは要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、
class ... { : inline double get_re() const { re = 0 ; // 文法エラー return re ; } } ;
再帰呼び出しと再帰方程式
再帰関数と再帰方程式
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。
// 階乗 (末尾再帰) 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の処理(Tb)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 で表せる。
} 再帰方程式
このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式 が得られる。
T(1)=Ta
T(2)=Tb+T(1)=Tb+Ta
T(3)=Tb+T(2)=2×Tb+Ta
:
T(N)=Tb+T(N-1)=Tb + (N-2)×Tb+Ta
一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。
再帰を含む一般的なプログラム例
ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的な再帰呼び出しのプログラムを、再帰方程式で処理時間を分析してみよう。
以下のプログラムを実行したらどんな値になるであろうか?それを踏まえ、処理時間はどのように表現できるであろうか?
int array[ 8 ] = { 3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 , } ; int sum( int a[] , int L , int R ) { // 非末尾再帰 if ( R - L == 1 ) { return a[ L ] ; } else { int M = (L + R) / 2 ; return sum( a , L , M ) + sum( a , M , R ) ; } } int main() { printf( "%d¥n" , sum( array , 0 , 8 ) ) ; return 0 ; }
このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端・右端を表している。そして、再帰のたびに2つに分割して解いている。
このような、処理を分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。
このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間Ts(N)は次の再帰方程式で表せる。
← Tβ + (L〜M)の処理時間 + (M〜R)の処理時間
これを代入の繰り返しで解いていくと、
ということで、このプログラムの処理時間は、 で表せる。
再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。
ハノイの塔
ハノイの塔は、3本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。
… ①
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、
… ③より
… ①を代入
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
理解度確認
- 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
- 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
- 再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ。
int a[ 10 ] = { 7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98 } ; int find( int array[] , int L , int R , int key ) { // 末尾再帰 // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。 if ( __________ ) { return ____ ; // 見つからなかった } else { int M = _________ ; if ( array[ M ] == key ) return ____ ; else if ( array[ M ] > key ) return find( array , ___ , ___ , key ) ; else return find( _____ , ___ , ___ , ___ ) ; } } int main() { if ( find( a , 0 , 10 , 56 ) ) printf( "みつけた¥n" ) ; }
再帰を使ったソートアルゴリズム
データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。
この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。
マージソートの分析
マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。
:
よって、
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。