出張の都合により、今日は授業を入替え、3年の授業。
構造体の理解については、明日の授業で演習を行う。今日は、振替えで演習室も使えないので、 普通の講義。

ビットフィールド

例えば、生年月日を記憶する場合、構造体を使えば以下のように宣言できるが、 int型(32bit=4byte)であれば、12byteを要する。

struct YMD {
   int  year ;
   int  month ;
   int  day ;
} ;

しかし、生年月日の比較などをする場合であれば、 年月日を10進数の桁に合わせて、日付を 20151109 といった数値で表すことも多い。 この場合であれば、int 型 2^31-1 = 2,000,000,000 にも収まる。 プログラムも解りやすくするのであれば、以下の様な補助関数を準備すれば良い。

int ymd10_year( int ymd ) {
   return ymd / 10000 ;
}
int ymd10_month( int ymd ) {
   return (ymd / 100) % 100 ;
}
int ymd10_day( int ymd ) {
   return ymd % 100 ;
}

しかし、このプログラムでは、日の1〜31までの数字のために、0〜99の10進2桁を使う。 月の1〜12のために0〜99の10進2桁を使う。 また、各桁を抜き出すために、除算を使うため処理も手間がかかる。

そこで、年月日を2進数の桁の組合せで保存することを考える。こうすれば、2進数のビットシフト命令で機械語では扱いやすくなる。

// 年(12bit),月(4bit),日(5bit) = Y,YYYY,YYYY,YYYM,MMMD,DDDD
int ymd2( int y , int m , int d ) {
   return (y << 9) | (m << 5) | d ;
}
int ymd2_year ( int ymd ) {
   return ymd >> 9 ;
}
int ymd2_month( int ymd ) {
   return (ymd >> 5) & 0xF ;
}
int ymd2 _day( int ymd ) {
   return ymd & 0x1F ;
}

しかし、この方法でデータを扱うと、月の値を1つ増やすといった処理を書こうと思うと、2進数の扱いに慣れていないと プログラムも間違いやすい。

int ymd = ymd2( 2015 , 11 , 9 ) ;
// ymd の月を12月に変更したい。
ymd = (ymd  & 0x1FFE1F) | (12 << 5) ;

このような処理のために、ビットフィールドを使用する。使い方は、構造体の要素の宣言の後ろに、": bit数"をかけばいい。 こうすれば、構造体の要素の参照の式をかけば、必要に応じて2進数を使った機械語命令をコンパイラが書いてくれる。

struct YMD {
   unsigned int  year  : 12 ;
   unsigned int  month : 4 ;
   unsigned int  day   : 5 ;
} ;

共用体

構造体と同じような文法の一つに共用体がある。 構造体では、異なる型の各要素のメモリの領域を準備するが、共用体では全要素が同じ場所を使う。 このため、どれか１つの値を覚えるだけでいい場合に使う。

union int_str4 {
   int  data ;
   char str[4] ;
} ;

union int_str4  a[4] ;
a[0].data = 1234 ;
strcpy( a[1].str , "ABC" ) ;
a[2].data = 2345 ;
strcpy( a[3].str , "BCD" ) ;
printf( "%d¥n" , sizeof( a ) ) ; // 4byte×4 = 16

この異なる型を同じ場所に覚えるための文法は、最近のオブジェクト指向のプログラム言語では、仮想関数という考え方 が利用できるので、あまり利用することは少なくなっている。

列挙型

プログラムの中で週のような情報を覚える時、日付の処理を考えると、 日=0,月=1,火=2,水=3,木=4,金=5,土=6　といった割り当てをすることも多い。 しかし、水曜の処理だったら…という時に、if ( week == 3 ) という書き方では、分かりにくい。

int wd = 1 ; // 月初めが月曜の場合...
int day ;
for( day = 1 ; day <= 31 ; day++ , wd = (wd + 1) % 7 ) {
   if ( wd == 3 ) {
      水曜日の処理...
   }
}
// マジックナンバーを使わない場合
#define SUN 0
#define MON 1
#define TUE 2
#define WED 3
: (略)
int wd = MON ; // 月初めが月曜の場合...
int day ;
for( day = 1 ; day <= 31 ; day++ , wd = (wd + 1) % 7 ) {
   if ( wd == WED ) {
      水曜日の処理...
   }
}

上のプログラムの後半のマジックナンバーを使わない例であれば、プログラムの意味も解りやすくなる。 しかし、#define を7つも書き並べるのは面倒だし、対応する数値を1つづつ増やしながら書くのは、 間違って修正するかもしれない。 こういう場合には、列挙型を用いる。

enum Week {
   SUN , MON , TUE , WED , THR , FRI , SAT
} ;
enum Week wd = MON ;
int day ;

for( day = 1 ; day <= 31 ; day++ ) {
   if ( wd == WED ) {
      水曜日の処理...
   }
   // wd 型は int ではないので、週番号を増やすのはちょっと面倒
   wd = (enum Week)( ( (int) wd + 1 ) % 7 ) ;
}

SQLの説明も大体終わったので、演習を行う。

SQLの演習

学内のアカウントでログインすれば、SQLite3 を使った簡単な演習ができる環境を 準備しているので、それを使って演習。 教科書で示されるデータなども、簡単に読み込めるようにしてある。

演習内容は、SQLでデータを検索する処理を2つ考え動かしてみる。 最低でも、2つのテーブルにまたがった処理であること。 できれば、副問い合わせなどを含んだ処理などにチャレンジすること。 また、そのSQL命令をC言語で記述したものを作り、 直積処理などの意味を考える。

提出は、SQL命令、C言語、説明、動作確認、考察が記載されていること。

• SQL実験環境
• C言語で書いた場合

前回の授業で、２分木の話の中にて構文木とかで複数の枝を持つ データ構造の話をしたので、今回はB木について説明

B木

B木はデータベースに利用されているデータ構造であり、 位数をNとした場合、１ノード内には、N個以上、2N未満のデータを持つ。 また、data[i-1] < x < data[ i ] の条件を満たすデータは、pointer[ i ] で示すノードに保存する。

// B木のデータ構造の宣言例
#define SIZE 2
struct BTree {
   int  size ; // ノード内のデータ件数
   int  data[ SIZE * 2 ] ;
   struct BTree* pointer[ SIZE * 2 + 1 ] ;
} ;

B木では、ノードにデータを追加する場合には、ノードが2Nにならないのであれば、単純にそのノードに データを追加する。追加してノード内データが2N個を越える場合には、 追加後のデータ列の中央値を、上位ノードに移動させ、そのノードは中央値の前後の２つのノードに分割を行う。

こうすることにより、データ追加時に一方的に延びる不均一な構造を避けることができる。

データベースシステム

このB木では、データを効率よく扱えるが、データベースシステムでは、目的の１件を探すだけでなく、 条件に合ったデータの組合せを全データの中から探す処理も重要となる。

この全件処理は、2分木であれば、再帰処理などを伴いデータベースシステムには取り扱いが困難となる。 そこで、全件をシーケンシャルにアクセスするための改良を施したB+木やB*木などを使う。

データベースシステムでは、データすべてを表形式で覚え、その表の組合せることで複雑なデータを表現する リレーショナルデータベースを使うことが多い。 詳しくは、５年データベースの講義資料を参照。

先日(10/28)の4EIの交流会にてバーベキューに参加しました。

地域経済分析システムRESASの出前講座を 内閣府地方創生推進室の方を招いて開催していただきました。

地方創成に何が必要かを分析するために、 オープンデータなどを集め視覚的に表示してくれるシステムであり、 様々な角度でのデータを地図上やグラフで表示してくれます。

福井県の耕作放棄地率

試しに、越前市などの農地情報を表示させてみましたが、 簡単な操作で耕作放棄地の率が表示できたりします。 そして、鯖江市や越前市が 放棄率が県平均よりかなり低く、 奥越の勝山市大野市も低いことが解りました。

だったら、県内の何処が耕作放棄地率を高めているのか…. 比較グラフを表示させてみたら、下記グラフのように、 嶺南….。 地方の様々な問題が、簡単に浮き彫りにできちゃいます。

ちなみに、RESASを用いた、「地方創生☆政策アイデアコンテスト」が開催中だそうです。

今日は、2分木の応用ということで、2項演算子の構文木と、意思決定木の説明を行う。

時間があまったので、対話システムの雑談から、eliza の話をして、 本当は人工無能「うずら」ちゃんの話をしようと思っていたけど、 チューリングテストの話になって、 アラン・チューリングの話になって、 映画イミテーションゲームの説明をして、 2045年問題の話をして….どんどん暗い話題に…

2項演算と構文木

先週の講義で、演算子の話をしておいたので、演算式の2分木で扱うプログラムを説明。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

１つのノードは、演算子か末端の数値であることに注目し、 右枝・左枝がNULLなら数値、それ以外は演算子として扱うとして…

struct Tree {
   int  data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
struct Tree* tree_int( int x )
{
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = n->right = NULL ;
   }
   return n ;
}
struct Tree* tree_op( int op ,
         struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = op ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
int eval( struct Tree* p ) {
   if ( p->left == NULL && p->right == NULL )
      return p->data ;
   else
      switch( p->data ) {
      case '+' : return eval( p->left ) + eval( p->right ) ;
      case '*' : return eval( p->left ) * eval( p->right ) ;
      }
}

void main() {
   struct Tree* exp =
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) , tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

関連する雑談として、プログラム言語の構文木の説明を行い、 (1) 字句解析 , (2) 構文解析 を組み合わせて作るけど、 字句解析支援ソフト(lex)や構文解析支援ソフト(yacc)などの紹介も行う。

意思決定木

意思決定木の説明ということで、yes/noクイズの例を示しながら、2分木になっていることを 説明しプログラムを紹介。

((意思決定木の例:うちの子供が発熱した時))
　　　　　　　38.5℃以上の発熱がある？
　　　　　　no／　　　　　　　　　＼yes
　　　元気がある？　　　　　　　　むねがひいひい？
　yes／　　　　＼no　　　　　　no／　　　　　＼yes
様子をみる　氷枕で病院　　解熱剤で病院　　速攻で病院

struct Tree {
   char *qa ;
   struct Tree* yes ;
   struct Tree* no ;
} ;
struct Tree* dtree( char *s , struct Tree* l , struct Tree* r )
{  struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->qa = s ;
      n->yes = l ;
      n->no = r ;
   }
   return n ;
}
void main() {
   struct Tree* p =
      dtree( "38.5℃以上の発熱がある?" ,
             dtree( "胸がひぃひぃ" ,
                    dtree( "速攻で病院" , NULL , NULL ) ,
                    dtree( "解熱剤で病院" , NULL , NULL ) ) ,
             dtree( "元気がある?" ,
                    dtree( "様子をみる" , NULL , NULL ) ,
                    dtree( "氷枕で病院" , NULL , NULL ) ) ) ;
   struct Tree* d = p ;
   while( d->yes != NULL || d->no != NULL ) {
      printf( "%s¥n" , d->qa ) ;
      scant( "%d" , &ans ) ;
      if ( ans == 1 )
         d = d->yes ;
      else if ( ans == 0 )
         d = d->no ;
   }
   printf( "%s¥n" , d->qa ) ;
}

今日は、構造体を使ったプログラミングの演習。 単純な演習だけでは、来週に研修旅行を予定している3年は授業の遅れも心配なので、 前半にワード境界の話をする。

ワード境界

struct Data {
   char name[3] ;
   int  point ;
} ;
struct Data array[3] ;
// 構造体の大きさは何バイト？
printf( "%d\n" , sizeof( struct Data ) ) ;
printf( "%d\n" , sizeof( array ) ) ;

簡単なデータのバイト数の知識だけであれば、Dataの大きさは、3byte+4byteの 7byteと思うかもしれない。しかし、この考えだと、array の配列は、メモリ上に以下に並ぶと思うであろう。

n1,n1,n1が、array[1].nameの3byteをあらわすとする。
n0,n0,n0,p0,p0,p0,p0,n1,n1,n1,p1,p1,p1,p1,n2,n2,n2,p2,p2,p2,p2

しかし、最近のコンピュータでは、CPUクロック2GHz,メモリクロック1GHzといった速度で、 メモリの速度はCPUに比べて遅い。このため、CPUがメモリのデータを読み出す際は、 複数のbyte数を一括して読み込む。このデータの単位は32bitコンピュータであれば、 4byte単位であったりする。

ワード境界を考えない構造体要素の配置の場合
0行目:n0,n0,n0,p0,
1行目:p0,p0,p0,n1,
2行目:n1,n1,p1,p1,
3行目:p1,p1,n2,n2,
4行目:n2,p2,p2,p2,
5行目:p2,--,--,--,

この場合、array[1].pointを読み出そうとすると2行目と3行目の2回にわけて データを読み込むことになり、プログラムの速度が落ちてしまう。

このため、構造体の要素をメモリに保存する場合、4byte毎の「ワード境界」を またがってデータを配置しないようにするのが普通である。こういう メモリへの配置を「ワードアライメント」という。

ワード境界を考え、途中に空き(xx)を配置した例
0行目:n0,n0,n0,xx,
1行目:p0,p0,p0,p0,
2行目:n1,n1,n1,xx,
3行目:p1,p1,p1,p1,
4行目:n2,n2,n2,xx,
5行目:p2,p2,p2,p2

ということで、sizeof( struct Data ) は、8byteとなるのが普通である。 ただし、処理速度を犠牲にしてメモリ量を節約する必要がある場合には、 "#pragma …."といったプリプロセッサ命令で、隙間を詰めることもできる。

「ワード」とは、8bit = 1byte より大きいデータ単位で、16bitであったり、32bitであったりする。 機械語でプログラムを記述する際には、以下のように区別することが多い。
16bit = 2byte = ワード(WORD),対応する型：short int
32bit = 4byte = ダブルワード(DWORD)、対応する型：int,float
64bit = 8byte = QWORD、対応する型：double

高専プロコンの競技部門や、プログラミング甲子園に、学生さんが参加しているけど、 パズル問題は再帰呼び出しとかの経験がないと難しい。

そこで、校内プロコンをやって実力をつけてもらおう…という話がでてきたので、 定番のパズル問題を、私なりにひねってみた。 プログラミング甲子園でも、同じ問題があったかもしれないけど、 一応私が考えた問題をいかに示す。

ぷよぷよ連鎖

6×6のます目に、ぷよぷよのブロックがいくつか落ちた 状態の情報が記録されている。 ブロックを１つ落とすなら、どこがいいか答えよ。

問題は、C言語の配列で与えられる。

• ぷよぷよのブロックの色は、アルファベット1文字で表現し、黄Y,緑G,赤R,青Bの4色とする。
• ブロックの無い場所には空白が入っている。
• 1行の7文字目には\0が入っていて、C言語の配列としては6×7とする。

(例)
char field[6][7] = {
   "      " ,
   "  GGGB" ,
   " YYYBG" ,
   " RRGRR" ,
   "BBRGRB" ,
   "RRBGBR" ,
} ;

このマス目にぷよぷよのブロックを1つ落とす。 どこに何色を落とすと何ブロック消せるか求め、 消えるブロック数が最大となる場合の、場所と色を答えよ。 連鎖のルールはぷよぷよと同じとする。

最大の式

文字列で与えられた数字と演算子を組み合わせて数式を作る。 その数式の最大値を答えよ。

式をつくる条件は以下の通りとする。

• 数字は1桁とし、必ず間に演算子を挟むこと。(43はNG)
• すべての文字を使わなくてもいい
• 同じ数字や演算子を2度使うのは禁止。112+*が与えられた場合、2*2+2はNG。2*1+1はOK
• 与えられる文字は、0-9,+,-,*,/,(,)
• 0除算が発生する式はNGで、C言語の文法として正しいこと。

int max_exp( char exp[] , char src[] ) {
   // src: 与えられる文字
   // exp: 答えの式
   // 返り値: その式の値
}
int main() {
   char ans[ 10 ] ;
   int ans = max_exp( ans , "1234+-*" ) ;
   printf( "%s = %d\n" , exp , ans ) ;
   // たぶん、4*3+2 が答えだと思う。
   return 0 ;
}

8クイーンの将棋バージョン

プログラミングの組み合わせ問題の有名なもので、8クイーンがある。 8クイーンは、チェスの盤面にお互いに取られないように、8つのクイーンの 置き方を答える問題。

これの将棋バージョンの問題として、以下2つの問題を答えよ。

9竜馬

9×9の将棋盤上に、竜馬(成り角)をお互い取られないように並べたい。 最大おける個数とその配置を答えよ。別解が複数ある場合は、最低１つ出力すればよい(全解でもよい)。

9桂馬

同じく、9×9の将棋盤上に、敵方向に向いた桂馬をできるだけ多く並べたい。 ただし、各桂馬は、次の１手が打てること。 次の１手で移動した先に、他の桂馬が無いこと。
この条件を満たすように桂馬を置く場合、最大いくつ置けるか？ その配置も答えよ。

評価方法

以上のプログラムを、すべての提出されたプログラムがそろった段階で、すべてを実行させ 最適解を答えられたものについて、処理速度とシンプルさで評価する。

処理速度は、答えやデバッグ用出力をすべてコメントアウトし、 処理関数を100回とか1000回とか複数回実行させるようにしたプログラムで、コンパイルする。 処理開始、処理終了の時間差を求めて比較する。(unixのtimeコマンドなどで比較)

プログラム言語は、問題趣旨に沿っていれば、なんでもよい。 ただし、コンパイル結果の時間で比べるため、 同一プログラムがJavaプログラムとCプログラムであれば、 C言語の方が有利となる。

プログラムのシンプルさについては、空白行やC言語のプリプロセッサ行を消した状態で、 一般的なプログラム清書プログラム(例えばcb)にかけた結果の行数が少ないものを勝ちとする。