ホーム » スタッフ » 斉藤徹 » 講義録 » 情報構造論

情報構造論」カテゴリーアーカイブ

2020年1月
« 12月    
 1234
567891011
12131415161718
19202122232425
262728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

情報構造論2019-講義録

オブジェクト指向と情報構造論と演習

データ構造を扱うプログラムの書き方を説明してきたので、それらを便利に書くためのオブジェクト指向の入り口を紹介する。

データ指向のプログラム記述

名前と年齢のデータを扱うプログラムを書く時、私なら以下のようなプログラムを作成する。

このプログラムの書き方では、saitohというデータにset_NameAge() , print_NameAge() を呼び出していて、データに対して処理を加えるという雰囲気がでている。このようにプログラムを書くと、saitoh というデータに対して命令するイメージとなり、擬人化したデータに向かってset,printしろ…って命令しているように見える。

// 名前と年齢の構造体 
struct NameAge {
   char name[ 20 ] ;
   int  age ;
} ;

// NameAgeを初期化する関数
void set_NameAge( struct NameAge* p , char s[] , int a ) {
   strcpy( p->name , s ) ;
   p->age = a ;
}

// NameAgeを表示する関数
void print_NameAge( struct NameAge* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}

void main() {
   struct NameAge saitoh ;

   set_NameAge( &saitoh, "t-saitoh" , 53 ) ;
   print_NameAge( &saitoh ) ;

   // NameAge の中身を知らなくても、
   // set_NameAge(),print_NameAge() の中身を見なくても、
   // saitoh を set して print する....という雰囲気は伝わるよね!!  
}

このプログラムでは、例えば、データに誕生日も覚えたいという改良を加えるとしても、main の前のデータ構造と関数の部分は色々と書き換えることになるだろうけど、main の内部はあまり変わらないだろう。こういう状態なので、プログラムを作成するときには、データ構造とそれを扱う関数を記述する人と、データ構造を使う人(main内部を書く人)と、分業ができるようになる。

隠蔽化

このような記述では、データ構造の中身を知らなくても、main で、setしてprintして…という処理の雰囲気は分かる。さらに、set_NameAge()とか、print_NameAge() の処理の中身を知らなくても、設定するとか表示するとか…は予想できる。

これは、NameAge というデータをブラックボックス化して捉えていると見れる。データ構造の中身を知らなくてもプログラムを理解できることは、データ構造の隠蔽化という。また、関数の中身を知らなくても理解できることは、手続きの隠蔽化という。

オブジェクト指向プログラミング

前述のように、プログラムを書く時には、データ構造とそのデータを扱う関数を一緒に開発するのが一般的である。オブジェクト指向プログラミングでは、データ構造その関数(メソッドと呼ぶ)をまとめてクラスと呼ぶ。

class NameAge {
private:
   // データ構造の宣言
   char name[ 20 ] ;
   int  age ;

public:
   // メソッドの定義
   void set( char s[] , int a ) { // 初期化関数
      strcpy( name , s ) ;
      age = a ;
   }
   void print() {                 // 表示関数
      printf( "%s %d¥n" , name , age ) ;
   }
} ;

void main() {
   NameAge saitoh ;
   saitoh.set( "t-saitoh" , 53 ) ;
   saitoh.print() ;
}

このプログラムでは、saitoh というデータ(具体的なデータオブジェクトと呼ぶ)に対して、set() , print() を呼び出している。

オブジェクト指向では、データに対して private を指定すると、クラス以外でその要素を扱うことができなくなる。これにより、クラスを設計する人と、クラスを使う人を明確に分けることができ、クラスを使う人が、クラス内部の変数を勝手に触ることを禁止できる。

プログラムを記述する時には、データ件数を数える時に、カウンタの初期化を忘れて動かないといった、初期化忘れも問題となる。オブジェクト指向のプログラム言語では、こういうミスを減らすために、データ初期化専用の関数(コンストラクタ)を定義することで、初期化忘れを防ぐことができる。

// コンストラクタを使う例
class NameAge {
   // 略
public:
   NameAge( char s[] , int a ) { // データ初期化専用の関数
      strcpy( name , s ) ;       //  コンストラクタと呼ぶ
      age = a ;
   }
   // 略
} ;
void main() {
   NameAge saitoh( "t-saitoh" , 53 ) ; // オブジェクトの宣言と初期化をまとめて記述できる。
   saitoh.print() ;
}

最近のC++なら

最近のオブジェクト指向プログラミングは、テンプレート機能と組み合わせると、単純リスト処理が以下のように書けてしまう。struct 宣言やmalloc()なんて出てこない。(^_^;

#include <iostream>
#include <forward_list>
#include <algorithm>

int main() {
  // std::forward_list<>線形リスト
  std::forward_list<int> lst{ 1 , 2 , 3 } ;

  // リスト先頭に 0 を挿入
  lst.push_front( 0 ) ;


  // 以下のような処理を最新のC++なら...
  //   for( struct List*p = top ; p != NULL ; p = p->next )
  //     printf( "%d¥n" , p->data ) ;

  // 通常の反復子iteratorを使って書いてみる。
  //   auto は、lst の型推論。
  //   本来なら、std::forward_list<int>::iterator itr = lst.begin() と書く。
  for( auto itr = lst.begin() ;
       itr != lst.end() ;
       itr++ ) {
    std::cout << *itr << std::endl ;
  }

  // 同じ処理を algorithm を使って書く。
  std::for_each( lst.begin() ,
                 lst.end() ,
                 []( int x ) { // 配列参照のコールバック関数
                   std::cout << x << std::endl ;
                 } );

  // 特に書かなくてもデストラクタがlstを捨ててくれる。
  return 0 ;
}

演習(ハッシュ法)

ハッシュ法のプログラム(オープンアドレス法もしくはチェイン法)を用いて、
(1)名前と電話番号,(2)名前と住所,(3)名前と誕生日について、名前をキーとして検索するプログラムを作成せよ。

原則として「出席番号 % 3 + 1」の番号のテーマに取り組むこと。

レポートを作成する際には、ハッシュ関数を変更してどういった変化があるか確認せよ。
ハッシュサイズは、10〜20件程度で良い。

動的メモリ確保(malloc()とfreelist)

C言語では、動的メモリ領域をどのように管理していくのか解説する。

局所変数とスタック

局所変数は、関数に入った時に作られるメモリ領域であり、関数の処理を抜けると自動的に開放されるデータ領域である。

関数の中で関数が呼び出されると、スタックには戻り番地情報を保存し、関数に移動する。最初の処理で局所変数領域が確保され、関数を終えると局所変数は開放される。
この局所変数の確保と開放は、最後に確保された領域を最初に開放される(Last In First Out)ことから、スタック上に保存される。

baz()の中で、「*((&c)+8) = 123 ;」を実行したら、bar()のxを書き換えられるかも…

動的メモリ領域とフリーリスト

動的なメモリ領域(ヒープ領域)は、malloc()関数で処理用のメモリを借りfree()関数で使わなくなったメモリを返却する。

この返却されたメモリ領域は、改めて malloc() が呼び出されたときに再利用を行う。この再利用するメモリ領域は、簡単に扱えるようにリスト構造にして保存する。この free された再利用候補のリスト構造は、free_list と呼ばれる。

mallocが一定サイズの場合

仕組みを理解する第1歩として、free_list の考え方を説明するために、malloc() でのメモリサイズが一定として説明を行う。free_list には、貸し出すためのメモリ空間をリスト構造で繋がった状態にしておく。

malloc() が呼び出される度に、free_list の先頭から貸し出すメモリを取り出し(a=malloc(),b=malloc(),c=malloc()まで)、free() が呼び出されると、返却されたメモリは、free_list の先頭につないでおく。

任意サイズのメモリ確保の場合

最初のステップでの説明は、mallocのメモリサイズを一定としていたが、本来は確保するメモリサイズが指定する。この場合は、以下の様に管理されている。mallocで貸し出されるメモリ空間には、ヒープメモリの利用者が使うブロックの前に、次のメモリブロックへのポインタとブロックサイズを記憶する領域をつけておく。こういったメモリブロックを free_list の考え方と同じようにリスト構造となるようにつないで保存されている。

この図の一番下の赤部分は、次のメモリブロックへのポインタとブロックサイズの大きさが20byteの場合の例。

malloc() で、指定されたサイズのものが、free_list の中にあれば、それを使う。malloc(40)

丁度いいサイズが無い場合は、それより大きいメモリブロックの後半を切り分けて、貸し出す。malloc(60)

free()の処理とメモリブロックの併合

この例の最後の処理では、20byte,60byte,40byte,50byteが併合された例。併合後のブロックサイズは、すこしいい加減に書いてある。

使用されていたメモリブロックが free() で返却された場合は、free_list につないでいく。ただし、単純にリストに繋ぐだけであれば、malloc(),free() を繰り返すと、小さなメモリブロックばかりになってしまい、大きいメモリのmalloc()ができなくなる。

そこで、free() で返却される際には、隣り合うメモリブロックと併合できるかを確認し、大きなメモリブロックになるような処理を行う。

また、隣り合うメモリブロックが併合できるかの判定が簡単になるように、free_listにつなぐ際は、次のメモリブロックへのポインタは、昇順となるように並べる。

一般的には、上記のようにmalloc(),free()を行うが(K&Rのmallocアルゴリズム)、mallocのサイズが小さい場合には小さいメモリブロック毎にnextブロックポインタやブロックサイズを記憶する場合、メモリのムダが多い。
そこで、最初に説明した一定サイズのmalloc()の手法で、8byte専用のfreelist,16byte専用のfreelist,32byte専用のfreelistのように2Nbyteのfreelistで管理する。10byteといった中途半端なサイズの時は、それより大きい16byteのfreelistを使う。(dlmallocのアルゴリズム)

ヒープメモリの断片化

ヒープメモリの malloc() , free() を繰り返すと、最悪、以下の図の様に、使用中領域(赤)とfreeされた未使用領域(黒)が交互に並ぶ状態が発生するかもしれない。この場合、全体の未使用領域の合計では十分なサイズでも、小さなメモリブロックばかりとなって、大きなメモリブロックを要求されても十分な大きさのメモリが見つからない状態が発生する場合がある。

この状態をヒープメモリの断片化といい、使用しづらい小さなメモリブロックはヒープホールと呼ばれる。

(補足) 断片化

断片化というと、OSではハードディスクの断片化(フラグメンテーション)を思い浮かべるかもしれない。ハードディスクの断片化とは、ファイル領域の割り当てとファイルの削除を繰り返すことで、ファイルのセクタが不連続となり、アクセス効率が悪くなる現象。OSによっては、ファイル実体の位置を動かすことで断片化を改善できる。以下の図のようにフラグメンテーションを防ぐための実体の移動を行う最適化はデフラグと呼ばれる。

上記の図では、上の青の図が断片化が発生している事例で、a1→a2,a2→a3の時にヘッド移動(シーク時間)が発生する。下の赤の図のように、デフラグ処理を施すことでシーク時間が減らせる。

Windows が 95,98,Me といった時代ではOSが不安定で、フラグメントが多く発生する場合Windowsがフリーズすることが多く、OSが不安定になったらデフラグを実行する…というテクニックが定番だった。最新のWindowsでは、デフラグが自動的に実行されるのでユーザが意識的に実行する機会はほぼなくなった。

文字列のハッシュ値と共有のあるデータの取り扱い

文字列のハッシュ値

ここまでで説明した事例は、電話番号をキーとするものであり、余りを求めるだけといったような簡単な計算で、ハッシュ値が求められた。しかし、一般的には文字列といったような名前から、ハッシュ値が欲しいことが普通だろう。

ハッシュ値は、簡単な計算で、見た目デタラメな値が求まればいい。 (ただしく言えば、ハッシュ値の出現確率が極力一様であること)。一見規則性が解らない値として、文字であれば文字コードが考えられる。複数の文字で、これらの文字コードを加えるなどの計算をすれば、 偏りの少ない値を取り出すことができる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum + s[i] ;
   }
   return sum % SIZE ;
}

文字列順で異なる値となるように

前述のハッシュ関数は、”ABC”さんと”CBA”さんでは、同じハッシュ値が求まってしまう。文字列順で異なる値が求まるように改良してみる。

int hash_func( char s[] ) {
   int sum = 0 ;
   for( int i = 0 ; s[i] != '¥0' ; i++ ) {
      sum = sum*2 + s[i] ;
      // sum = (sum * 小さい素数 + s[i]) % 大きい素数 ;
   }
   return sum % SIZE ;
}

共有のあるデータの取扱の問題

リスト構造で集合計算の和集合を求める処理を考える。

// 集合和を求める処理
struct List* join( struct List* a , struct List* b )
{  struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( ans , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
void list_del( struct List* p )
{                            // ダメなプログラムの例
   while( p != NULL ) {      // for( ; p != NULL ; p = p->next )
      struct List* d = p ;   //    free( p ) ;
      p = p->next ;
      free( d ) ;
   }    
}

void main() {
   // リストの生成
   struct List* a = cons( 1 , cons( 2 , cons( 3 , NULL ) ) ) ;
   struct List* b = cons( 2 , cons( 3 , cons( 4 , NULL ) ) ) ;
   struct List* c = join( a , b ) ; // c = { 1, 1, 2, 3 }
                                     //          ~~~~~~~ ここは b
   // a,b,cを使った処理

   // 処理が終わったのでa,b,cを捨てる
   list_del( a ) ;
   list_del( b ) ;
   list_del( c ) ; // list_del(b)ですでに消えている
}                  // このためメモリー参照エラー発生

このようなプログラムでは、c=join(a,b) ; が終わると下の図のようなデータ構造となる。しかし処理が終わってリスト廃棄list_del(c), list_del(b), listdel(a)を行おうとすると、bの先のデータは廃棄済みなのに、list_del(c)の実行時に、その領域を触ろうとして異常が発生する。

参照カウンタ法

上記の問題は、b の先のリストが c の一部とデータを共有しているために発生する。この解決方法として簡単な方法では、参照カウンタ法が用いられる。

参照カウンタ法では、データを参照するポインタの数をデータと共に保存する。

  • データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に1とする。
  • 処理の中で共有が発生すると、参照カウンタをカウントアップする。
  • データを捨てる際には、参照カウンタをカウントダウンし、0になったら本当にそのデータを消す。
struct List {
   int          refc ; // 参照カウンタ
   int          data ; // データ
   struct List* next ; // 次のポインタ
} ;

void list_del( strcut List* p ) {  // 再帰で全廃棄
   if ( p != NULL
        && --(p->refc) <= 0 ) {    // 参照カウンタを減らし
      list_del( p->next ) ;        // 0ならば本当に消す
      free( p ) ;
   }
}

ただし、参照カウンタ法は、循環リストではカウンタが0にならないので、取扱いが苦手。

参照カウンタ法が用いられている事例をあげよ。

ガベージコレクタ

では、循環リストの発生するようなデータで、共有が発生するような場合には、どのようにデータを管理すれば良いだろうか?
最も簡単な方法は、処理が終わっても、使い終わったメモリを返却しない、方法である。ただし、このままでは、メモリを使い切ってしまう。

そこで、廃棄処理をしないまま、ゴミだらけになってしまったメモリ空間を再利用するのが、ガベージコレクタである。
ガベージコレクタは、貸し出すメモリ空間が無くなった時に起動され、

  1. すべてのメモリ空間に、「不要」の目印をつける。(unmark処理)
  2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
  3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)


この方式は、マークアンドスイープ法と呼ばれる。ただし、このようなガベージコレクタが動く場合は、他の処理ができず処理が中断されるので、コンピュータの操作性という点では問題となる。

最近のプログラミング言語では、参照カウンタとガベージコレクタを取り混ぜた方式でメモリ管理をする機能が組み込まれている。このようなシステムでは、局所変数のような生成され関数終了といったすぐに不要となる領域は、ガベージコレクタで管理し、大域変数のような長期間保管するデータはガベージコレクタで管理される。

 

ハッシュ法

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、2分探索ならO(log N)となる)、単純リスト(データ検索(シーケンシャルアクセスしかできないのでO(N)となる)、2分探索木( O(log N) ) といった手法を説明してきた。しかし、もっと高速なデータ検索はできないのであろうか?

究極のシンプルなやり方(メモリの無駄)

最も簡単なアルゴリズムは、電話番号から名前を求めるようなデータベースであれば、電話番号自身を配列添え字番号とする方法がある。しかしながら、この方法は大量のメモリを必要とする。

// メモリ無駄遣いな超高速方法
struct PhoneName {
   int  phone ;
   char name[ 20 ] ;
} ;

// 電話番号は6桁とする。
struct PhoneName table[ 1000000 ] ; // 携帯電話番号ならどーなる!?!?

// 配列に電話番号と名前を保存
void entry( int phone , char* name ) {
   table[ phone ].phone = phone ;
   strcpy( table[ phone ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   return table[ phone ].name ;
}

しかし、50人程度のデータであれば、電話番号の末尾2桁を取り出した場合、同じ数値の人がいることは少ないであろう。であれば、電話番号の末尾2桁の値を配列の添え字番号として、データを保存すれば、配列サイズは100件となり、メモリの無駄を減らすことができる。

ハッシュ法

先に述べたように、データの一部を取り出して、それを配列の添え字番号として保存することで、高速にデータを読み書きできるようにするアルゴリズムはハッシュ法と呼ばれる。データを格納する表をハッシュ表、データの一部を取り出した添え字番号はハッシュ値、ハッシュ値を得るための関数がハッシュ関数と呼ばれる。

// ハッシュ衝突を考えないハッシュ法

#define HASH_SIZE 100 ;
struct PhoneName table[ HASH_SIZE ] ;

// ハッシュ関数
int hash_func( int phone ) {
   return phone % HASH_SIZE ;
}

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ; 
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   return table[ idx ].name ;
}

ただし、上記のプログラムでは、電話番号の末尾2桁が偶然他の人と同じになることを考慮していない。
例えば、データ件数が100件あれば、同じ値の人も出てくるであろう。このように、異なるデータなのに同じハッシュ値が求まることを、ハッシュ衝突と呼ぶ。

たとえ話で言うなら、100個の椅子が連番付きで並んでいて、自分の電話番号末尾2桁の場所に座ろうとしたら、先に座っている人がいるような状態である。このような状態で、あなたなら何処に座るだろうか?

ハッシュ関数に求められる特性

ハッシュ関数は、できる限り同じような値が求まるものは、ハッシュ衝突が多発するので、避けなければならない。例えば、6桁の電話番号の先頭2桁であれば、電話番号の局番であり、同じ学校の人でデータを覚えたら、同じ地域の人でハッシュ衝突が発生してしまう。また、ハッシュ値を計算するのに、配列の空き場所を一つ一つ探すような方式では、データ件数に比例した時間がかかり、高速なアルゴリズムでなくなってしまう。このことから、ハッシュ関数には以下のような特徴が必要となる。

  • 同じハッシュ値が発生しづらい(一見してデタラメのように見える値)
  • 簡単な計算で求まること。
  • 同じデータに対し常に、同じハッシュ値が求まること。

オープンアドレス法

先の椅子取りゲームの例え話であれば、先に座っている人がいた場合、最も簡単な椅子に座る方法は、隣が空いているか確認して空いていたらそこに座ればいい。

これをプログラムにしてみると、以下のようになる。このハッシュ法は、求まったアドレスの場所にこだわらない方式でオープンアドレス法と呼ばれる。

// オープンアドレス法
// table[] は大域変数で0で初期化されているものとする。

// 配列に電話番号と名前を保存
void entry( int phone , name ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 )
      idx = (idx + 1) % HASH_SIZE ;
   }
   table[ idx ].phone = phone ;
   strcpy( table[ idx ].name , name ) ;
}

// 電話番号から名前を調べる
char* search( int phone ) {
   int idx = hash_func( phone ) ;

   while( table[ idx ].phone != 0 ) {
      if ( table[ idx ].phone == phone )
         return table[ idx ].name ;
      idx = (idx + 1) % HASH_SIZE ;
   }
   return NULL ; // 見つからなかった
}

注意:このプログラムは、ハッシュ表すべてにデータが埋まった場合、無限ループとなるので、実際にはもう少し改良が必要である。

チェイン法

前に述べたオープンアドレス法は、ハッシュ衝突が発生した場合、別のハッシュ値を求めそこに格納する。配列で実装した場合であれば、ハッシュ表以上の データ件数を保存することはできない。

チェイン法は、同じハッシュ値のデータをグループ化して保存する方法。 同じハッシュ値のデータは、リスト構造とするのが一般的。

#define SIZE 100
int hash_func( int ph ) {
   return ph % SIZE ;
}
struct PhoneNameList {
   int phone ;
   char name[ 20 ] ;
   struct PhoneNameList* next ;
} ;
struct PhoneNameList* hash[ SIZE ] ; // NULLで初期化

struct PhoneNameList* cons( int ph ,
                            char* nm ,
                            struct PhoneNameList* nx ) {
   struct PhoneNameList* ans ;
   ans = (struct PhoneNameList*)malloc(
                      sizeof( struct PhoneNameList ) ) ;
   if ( ans != NULL ) {
      ans->phone = ph ;
      strcpy( ans->name , nm ) ;
      ans->next = nx ;
   }
   return ans ;
}

void entry( int phone , char* name ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , name , hash[ idx ] ) ;
}
char* search( int phone ) {
   int idx = hash_func( phone ) ;
   struct PhoneNameList* p ;
   for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
      if ( p->phone == phone )
         return p->name ;
   }
   return NULL ;
}

講義録に動くサンプルコードを併記

長男からプログラミングの授業の質問が LINE で流れてきて、大学の先生の資料を覗き見。その大学の課題ではサンプルコードの配布がしっかりしている。私の講義録でもサンプルコードは掲載しているけど、プロジェクタで掲示しながら授業をするため、#include 行を省略したり、main を void 宣言したりと、そのまま入れても動かない。

そこで、ダウンロードすれば「そのまま動くサンプルコード」を積極的に入れるようにしてみよう。

まずは、後期の情報構造論の半分ほどのサンプルコードを動く様に加筆し、テキストファイルへのリンクを埋め込んだ。

データベースについても、学内向けのSQLite3を使った実験環境にて動作ができるように、若干の改良を加え、リンクを埋め込んだ。

前期分は、来年度の授業の中で修正していこう。

B木とデータベース

2分探索木の考え方を拡張したもので、B木がある。

B木の構造

2分木では、データの増減で木の組換えの発生頻度が高い。そこで、1つのノード内に複数のデータを一定数覚える方法をとる。B木では、位数=Nに対し、最大2N個のデータd0..d2N-1と、2N+1本のポインタp0..p2Nから構成される。piの先には、di-1<x<di を満たすデータが入った B木のノードを配置する。ただし、データの充填率を下げないようにするため、データは最小でもN個、最大で2N個を保存する。

B木からデータの検索

データを探す場合は、ノード内のデータ diの中から探し、見つからない場合は、ポインタの先のデータを探す。位数がある程度大きい場合、ノード内の検索は2分探索法が使用できる。また、1つのノード内の検索が終われば、探索するデータ件数は、1/N〜1/2Nとなることから、指数的に対象件数が減っていく。よって、検索時間のオーダは、O(logN) となる。

B木へのデータの追加

B木にデータを追加する場合は、ノード内に空きがあれば、単純にデータの追加を行う。ノード内のデータが2N個を越える場合は、以下のような処理を行う。

ノード内のデータと追加データを並べ、その中央値を選ぶ。この中央値より大きいデータは、新たにつくられたノードに移す。中央値のデータは上のノードに追加処理を行う。このような方法を取ることで、2分木のような木の偏りが作られにくい構造となるようにする。

データを削除する場合も同様に、データ件数がN個を下回る場合は、隣接するノードからデータを取ってくることで、N個を下回らないようにする。

B木とデータベース

このB木の構造は、一般的にデータベースのデータを保存するために広く利用されている。

データベースシステムでは、データを効率よく保存するだけでなく、データの一貫性が保たれるように作られている。
例えば、データベースのシステムが途中でクラッシュした場合でも、データ更新履歴の情報を元にデータを元に戻し、データを再投入して復旧できなければならない。データを複数の所からアクセスした場合に、その順序から変な値にならないように、排他制御も行ってくれる。

データベースで最も使われているシステムは、データすべてを表形式で扱うリレーショナル・データベースである。

((リレーショナル・データベースの例))
STUDENT                             RESULT
ID   | name     | grade | course    ID   | subject | point
-----+----------+-------+--------   -----+---------+-------
1001 | t-saitoh |  5    | EI        1001 | math    | 83
1002 | sakamoto |  4    | E         1001 | english | 65
1003 | aoyama   |  4    | EI        1002 | english | 90

((SQLの例))
select STUDENT.name, RESULT.subject, RESULT.point --射影--
   from STUDENT , RESULT                          --結合--
   where STUDENT.ID == RESULT.ID    -- 串刺し --   --選択--
         and RESULT.point >= 60 ;

((上記SQLをC言語で書いた場合))
for( st = 0 ; st < 3 ; st++ )                   // 結合
   for( re = 0 ; re < 3 ; re++ )
      if ( student[ st ].ID == result[ re ].ID  // 選択
        && result[ re ].point >= 60 )
           printf( "%s %s %d" ,                 // 射影
                   student[ st ].name ,
                   result[ re ].subject ,
                   result[ re ].point ) ;

B+木

データベースの処理では、目的のデータを O(log N) で見つける以外にも、全データに対する処理も重要である。この場合、全てのデータに対する処理では、単純なB木では再帰呼び出しが必要となる。しかし、他の表でも再帰処理を伴うと、プログラムは複雑になってしまう。

そこで、B木のデータを横方向に並べて処理を行う場合に、その処理が簡単になるように B+木が用いられる。
この方法では、末端のノードは、隣接するノードへのポインタを持つ。

ポインタの先には何がある?

学生さんから「ポインタの先には何があるの?」との質問があった。

私が「そのポインタの型のデータ」と答えると、さらに「ポインタはメモリの場所。でもメモリには int や char や double といった色んなデータがある。そんな色々なデータの中からデータを取り出すんだから、そこにはどんなデータが入っているのか判らないとデータを取り出せないんじゃ?」と疑問をぶつけてきた。

なるほど、本当の疑問点が見えてきた。

最近のPython等の動的型付け言語の場合

# ポインタの質問だから、C言語の場合を答えればいいんだけど…

最近の Python , PHP といった変数が型を持たない「動的型付け言語」は、まさに質問の通り。データを取り出すためには、型の情報が必要。こういう言語は、基本型以外のデータはすべて参照型(要はポインタ)なので、変数の指し示す先には型情報とそのデータがペアで保存されているので、その型情報をみてデータを取り出している。

C言語の場合(静的型付け言語)

C言語では、ポインタは単なるメモリの場所を表すだけ。ポインタの先にはデータがある。(だからデータしかないって!)

メモリからデータを読み出すときに、int 4byte で取り出すのか、 double 8byte で取り出すかどうやってわかるの?と思うかもしれないけど、そのポインタの変数がどういう型へのポインタで定義されているかプログラムを読めばわかる。それに従って取り出せばいい。こういう言語は「静的型付け言語」という。

となると「じゃあ int のデータを char として読めるの?」と思うかもしれないけど「読めるよ!」

#include <stdio.h>
int main() {
   // 型を偽って参照するのは間違いの元なので型のチェックは厳格。
   //   だから 以下の様なヤバイことをする時は、型キャスト で
   //   だますことが定番。
   int x = 0x41424344 ; 
   char* p = (char*)( &x ) ; // int型の場所をchar型にする 
   printf( "%c\n" , *p ) ;

   // int型は4バイト、次のアドレスは?
   int y[] = {
      0x11223344 , 0x12345678 ,
   } ;
   printf( "%p %p\n" , y , y + 1 ) ; 
   int *r = y + 1 ;
   printf( "%04d\n" , *r ) ; // 12345678 が表示

   // intの1byteとなりをintとして読める?
   int *q = (int*)((char*)( &y ) + 1) ;
   printf( "%04x\n" , *q ) ; // 処理系によってはメモリエラー

   // ポインタは番地を表す数値だよね?
   //  0x100番地のデータは読める?
   int* s = (int*)0x100 ;
   printf( "%d\n" , *s ) ; // Segmentation Fault.

   return 0 ;
}

さて、上記のプログラムをみてどう思った?

C言語って自由奔放で、やばくね? — ポインタなんか使えるからだよね、そう思うんなら Java 使え。ポインタなんか使えないから。

でも型宣言が面倒なんだよねPython, Ruby などの動的型付けな言語使え。

でも変数参照でいちいち型情報しらべる言語って遅くね? — あるよ。「型推論」。型を明記しなくても、プログラムの文脈から型を推論してくれる静的型付け言語。Go , Swift , Kotlin…といった、今 流行りのプログラム言語がソレ。最新のJavaやC++も型推論機能が使えるようになってるよ。んで、今話題の中学生が作ったプログラム言語 Blawn も、型推論の言語!すげーな。

演算子と2分木による式の表現

2分木の応用として、式の表現を行うけどその前に…

逆ポーランド記法

一般的に 1*2 + 3*4 と記載すると、数学的には演算子の優先順位を考慮して、(1*2)+(3*4) のように乗算を先に行う。このような優先順位を表現する時に、()を使わない方法として、逆ポーランド記法がある。

演算子の書き方には、前置記法、中置記法、後置記法があり、後置記法は、「2と3を掛ける、それに1を加える」と捉えると、日本語の処理と似ている。

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+

後置記法は、一般的に逆ポーランド記法(Reverse Polish Notation)とも呼ばれ、式を機械語の命令に置き換える際に役立つ。

理解度確認

以下の式を指定された書き方で表現せよ。

逆ポーランド記法 1,2,*,3,4,*,+ を中置記法で表現せよ。
中置記法 (1+2)*3-4*5 を逆ポーランド記法で表現せよ。

以前の情報処理技術者試験では、スタックの概念の理解の例題として、逆ポーランド記法への変換アルゴリズムのプログラム作成が出題されることが多かったが、最近は出題されることはなくなってきた。

逆ポーランド式の実行

この逆ポーランド記法で書かれた式から結果を求めるプログラムは以下のように記述できる。このプログラムでは式を簡単にするため、数値は1桁の数字のみとする。

// 単純な配列を用いたスタック
int stack[ 10 ] ;
int sp = 0 ;

void push( int x ) {
   stack[ sp++ ] = x ;
}
int pop() {
   return stack[ --sp ] ;
}

// 逆ポーランド記法の計算
int rpn( char* p ) {
   for( ; *p != '\0' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
      } else if ( *p == '+' ) {
         // 演算子+は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 加算結果をスタックに積む
         push( l + r ) ;
      } else if ( *p == '*' ) {
         // 演算子*は上部2つを取出し
         int r = pop() ;
         int l = pop() ;
         // 乗算結果をスタックに積む
         push( l * r ) ;
      }//~~~~~~~~~~~~~(B)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}

逆ポーランド記法の式の実行は、上記のようにスタックを用いると簡単にできる。このようなスタックと簡単な命令で複雑な処理を行う方法はスタックマシンと呼ばれる。Java のバイトコードインタプリタもこのようなスタックマシンである。

Cプログラママニア向けの考察

上記のプログラムでは、int r=pop();…push(l+r); で記載しているが、

push( pop() + pop() ) ;

とは移植性を考慮して書かなかった。理由を述べよ。

最初の関数電卓

初期の関数電卓では複雑な数式を計算する際に、演算子の優先順位を扱うのが困難であった。このため、HP社の関数電卓では、式の入力が RPN を用いていた。(HP-10Cシリーズ)

2項演算と構文木

演算子を含む式が与えられたとして、それを保存する場合、演算式の2分木で扱うと都合が良い。

   +
  / \
 1   *
    / \
   2   3

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝がNULLなら数値(data部にはその数値)、それ以外は演算子(data部には演算子の文字コード)として扱うとして…

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 ) {     // ~~~~~~~~~~~~~~~~~~~~~(C)
      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 ) ;
      }              // ~~~~~~~~~~~~~~~(D)      ~~~~~~~~(E)
   }
}

void main() {
   struct Tree* exp =  // 1+(2*3) の構文木を生成
      tree_op( '+' ,
               tree_int( 1 ) ,
               tree_op( '*' ,
                        tree_int( 2 ) , tree_int( 3 ) ) ) ;
   printf( "%d¥n" , eval( exp ) ) ;
}

理解度確認

  • 上記プログラム中の(A),(B),(C),(D)の型を答えよ。

const char*s, char* const sの違い

専攻科実験のサンプルコードで、警告がでたことについて質問があったので説明。

(( サンプルコード sample.cxx ))
#include <stdio.h>
void foo( char* s ) {
  printf( "%s¥n" , s ) ;
}
int main() {
  foo( "ABC" ) ;
  return 0 ;
}

(( コンパイル時の警告 ))
$ g++ sample.cxx
test.cxx:6:6: warning: conversion from string literal
      to 'char *' is deprecated
      [-Wc++11-compat-deprecated-writable-strings]
  foo( "abcde" ) ;
       ^
1 warning generated.

警告を抑止する “-Wno-…” のオプションをつけて “g++ -Wno-c++11-compat-deprecated-writable-strings sample.cxx” でコンパイルすることもできるけど、ここは変数の型を厳格にするのが鉄則。

この例では、引数の “ABC” が書き換えのできない定数なので、const キーワードを付ければよい。ただし、宣言時の const の付け場所によって、意味が違うので注意が必要。

void foo( char const* s ) { // const char* s も同じ意味
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // OK ポインタを動かすことはできる
}
void foo( char *const s ) {
   *s = 'A' ; // OK ポインタの先は書き込める
   s++ ;      // NG ポインタは動かせない
}
void foo( char const*const s ) {
   *s = 'A' ; // NG ポインタの先を書き換えできない
   s++ ;      // NG ポインタは動かせない
}

const を書く場所は?

int const x = 123 , y = 234 ; の場合、yは定数だろうか?

(( おまけ ))
#include <stdio.h>
int main() {
  int const x = 123 , y = 234 ; // x は定数だけど yは定数?
  x++ ; // 予想通りエラー
  y++ ; // yも定数なのでエラー
  int const s = 345 , const t = 456 ; // sもtも明らかに定数っぽい
  //                  ^ここで文法エラー

  // おまけのおまけ
  char* s , t ;   // s は文字へのポインタ、t は文字
  char  *s , *t ; // s は文字へのポインタ、t も文字へのポインタ
  return 0 ;
}
Secured By miniOrange