ホーム » 2021 » 1月 » 27

日別アーカイブ: 2021年1月27日

2021年1月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最新の投稿(電子情報)

アーカイブ

カテゴリー

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

データ構造を扱うプログラムの書き方を説明してきたが、その考え方をプログラムにするためには手間もかかる。こういった手間を少しでも減らすために、プログラム言語が支援してくれる。その代表格がオブジェクト指向プログラミング(Object Oriented Programming:略称OOP)であり、以下にその基本を説明する。

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

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

このプログラムの書き方では、saitohというデータにset_NameAge() , print_NameAge() を呼び出していて、データに対して処理を加えるという雰囲気がでている。(C言語なのでデータに処理を施す関数には、必ずどのデータに対する処理なのかを与えるポインタがある。) このようにプログラムを書くと、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 ) ; // set,printはpublicなので自由に使える。
   saitoh.print() ;
   // saitoh.age = 54 ; エラー:クラス外でprivateの要素は触れない。
}

このプログラムでは、saitoh というデータ(具体的なデータが割り当てられたものはオブジェクトと呼ぶ)に対して、set() , print() のメソッドを呼び出している。

# C++ではクラス毎に関数名を区別してくれるので、関数名もシンプルにset,printのようにかける。

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

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

// コンストラクタを使う例
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++なら...
  // * もともとのC言語なら以下のように書くだろう。
  //   for( struct List*p = top ; p != NULL ; p = p->next )
  //     printf( "%d¥n" , p->data ) ;

  // * 通常の反復子iteratorを使って書いてみる。
  //   auto は、lst の型推論。
  //   ちょっと前のC++なら型推論がないので、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 ;
}

テンプレート機能

テンプレート機能は、実際のデータを覚える部分の型を後で指定できるようにしたデータ構造を定義する機能。

template <class >
struct List {
   T   data ;
   struct List* next ;
} ;

int main() {
   List<int>    li ;  // 整数を要素とするList型の宣言
   List<double> ld ;  // 実数を要素とするList型の宣言
}

関数ポインタ

前プログラムのC++のfor_each アルゴリズムでは、コールバック関数が使われていたが、この仕組みを分かるために関数ポインタの考え方が重要。

int add( int x , int y ) {
   return x + y ;
}
int mul( int x , int y ) {
   return x * y ;
}
void main() {
   int (*f)( int , int ) ; // fは2つのintを引数とする関数へのポインタ
   f = add ;               // f = add( ... ) ; ではないことに注意
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3+4=7
   f = mul ;
   printf( "%d¥n" , (*f)( 3 , 4 ) ) ; // 3*4=12
}

演習(ハッシュ法)

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

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

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

B木とB+木とハッシュ法

データベースでは、キーなどの値を高速に探し出すために、単純なデータが並んだだけのテーブルとは別に、検索専用のデータ構造を別に持たせることが多い。これらの検索用のデータは、インデックスファイルと呼ばれる。

以下に、データベースの各レコードを高速に参照するための仕組みについて説明する。

B木

データベースのデータを扱う場合には、B木を用いることが多い。

複数のデータを格納するノードは、位数Nであれば、2✕N個のデータと、その間のデータを持つノードへの2N+1個のポインタで構成される。

ノードにデータを加える場合(あるいは削除する場合)は、頻繁にノードのポインタの付け替えが発生しないように、データがN個を下回った時や、2N個を超える場合に以下のような処理を行う。ノード内のデータ数が2Nを超える場合は、均等に木構造が成長するように、中央値を上のノードに移動し、ノードを2分割する。

データを削除することでN個を下回る場合は、隣接するノードからデータを移動する。(上図の緑部分のように上位ノードの値を交えながら移動する)

このような処理を行うことで、極力不均一に成長した木構造が発生しないようにB木は管理されている。

B+木とシーケンスセット

再帰的な木構造のB木では、特定のデータを探す場合には、O(log N)で検索が可能である。

しかしながら、直積のようなすべてのデータを対象とする処理を行う場合、単純なB木では再帰呼出しをしながらの処理を必要とすることから、複雑な処理が発生する。そこで、データ列を横方向にアクセスするための単純リストであるシーケンスセットをB木と並行して管理するデータ構造B+木である。

データを検索する場合は、B木構造部を用い、全データ処理は、シーケンスセットを用いる。

ハッシュ法

ハッシュ表は、データの一部をとりだしてハッシュ値を求め、そのハッシュ値を番地とする場所にデータを保存する方法である。しかし、データの一部を取り出すため、異なるデータに対して同じハッシュ値となる場合がある。これをハッシュ衝突とよぶ。この際のデータの保存の方法から、2つの方式がある。

  1. オープンアドレス法
    ハッシュ表がすでに埋まっていたら、別の保存場所を探す方式。
  2. チェイン法
    同じハッシュ値となるデータをリスト構造で保存する方法。