リスト処理の基本
来週からのテストということもあり、前半に簡単なリスト処理の基本を説明したあと、 後半はテスト勉強時間とした。
最初に復習のおまけとして、typedef や C++でのリストの宣言の違いを説明。
// 授業でのスタイル
struct List {
int data ;
struct List* next ;
} ;
// C言語でtypedefを使うスタイル
typedef struct LIST {
int data ;
struct LIST* next ;
} List ;
List* top = .... ;
// C++では、構造体名がそのまま使える
struct List {
int data ;
List* next ;
} ;
List* top = .... ;
簡単な補助関数を示して、基礎的なプログラム例を演習として行う。
struct List* cons( int x , struct List* n ) {
struct List* ans ;
if ( (ans=(struct List*)malloc(sizeof(struct List)))!=NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
void print( struct List* p ) {
for( ; p != NULL ; p = p->next ) {
printf( "%d" , p->data ) ;
}
}
int sum( struct List* p ) {
int ans ;
for( ans = 0 ; p != NULL ; p = p->next ) {
ans += p->data ;
}
return ans ;
}
void main() {
struct List* top = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
print( top ) ;
printf( "%d" , sum( top ) ) ;
}
FD講演会で認証評価に関する講演
今年度は、福井高専では学位授与機構にによる認証評価とJABEE審査が行われる。 講演では、認証評価に備えた説明があった。
この中で、特徴的と思われる点は、第2サイクルの評価に当たり、 「学生による事前学習」が重要とのことであった。 このため、シラバスには事前学習の内容を明記などが、必要となりそう。 特に各週毎に明記が理想とのことであった。
うーむ、シラバスの管理システムに、記述欄そんなに増やせるのかな…
グラフィックスと純粋仮想クラス
先週の純粋仮想基底クラスの事例を、具体的なプログラムでの演習とすべく、 下記資料を配布し、演習を行う。
最初に、他学科の学生であればGrWinを知らない可能性もあり、 本科3年向けの資料を配布し、説明を行う。 ただし、電気電子OB学生が中心であるため、GrWinは授業で経験済みであった。
Figure というdraw()という仮想関数を持つ純粋仮想基底クラスを宣言し、 FigureBox , FigureCircle という、具体的な図形のクラスを派生させ、 各描画関数 draw を示す。演習では、別の図形を派生させたり、 色つきクラスに拡張してもらうなどして、次のクラス設計の元ネタとすべく演習を予定。
2011年度授業アンケート
授業アンケート(2011年度)のデータが送付されてきた。 ということで、例年通りそのまま記載。
データベース
75.9→77.8でポイントは微増。 黒板やOHP資料のポイントが低い。 担任クラスでもあり、甘めの評価の懸念あり。
情報構造論
81.3→82.3でポイントは微増。 黒板やOHP資料のポイントが低い。 意見欄では、良かったや分かりやすかったの意見があり、 総じて良い評価であったと思われる。
創造工学演習
時間不足を指摘する意見が多い。 前年度の授業段階から事前準備などの提案もあり、 目的意識を持って取り組んだという意味では、良い傾向と思われる。
プログラミング応用
77.3→81.0でポイントも上がっている。 この科目では、黒板OHPのポイントが特に悪いという程ではない。 意見欄でも、プリントが分かりやすいとか理解が深まったとの 好印象な意見が得られた。 一方、授業中の演習が座学と区別しているため、実際にどんな動きをするのか見てみたかったとの意見もあった。
計算機システム
N進数変換とbit演算の応用
前回の授業で、#defineマクロやbit演算の説明をしたけど、 まだ詰めが甘かったので、開いたサブルーチン・閉じたサブルーチンなどの 説明を行い、標準関数などの説明も行う。
開いたサブルーチンと閉じたサブルーチン
#define マクロと、関数の違いを理解してもらうために、 プリプロセッサ・コンパイル・リンクといった機械語生成までの流れを説明し、 #define マクロを多用すると、同じ機械語が何度も生成され、機械語が肥大する 可能性を説明する。逆に関数を何度も利用しても、一箇所の機械語が使われるため 機械語の肥大は無いことを説明する。一方、関数では実引数・仮引数の 値渡しなどが発生するので、わずかとはいえ余計な処理時間を要することを説明。 この結果、#define マクロは、小さな関数向きであることを述べる。 また、関数は入口・出口が明確に作られることから、閉じたサブルーチンと呼ばれる。 逆に #define マクロは入口・出口が明確でなく、開いたサブルーチンと呼ばれることを 説明する。
N進数変換や文字列処理で使う標準関数
N進数変換や文字列処理で、ctype.h の isdigit() 関数や、stdlib.h の strtol() などの 標準関数を説明する。
型の問題と実行時のトラブル
1桁の数値と+,-記号で式の値を求めるeval() という関数を示し、 文字列処理のサンプルを説明する。このあと、以下の様な呼び出しの問題点を考えてもらう。
int eval( char s[] ) {
// 一桁の数値と"+","-"の計算式
// 例 printf( "%d" , eval( "1+2+3" ) ) ; // 6
}
void main() {
printf( "%d" , eval( 1+2+3 ) ) ; // 引数型の不一致
printf( "%d" , eval( '1+2+3' ) ) ; // 文字定数エラー
printf( "%d" , eval( "1+2+3" ) ) ; // OK
// よくありそうな書き間違い
char s[ 100 ] ;
scanf( "%s" , s ) ;
printf( "%d" , eval( s[100] ) ) ; // 引数型不一致
// 文字列ポインタの間違い
char* s ;
scanf( "%s" , s ) ; // 変な場所に文字列格納でメモリエラー
printf( "%d" , eval( s ) ) ;
//
char s[ 5 ] ;
scanf( "%s" , s ) ; // 1+2+3+4+5+6 を入力したら!?
printf( "%d" , eval( s ) ) ;
}
リスト構造
配列の利点・欠点を踏まえ、リスト構造の説明を行う。
配列は、N番目のデータ抽出が簡単であり、2分探索法では中央の値を 簡単に取り出せることから、O(log N)の処理が可能となる。 この一方で、C言語では配列サイズは固定であり、 最初の段階で適切なサイズが解らない場合は、メモリの使用効率を 低下させる。
これに加え、配列の欠点としてあげられるのが、途中データの削除・挿入となる。 配列の指定位置にデータを追加しようと思うと、 入れるべき場所に"空き"を作るために、以降のデータを１つ後ろにずらす必要がある。 削除でも同様に、１つ前にずらす処理が必要となる。 これにかかる処理時間は、最悪N件、最低で0件となることから、平均N/2回の ループを要し、O(N)の処理が必要となる。
これらの欠点の対応方法として、配列であれば、次のデータの入っている 場所を使えば良い。
((リストを配列で)) top: 3 data,next 0: 41 1 int data[..] ; 1: 60 -1 int next[..] ; 2: 10 4 for( p = top ; p >= 0 ; p = next[ p ] ) 3: 6 2 printf( "%d" , data[ p ] ) ; 4: 22 5 5: 34 0
この方法は、アパートの回覧板で、部屋の住人は「次の部屋の人の番号を知っていれば十分」という状況と同じである。 この方式であれば、たとえデータを追加したい場合でも、 例えば30を追加するのであれば、data[4]の後ろに追加したいのであり、 data[6] = 30 を保存し、next[4] = 6、next[6] = 5 とすれば、途中にデータを混ぜることができる。
この方法によって、データを途中に追加する場合でも、O(1)で挿入が可能となる。 (ただし挿入すべき場所を探すにはO(N)の時間を要する)
リスト構造
一方でこのままでは、data[],next[]の最初の配列サイズ以上のデータを保存することは できない。そこで必要に応じてメモリを確保する方法をとる。
// 基本となるリスト構造の宣言
struct List {
int data ;
struct List* next ;
} ;
// 手作業で地道にリストを生成
struct List* top ;
top = (struct List*)malloc( sizeof(struct List) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->data = 2 ;
top->next->next = (struct List*)malloc( sizeof(struct List) ) ;
top->next->next->data = 3 ;
top->next->next->next = NULL ;
// リストデータを表示
struct List* p ;
for( p = top ; p != NULL ; p = p->next )
printf( "%d" , p->data ) ;
このような方法であれば、必要に応じてメモリを確保するため、 配列サイズが途中で不足するといった事態を考える必要がない。 (mallocがNULLを返すことは考える必要があるけど…) 一方、欠点としては、データを参照する場合には、 先頭から１つづつアクセスする必要があり、 中央データを参照して２分探索といったテクニックは使えない。
いいねぇ〜 “素人でも使…(05/21)
- 05/21 いいねぇ〜 "素人でも使いやすい回路図エディタBSch3V" http://tinyurl.com/6wdovm #fnct
- 05/21 いいねぇ〜… RT @jun1s: 先日も、市内の某ＩＴ会社の役員達と飲んでいたわけだが、曰く、「いい人材の雇用はとかく難しい。面接やテストだけではなかなか測れない。奥が深い。しかし、高専卒は別。彼らは安心して採用できる。5年間彼らを見てきた先生達から意見を… #fnct
この記事は、
の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。
浮動小数点データ・bit演算・#defineマクロ
演習も終わった所で、同じプログラムを効率良く記述できることを知ることを 目標に、bit演算や#defineマクロを説明する。
浮動小数点データ
浮動小数点形式のデータは、float,double の2通りがあるが、最近はほとんど double 型で 計算をすれば十分。単精度実数(float)と、その倍の倍精度実数(double)
((float)) S:符号(1bit) E:指数部(8bit) F:仮数部(23bit) SEEE,EEEE,EFFF,FFFF,FFFF,FFFF,FFFF,FFFF 指数部 - 127 float = 1.仮数部 * 2 ((double)) S:符号(1bit) E:指数部(11bit) F:仮数部(52bit) SEEE,EEEE...EEEE,FFFF,FFFF,.....,FFFF,FFFF 指数部 - 1023 double = 1.仮数部 * 2
bit演算子
2進数,8進数,16進数の変換プログラムでは、 2,8,16といった数値で割った余りや、商を求めることが多い。 コンピュータ内は2進数で扱っているため、16での余りを求める計算は、 下4bitを取り出したり、16で割るという計算は4ビットシフトに置き換えられる。 そこで、AND(&),OR(|),XOR(^),NOT(~)などのbit演算を説明。
printf( "%d" , 5 & 3 ) ; // 0101 & 0011 = 0001 = 1)10 printf( "%d" , 5 | 3 ) ; // 0101 | 0011 = 0111 = 7)10 printf( "%d" , 5 ^ 3 ) ; // 0101 ^ 0011 = 0110 = 6)10 printf( "%d" , 5 << 2 ) ; // 0101 左2bitシフト = 010100 = 20)10 printf( "%d" , ~10 + 1 ) ; // 反転+1は2の補数 = -10
#defineマクロ
N進数変換のプログラムの中には、下記のような部分があるけど、これを シンプルに書くためには、#defineマクロがよく利用される。
char s[...] ;
if ( '0' <= s[i] && s[i] <= '9' ) ....
#define isdigit(C) ('0' <= (C) && (C) <= '9')
if ( isdigit( s[i] ) ) ...
C言語のプログラムは、最初にプリプロセッサと呼ばれる文字列置換プログラムによって、 #include や、#define の処理が行われる。 #define は、指定された文字を、指定された文字に置換する。 #define マクロは、それを関数的に記載できるようにしたもの。 閉じたサブルーチンと開いたサブルーチンの説明は次回に行う予定。
qmailとsudoの相性の問題?
先日、学科のメインサーバのアップデートで、sudoなども更新された。 これでMovableTypeの記事をメールで書き込む mail2entry.pl の動きがおかしくなった。
具体的には、今までは、sudo を使って www-data 権限を得て 記事を書き込んでいた。
(( .qmail-XXXX )) | /usr/bin/sudo -u www-data /usr/lib/cgi-bin/movabletype/mail2entry.pl
しかし、sudo-1.8.3p2 では、記事書き込み終了後に、mail2entry.pl が ZOMBIE になって処理が終わらず、上位プロセス sudo , qmail-local が残って しまう。このため、一定数以上のmovabletype記事書き込みが溜まると、 メールシステム全体がメール配達が止まったり遅配となっていた。
どうも、sudo の問題みたいなので、sudo を使わずに処理を行うように、 設定を変更した。具体的には、/var/qmail/users/assign によって、 www-data 権限を与えて動かすようにした。
(( /var/qmail/users/assign )) +mt-XXXX:www-data:33:33:/var/qmail/alias:-:mt-XXXX: (( /var/qmail/alias/.qmail-mt-XXXX )) | /usr/lib/cgi-bin/movabletype/mail2entry.pl (( 設定 )) # chmod 644 /var/qmail/alias/.qmail-mt-XXXX # qmail-newu # /etc/init.d/qmail restart
純粋仮想基底クラスと関数ポインタ
先週の仮想関数の説明の応用ということで、 コンテナクラスなどの話につなげるための純粋仮想基底クラスの説明を行う。 その前に、仮想関数の実装の元となっている関数ポインタを簡単に紹介する。
関数ポインタ
関数ポインタとは、名前の通りで、動作説明の簡単なプログラムを紹介。
int add( int x , int y ) { // 加算関数
return x + y ;
}
int mul( int x , int y ) { // 乗算関数
return x * y ;
}
void main() {
int (*f)(int,int) ; // int×2引数、返り値intの関数へのポインタ
f = add ;
printf( "%d" , (*f)( 2 , 3 ) ) ; // 5を表示
f = mul ;
printf( "%d" , (*f)( 2 , 3 ) ) ; // 6を表示
}
関数ポインタを利用すれば、異なるデータに対する処理を、 汎用性高く作ることも可能となる。
int intcmp( int* x , int* y ) { // 整数比較関数
if ( *x > *y )
return 1 ;
else if ( *x < *y )
return -1 ;
else
return 0 ;
}
int vmax( void* array , // 配列先頭アドレス
int size , // 配列データ件数
int sizeofdata , // 1件あたりのbyte数
int(*f)( void*,void* ) ) { // 比較関数
int i , max = 0 ;
for( i = 0 ; i < size ; i++ )
if ( (*f)( array + max * sizeofdata ,
array + i * sizeofdata ) )
max = i ;
return max ;
}
int idata[ 4 ] = { 11 , 33 , 22 , 44 } ;
char sdata[ 4 ][ 4 ] = { "ab" , "bc" , "aa" , "c" } ;
void main() {
int m ;
// intcmp関数を使って、idata から最大値を探す
m = vmax( idata , 4 , sizeof(int) , intcmp ) ;
printf( "%d" , idata[ m ] ) ;
// strcmp関数を使って、sdata から最大値を探す
m = vmax( sdata , 4 , sizeof(sdata[0]) , strcmp ) ;
printf( "%s" , sdata[ m ] ) ;
}
純粋仮想基底クラス
これらの仮想基底クラスの考え方をもっと利用すると、 1つの配列に、異なる型の派生クラスを保存することも可能となる。
// 純粋仮想基底クラス
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" , data ) ;
}
} ;
// 実数クラス
class DoubleObject : public Object {
private:
double data ;
public:
DoubleObject( double x ) { data = x ; }
virtual void print() {
printf( "%f" , data ) ;
}
} ;
// 文字列クラス
class StringObject : public Object {
private:
char* data ;
public:
StringObject( char* x ) { data = x ; }
virtual void print() {
printf( "%s" , data ) ;
}
} ;
void main() {
Object* a[ 3 ] ;
// 配列に整数・実数・文字列が混在できる。
a[0] = new IntObject( 123 ) ;
a[1] = new DoubleObject( 1.23 ) ;
a[2] = new StringObject( "abc" ) ;
// 混在したデータでも、正しく全要素をprint()できる
for( int i = 0 ; i < 3 ; i++ )
a[ i ]->print() ;
}