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

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

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

このプログラムの書き方では、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() ;
}

演習(ハッシュ法)

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

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

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

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

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

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( c ) ;
   list_del( b ) ;
   list_del( a ) ; // list_del(c)ですでに消えている
}                  // このためメモリー参照エラー発生

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

参照カウンタ法

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

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

• データの中にポインタ数を覚える参照カウンタを設け、データを生成した時に１とする。
• 処理の中で共有が発生すると、参照カウンタをカウントアップする。
• データを捨てる際には、参照カウンタをカウントダウンし、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. すべてのメモリ空間に、「不要」の目印をつける。(mark処理)
2. 変数に代入されているデータが参照している先のデータは「使用中」の目印をつける。(mark処理)
3. その後、「不要」の目印がついている領域は、だれも使っていないので回収する。(sweep処理)

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

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

ハッシュ法

ここまでの授業では、配列(データ検索は、登録順保存ならO(N)、２分探索なら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 , 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 ; // 見つからなかった
}

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