前回の授業で、２分木の話の中にて構文木とかで複数の枝を持つ データ構造の話をしたので、今回は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