前回のコンストラクタなどの説明も終わったので、 今回は具体的な課題に取り組んでもらう。

最初に先週予告していたように、実部・虚部による複素数のクラスを宣言し、 加算と表示メソッドを作る。この後、オブジェクト指向の良さとして、 データ内部や手続き内部が隠蔽化されていれば、後でクラス設計者が 内部を、複素数の絶対値と偏角に変更しても、プログラムの利用者側の プログラムを一切変更せずに済むということを示す。

今回は、プロジェクタにエディタをそのまま投影しながら、 直接プログラムを書き、目の前でコンパイル＆実行しながら説明を行った。 時間の後半は、このクラスに乗算以外にもいろいろな複素数演算を加え、 呼び出し側のプログラムが変更不要といったことを実践できるような プログラムを作ることを目標として、課題に取り組んでもらう。

先週の最大選択法の処理時間の分析を、解説する。 具体的な説明は、先週の資料に記載したのでそちらを参照。 この後、2分探索法のブログラムを示し、オーダ記法の説明を行う。

2分探索法の分析

int data[ N ] ;     // dataはあらかじめ昇順にソート
int key = 探す値 ;
int L = 0 , R = N ; // [0,N)
while( R-L > 1 ) {
   int M = (L + R) / 2 ; // [L,M) , M , [M+1,R)
   if ( data[ M ] == key )
      break ;
   else if ( data[ M ] > key )
      R = M ;     // [L,M)
   else
      L = M+1 ;   // [M+1,R)
}

このプログラムでは、ループ1回につき、対象データ件数が約半分になる。 よって、m回ループをすれば、対象データ件数は、 となり、 データが見つからない最悪ケースでは、対象データ件数が1件になるまで繰り返す。 よって、 となり、 処理時間は、以下のように示される。

オーダ記法

処理速度の見積もりでは、単純ループはNに比例、 最大選択法では、に比例、 2分探索法では、 に比例ということが、アルゴリズムの処理時間の分析では重要となる。 そこで、「Nについてのどのような式に比例するのか？」を、オーダ記法で表す。 単純ループでは、、 最大選択法では、、 2分探索法では、といったように表記する。

最初に、先週の未消化分ということで、switch – case 文を説明。 caseラベルにジャンプする概念と、break 文の必要性を解説。

大域変数・動的局所変数・静的局所変数

変数には、寿命と有効範囲という概念が重要であり、 局所変数であれば、宣言されたブロックの中でのみ有効。 大域変数は、どこからでも使える変数で便利だけど、危険な使い方。 局所変数は、一般的に動的変数であり、ブロックに入った時に作られ、 ブロックを抜けると消滅する。 しかし、static キーワードを付けた局所変数は、静的変数となり、 プログラム起動時に作られ、プログラム終了まで生き残る。

int x = 123 ;            // 静的大域変数
void foo() {
int x = 234 ;        // 動的局所変数
x++ ;
printf( "%d" , x ) ;
}
void bar() {
static int x = 345 ; // 静的局所変数
x++ ;
printf( "%d" , x ) ;
}
void baz() {
x++ ;
printf( "%d" , x ) ;
}
void main() {
foo() ;   // 235
bar() ;   // 346
baz() ;   // 124
foo() ;   // 235
bar() ;   // 347
baz() ;   // 125
}

関数と引数

関数と引数の説明として、実引数のコピーが仮引数に渡されて、局所変数の仮引数は 関数処理と同時に消滅するという解説を行う。 これにより、関数での副作用が呼び出し側に伝わらないようにすることを説明。 一方で、関数の副作用を伝えたい場合は、値渡しではなく、ポインタ渡しをすることを説明。

// 値渡し(副作用が無い)
void foo( int x ) {
x++ ;
printf( "%d" , x ) ;
}
void main() {
int x = 123 ;
foo( x ) ;  // main::x とfoo::xは別の入れ物
foo( x ) ;
}
// ポインタ渡し(ポインタ経由で副作用)
void foo( int* p ) {
(*p)++ ;
printf( "%d" , *p ) ;
}
void main() {
int x = 123 ;
foo( &x ) ;
foo( &x ) ;
}

説明において、間違い・勘違いを防ぐためのテクニックとして、 switch-caseでは、最後の行にも breakを書くとか、次のcaseになだれ込みでも、/*no break*/ コメントを入れるとかのテクニックを紹介。 大域変数では、一時的な変数と間違われないように、使用目的が分かるような長い名前をつけるとか、大域変数は単語先頭を大文字、#define 定数は名前をすべて大文字とするといったような、 誤解されないテクニックも紹介する。

先日から、自宅に持ち帰って設定をしていたサーバが、 ようやく動いてくれるようになった。 新型の Software RAID 対応の組み込みRAIDコントローラだったけど、 Debianが対応が不十分なのか、Read-only の認識しかしてくれない。 やむなく、RAIDコントローラを使用せずに Software RAID を構成させた。

HDDにRAIDの下地となるパーティションの作成
　> SCSI1(0,0,0)(sda)-500GB ATA WDC XXXXXXXXX
　>  1.基本 128 MB B K raid  # md0(boot) -- 注:bootフラグを付ける
　>  2.基本 500 GB   K raid  # md1(LVM)
　> SCSI1(0,0,0)(sdb)-500GB ATA WDC XXXXXXXXX
　>  1.基本 128 MB B K raid  # md0(boot)
　>  2.基本 500 GB   K raid  # md1(LVM)

ブート起動用に128MBの領域を確保し、残りは /,/home,swap 用に使うけど、 /etc/sda,/etc/sdb でRAIDを構成させるために、領域種別にはraidを指定する。

ソフトウェアRAIDの設定
　MDデバイスの作成
　　種別=RAID1 , デバイス数=2 , スペアデバイス=0
/dev/sda1 /dev/sdb1 = RAID1 デバイス 0 # md0(boot)
/dev/sda2 /dev/sdb2 = RAID1 デバイス 1 # md1(LVM)

２つのHDDの４領域を、/dev/md0,/dev/md1 に組み合わせる。

boot領域の設定
　> RAID1 デバイス 0. - 128MB ソフトウェアRAIDデバイス
　>  1. ---- 128 MB   ext4   /boot
　> RAID1 デバイス 1. - 128MB ソフトウェアRAIDデバイス
　>  1. ---- 500 GB K lvm    # vg00(lv00:swap,lv01:root,lv02:home)

/dev/md0は、/boot に割り当てる。 /dev/md1は、lvm に構成させるために、領域種別には lvm を指定する。

LVMの設定
　論理ボリュームマネージャの設定
　　ボリュームグループの作成
　　　ボリュームグループ名 = vg00
　　　ボリュームグループデバイス = /dev/md1
　　論理ボリュームの作成 ( vg00 上)
　　　論理ボリューム名 lv00 =  12GB (swap用)
　　　論理ボリューム名 lv01 = 128GB (root用)
　　　論理ボリューム名 lv02 = 380GB (home用)
　> LVM VG vg00, LV lv00 -  12 GB Linux device-mapper(linear)
　>  1.  12 GB K スワップ スワップ
　> LVM VG vg00, LV lv01 - 128 GB Linux device-mapper(linear)
　>  1. 128 GB K ext4 /
　> LVM VG vg00, LV lv02 - 360 GB Linux device-mapper(linear)
　>  1. 360 GB K ext4 /home

lvm を論理ボリューム vg00 に全て割り当て、その中を swap用、root用、/home用に 区分けして、それぞれ割り当てる。

最初は、インストール後に再起動をかけたけど、bootしてくれない。 試行錯誤を繰り返すが原因がつかめなかったが、RAID設定が外れている状態でも、 異様な遅さがあったので、RAID処理が行われている雰囲気があった。 んで、最終的に、BIOS の設定で、Software RAID の設定があったので、 単独のHDDと認識するように設定を変更したら無事bootしてくれるようになった。

恒例の新入生歓迎会の一発芸なう。

使用前／使用後

先輩のいいとこを見習おう。

おまけ・寮の桜

前回の授業で、クラス宣言とメソッド定義の説明を終えているので、 今日は参照渡しの説明と、コンストラクタ・デストラクタの説明。

C言語での、値渡しとポインタ渡しの説明を行い、 関数呼び出しでの副作用の範囲を限定できることを説明。 これに加えて、ポインタ渡しを簡単に記述できる参照渡しの説明を行う。

// 参照渡しの例
void foo( int& x ) {
x++ ;
printf( "%d\n" , x ) ;
}
void main() {
int  a = 123 ;
foo( a ) ;  // 124
foo( a ) ;  // 125
}

例年よりは、C言語を分かっているようなので、今後C++のコードを読むと出てきそうな、 const 宣言や、inline 宣言を説明する。 inline 宣言では、Cであれば #define マクロを使っていた様な処理を、 通常の関数呼び出しと同じように書ける。

#define SQR(X) ((X)*(X))
inline int sqr( int x ) {
return x * x ;
}
void main() {
printf( "%d\n" , SQR( 1+2 ) ) ; // SQRの冗長な()が無いと...
printf( "%d\n" , sqr( 1+2 ) ) ;
}

一般的に、プログラムの間違いでは、初期化しないデータによるバグが多い。 オブジェクト指向では、オブジェクトを確実に初期化するための、コンストラクタ機能がある。

class Person {
private:
char name[ 20 ] ;
int  age ;
public:
void print() {
printf( "%s %d\n" , name , age ) ;
}
Person( char s[] , int a ) {
strcpy( name , s ) ;
age = a ;
printf( "Constructor " ) ;
print() ;
}
~Person() {
printf( "Destructor " ) ;
print() ;
}
} ;

質問：デストラクタはユーザが明示的に呼び出せるか？→無理…
自分自身の疑問：デストラクタがprivateだったら？→エラーが出た…

最初の授業ということで、シラバスなどのガイダンスに交えて、 「プログラムを作る時、何を考慮して書くべきか」という質問をしてみた。 こちらとしては、プログラムでのアルゴリズム評価の観点ということで、 「処理速度」、「使用メモリ量」、「アルゴリズムの複雑さ」という答えを 期待していたんだけれど、プログラムの見易さについての返答ばかり。 「処理速度」という答えがでるまでに随分と時間がかかってしまった。

速度・メモリ・複雑さの3つは、それぞれ速度優先のアルゴリズムは、メモリを大量消費したり、 プログラムが複雑になるなど、一方を優先すれば他方に悪影響のでる トレードオフの関係にあることを解説。 単純検索・2分探索法・全データメモリーマップなどの方法を例に挙げて説明を行う。 プログラム開発では、トレードオフの関係にあるからこそ、 その状況に応じたアルゴリズムを選択(デザイン)できるためにも、 速度・メモリ・複雑さを客観的に評価できる必要性がある。

速度の評価

まず手始めに、N件のデータを配列の中から探す処理で説明。

int  data[ N ] ;
int  key = ??? ;
for( int i = 0 ; i < N ; i++ ) {
   if ( data[ i ] == key )
      break ;
}

このプログラムの実行時間を考えると、最悪のケースでは、式の実行回数は、 i=0 | 1回、i < N | N+1回、i++,if(==) | N回となる。 よって、処理時間は、以下の式で示される。

このプログラムで、1000件で1msecの時間を要した場合、 10000件であれば、何秒かかるか？という問題があった場合、2変数1式であり 通常では処理時間を求めることができない。しかし、 処理速度の見積もりでは、大抵データ件数Nは巨大な場合がほとんどであり、 も、1回の初期化の時間であり、きわめて小さい値が一般的であり、無視できる。 よって、 から、10000件では、10msecという予想時間を求めることができる。

次に、もう少し複雑な例ということで、データの並び替えで最大選択法の プログラムを示し、処理時間を議論する。

int  data[ N ] ;
int  i , j , m , t ;
for( i = 0 ; i < N-1 ; i++ ) {
   m = i ;
   for( j = i+1 ; j < N ; j++ )
      if ( data[ m ] < data[ j ] )
         m = j ;
   t = data[ m ] ;
   data[ m ] = data[ i ] ;
   data[ i ] = t ;
}

内部のjのループの実行回数は、(N-1-i) 回であり、 これを外側iのループで回すため、以下のような式で示される。

プログラミング応用の最初ということで、授業の方針やシラバスを示しながら、 テストや評価方法などを解説。後半は、プログラミングの基礎を改めて説明。

制御構文：C言語の復習ということで制御構文について示す。 最初に文の定義として、式や制御構文、複文、空文などを説明し、 複数の文から大きな文が作られることを話す。 理解確認のために、例年通りforループの処理順序を書かせながら、 if(式)文 else 文、while(式)文、do 文 while(式) ; 、for(式;式;式) 文、break、continueなどを説明する。 breakなどで goto 文はほぼ不要となっている話の雑談として、 構造化プログラミングについて話し、処理の構造化・データの構造化を解説。 用語として、インデント、ネスティング(入れ子)など。

来週は、switch(…) case などの説明から。