2分木の応用として式の表現の説明を行うけど、その前に計算式の一般論の説明を行う。

逆ポーランド記法

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

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

中置記法 1+2*3
前置記法 +,1,*,2,3
後置記法 1,2,3,*,+　　# 1と「2と3をかけた値」をたす。

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

演算子の右結合・左結合

例えば、”1/2*3″という式が与えられたとする。この結果は、1/6だろうか？3/2だろうか？

一般的な数学では、優先順位が同じ演算子が並んだ場合、左側から計算を行う。つまり”1/2*3″は、”(1/2)*3″を意味する。こういった左側の優先順位が高い演算子は左結合の演算子という。

ただしC言語では、”a = b = c = 0″ と書くと、”a = (b = (c = 0))” として扱われる。こういった代入演算子は、 右結合の演算子である。

理解度確認

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

逆ポーランド記法 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 != '
// 単純な配列を用いたスタック
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' ) ;
         //    ~~~~~~~~(B)
      } 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 ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

void main() {
   printf( "%d\n" , rpn( "123*+" ) ) ;
}
' ; p++ ) {
      if ( isdigit( *p ) ) {
         //         ~~(A)
         // 数字はスタックに積む
         push( *p - '0' ) ;
         //    ~~~~~~~~(B)
      } 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 ) ;
      }//~~~~~~~~~~~~~(C)
   }
   // 最終結果がスタックに残る
   return pop() ;
}

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

• eval-rpn.cxx

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

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

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

push( pop() + pop() ) ;

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

最初の関数電卓

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

2項演算と構文木

演算子を含む式が与えられたとして、古いコンパイラではそれを逆ポーランド変換して計算命令を生成していた。しかし最近の複雑な言語では、計算式や命令を処理する場合、その式(または文)の構造を表す2分木(構文木)を生成する。。

　　　＋
　　／　＼
　１　　　＊
　　　　／　＼
　　　２　　　３

演算子の木のノードで、末端は数値であることに注目し、右枝・左枝が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 ) {     // ~~~~~~~~~~~~~~~~~~~~~(D)
      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 ) ;
      }              // ~~~~~~~~~~~~~~~(E)      ~~~~~~~~(F)
   }
}

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 ) ) ;
}

• eval-tree.cxx

理解度確認

• push(),pop() のスタックは、保存と取り出しの順序を表す単語の頭文字4つを使って何と呼ばれるか？
• 上記プログラム中の(A)～(F)の型を答えよ。

前回までの授業で2分探索木の説明をしてきたが、このデータ構造は他のデータを扱う際にも用いられる。ここで、意思決定木と構文木を紹介する。

意思決定木

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

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

このような判断を行うための情報は、yesの木 と noの木の2つの枝を持つデータである。これは2分木と同じであり、このような処理は以下のように記述ができる。

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 ) ;
      scanf( "%d" , &ans ) ;
      // 回答に応じてyes/noの枝に進む。
      if ( ans == 1 )      // yesを選択
         d = d->yes ;
      else if ( ans == 0 ) // noを選択
         d = d->no ;
   }
   // 最終決定を表示
   printf( "%s¥n" , d->qa ) ;
}

• decision-tree.cxx

コンパイラと言語処理系

2分木の応用の構文木について、この後説明を行うが、構文木を使うコンパイラなどの一般知識を事前に説明しておく。

高級言語で書かれたプログラムを計算機で実行するソフトウェアは、言語処理系と呼ばれる。その実行形式により

• インタプリタ(interpreter:翻訳)
  • ソースプログラムの意味を解析しながら、その意味に沿った処理を行う
• コンパイラ(compiler:通訳)
  • ソースプログラムから機械語を生成し、実行する際には機械語を実行
• トランスコンパイラ
  • ソースから他の言語のソースコードを生成し、それをさらにコンパイルし実行
    最初のC++の実装では、C++をトランスレータにかけてC言語を生成し、C言語のコンパイラで動かしていた。
• バイトコードインタプリタ
  • ソースからバイトコード(機械語に近いコードを生成)、実行時にはバイトコードの命令に沿った処理を行う
• エミュレーター
  • 異なるCPUのコンピュータで、システムの動作や機能を模倣して動かすシステム。
    近々の例であれば、AppleのARMベースM1チップで intel CPU の動きを真似て動作させる Rosetta2 がトピック。パソコンで古いファミコンのソフトを動かすといった技術もエミュレータ。
    • 同じCPUで異なるOSを動かす場合は、CPU仮想化。

に分けられる。

コンパイラが命令を処理する際には、以下の処理が行われる。

1. 字句解析(lexical analysys)
   文字列を言語要素(token)に分解
2. 構文解析(syntax analysys)
   tokenの並び順に意味を反映した構造を生成
3. 意味解析(semantics analysys)
   命令に合わせた中間コードを生成
4. 最適化(code optimization)
   中間コードを変形して効率よいプログラムに変換
5. コード生成(code generation)
   実際の命令コードとして出力

バイトコードインタプリタとは

例年だと説明していなかったけど最近利用されるプログラム言語の特徴を説明。

通常、コンパイラとかインタプリタの説明をすると、Java がコンパイラとか、JavaScript はインタプリタといった説明となる。しかし、最近のこういった言語がどのように処理されるのかは、微妙である。

(( Java の場合 ))
foo.java (ソースコード)
　↓       Java コンパイラ
foo.class (中間コード)
　↓
JRE(Java Runtime Engine)の上で
中間コードをインタプリタ方式で実行

あらかじめコンパイルされた中間コードを、JREの上でインタプリタ的に実行するものは、バイトコードインタプリタ方式と呼ぶ。

ただし、JRE でのインタプリタ実行では遅いため、最近では JIT コンパイラ(Just-In-Time Compiler)により、中間コードを機械語に変換してから実行する。

また、JavaScriptなどは(というか最近のインタプリタの殆どPython,PHP,Perl,…は)、一般的にはインタプリタに分類されるが、実行開始時に高級言語でかかれたコードから中間コードを生成し、そのバイトコードをインタプリタ的に動かしている。

しかし、インタプリタは、ソースコードがユーザの所に配布されて実行するので、プログラムの内容が見られてしまう。プログラムの考え方が盗まれてしまう。このため、変数名を短くしたり、空白を除去したり(…部分的に暗号化したり)といった難読化を行うのが一般的である。

トークンと正規表現(字句解析)

規定されたパターンの文字列を表現する方法として、正規表現(regular expression)が用いられる。

((正規表現の書き方))
選言　　　  「abd|acd」は、abd または acd にマッチする。
グループ化　「a(b|c)d」は、真ん中の c|b をグループ化
量化　　　　パターンの後ろに、繰り返し何回を指定
　　　　　　? 直前パターンが0個か1個
　　　　　　　「colou?r」
　　　　　　* 直前パターンが0個以上繰り返す
　　　　　　　「go*gle」は、ggle,gogle,google
　　　　　　+ 直前パターンが1個以上繰り返す
　　　　　　　「go+gle」は、gogle,google,gooogle

正規表現は、sed,awk,Perl,PHPといった文字列処理の得意なプログラム言語でも利用できる。こういった言語では、以下のようなパターンを記述できる。

[文字1-文字2...] 文字コード1以上、文字コード2以下
　　　　　　「[0-9]+」012,31415,...数字の列
^　　　　　行頭にマッチ
$　　　　　行末にマッチ
((例))
[a-zA-Z_][a-zA-Z_0-9]* C言語の変数名にマッチする正規表現

• 情報処理技術者試験で出題された正規表現の問題と解説

構文とバッカス記法

言語の文法を表現する時、バッカス記法(BNF)が良く使われる。

((バッカス記法))
<表現> ::= <表現1...> | <表現2...> | <表現3...> | ... ;

例えば、加減乗除記号と数字だけの式の場合、以下の様なBNFとなる。

((加減乗除式のバッカス記法))
<加算式> ::= <乗算式> '+' <乗算式>
          | <乗算式> '-' <乗算式>
          | <乗算式>
          ;
<乗算式> ::= <数字> '*' <乗算式>
          | <数字> '/' <乗算式>
          | <数字>
          ;
<数字>   ::= [0-9]+
          ;

上記のバッカス記法には、間違いがある。”1+2+3″を正しく認識できない。どこが間違っているだろうか?

このような構文が与えられた時、”1+23*456″と入力されたものを、“1,+,23,*,456”と区切る処理が、字句解析である。

また、バッカス記法での文法に合わせ、以下のような構文木を生成するのが構文解析である。

　　＋
　／　＼
１　　　＊
　　　／　＼
　　23　　　456

理解度確認

• インタプリタ方式で、処理速度が遅い以外の欠点をあげよ。
• 情報処理技術者試験の正規表現,BNF記法問題にて理解度を確認せよ。

配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)

// 2分探索法
int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ;

int bin_search( int a[] , int key , int L , int R ) {
   // Lは、範囲の左端
   // Rは、範囲の右端+1 (注意!!)
   while( R > L ) {
      int m = (L + R) / 2 ;
      if ( a[m] == key )
         return key ;
      else if ( a[m] > key )
         R = m ;
      else
         L = m + 1 ;
   }
   return -1 ; // 見つからなかった
}

void main() {
   printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ;
}

一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか？

2分探索木

ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。

この枝の特徴は何だろうか？この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。

特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。

このデータ構造をプログラムで書いてみよう。

struct Tree {
   struct Tree* left ;
   int          data ;
   struct Tree* right ;
} ;

// 2分木を作る補助関数
struct Tree* tcons( struct Tree* L ,
                    int          d ,
                    struct Tree* R ) {
   struct Tree* n = (struct Tree*)malloc(
                       sizeof( struct Tree ) ) ;
   if ( n != NULL ) { /* (A) */
      n->left = L ;
      n->data = d ;
      n->right = R ;
   }
   return n ;
}

// 2分探索木よりデータを探す
int tree_search( struct List* p , int key ) {
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ; // 見つからなかった
}
struct Tree* top = NULL ;

void main() {
   // 木構造をtcons()を使って直接生成 (B)
   top = tcons( tcons( tcons( NULL , 13 , NULL ) ,
                       27 ,
                       tcons( NULL , 38 , NULL ) ) ,
                42 ,
                tcons( tcons( NULL , 64 , NULL ) ,
                       72 ,
                       tcons( NULL , 81 , NULL ) ) ) ;
   printf( "%d¥n" , tree_search( top , 64 ) ) ;
}

この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。

理解度確認

• 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
• 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。

2分木に対する処理

2分探索木に対する簡単な処理を記述してみよう。

// データを探す
int search( struct Tree* p , int key ) {
   // 見つかったらその値、見つからないと-1
   while( p != NULL ) {
      if ( p->data == key )
         return key ;
      else if ( p->data > key )
         p = p->left ;
      else
         p = p->right ;
   }
   return -1 ;
}
// データを全表示
void print( struct Tree* p ) {
   if ( p != NULL ) {
      print( p->left ) ;
      printf( "%d¥n" , p->data ) ;
      print( p->right ) ;
   }
}
// データ件数を求める
int count( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return 1
             + count( p->left )
             + count( p->right ) ;
}
// データの合計を求める
int sum( struct Tree* p ) {
   if ( p == NULL )
      return 0 ;
   else
      return p->data
             + count( p->left )
             + count( p->right ) ;
}
// データの最大値
int max( struct Tree* p ) {
   while( p->right != NULL )
      p = p->right ;
   return p->data ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

リストを用いた待ち行列の補足

# リストによる待ち行列を早速に創造工学演習で応用した人からの質問より…

以前に説明したリストを用いた待ち行列(queue)において、時間的都合から詳しく説明できなかった点の注意点を説明する。

待ち行列の説明では、get() の処理を以下のように示していた。しかし、このままでは、待ち行列が1件の状態で、以下のような get() を実行するとポインタが以下のような図に示される状態となり、tail ポインタがおかしい状態となる。

struct List* queue = NULL ;
struct List** tail = &queue ;
// 待ち行列の先頭から取り出す。
int get() {
   struct List* d = queue ;
   int ans = d->data ;
   queue = queue->next ;
   free( d ) ;
}

このため、待ち行列内のデータ件数が 0 件になる時だけ、tail ポインタが正しくなるような特別処理を加える必要がある。こういった特別処理は、以後の授業で説明する双方向リスト(deque:double-ended queue)などでは、プログラムを複雑化させてしまうので、別途「番兵」というテクニックが使われる。

リスト処理による積集合

前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)

しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。また、今までの授業で説明してきた cons() などを使って表現すれば、簡単なプログラムでリストの処理が記述できる。

// 先週までに説明してきたリスト構造と補助関数
struct List {
   int     data ;
   struct List* next ;
} ;
// リストの入れ物を１つ作る
struct List* cons( int x , struct List* n ) {
   struct List* ans ;
   ans = (struct List*)malloc( sizeof( struct List ) ) ;
   if ( ans != NULL ) {
      ans->data = x ;
      ans->next = n ;
   }
   return ans ;
}
// リストを表示
void print( struct List* p ) {
   for( ; p != NULL ; p = p->next ) {
      printf( "%d " , p->data ) ;
   }
   printf( "\n" ) ;
}
// リストの中に指定要素があるか判定(有れば1,無ければ0)
int find( struct List* p , int key ) {
   for( ; p != NULL ; p = p->next )
      if ( p->data == key )
         return 1 ;
   return 0 ;
}

例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 両方に含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。

// 集合積の計算
struct List* set_prod( struct List* a , struct List* b ) {
   struct List* ans = NULL ;
   for( ; a != NULL ; a = a->next ) {
      // aの要素がbにも含まれていたら、ansに加える
      if ( find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   }
   return ans ;
}
void main() {
   struct List* a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
   struct List* b = cons( 2, cons( 4, cons( 6, NULL ) ) ) ;
   struct List* c = cons( 4, cons( 6, cons( 9, NULL ) ) ) ;
   print( set_prod( a , b ) ) ;
   print( set_prod( b , c ) ) ;
}

例題として、和集合、差集合などを考えてみよう。

リストの共有と削除の問題

リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。リストの全要素を捨てる処理であれば、以下のようになるであろう。

void list_free( struct List* p ) {
   while( p != NULL ) {
      struct List* d = p ;
      p = p->next ;
      free( d ) ; // 順序に注意
   }
}

一方、前説明の和集合(a ∪ b)のプログラムを以下のように作った場合、list_freeの処理は問題となる。

// 集合和
struct List* set_union( struct List*a, struct List*b ) {
   struct List* ans = b ;
   for( ; a != NULL ; a = a->next )
      if ( !find( b , a->data ) )
         ans = cons( a->data , ans ) ;
   return ans ;
}
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 = set_union( a , b ) ;
   // a,b,cを使った処理
   // 処理が終わったので、a,b,cを捨てる
   list_free( a ) ;
   list_free( b ) ;
   list_free( c ) ;
   // c = { 1 , (bのリスト) }
   // (b)の部分は先のlist_free(b)で解放済み
}

このような、リストb,リストcで共有されている部分があると、データの廃棄処理をどのように記述すべきなのか、問題となる。

これらの解決方法としては、(1) set_union() の最初で、ans=b となっている部分を別にコピーしておく、(2) 参照カウンタ法を用いる、(3) ガベージコレクタのある言語を用いる…などがある。(2),(3)は後期授業で改めて解説を行う。

// 同じ要素を含む、新しいリストを作る
struct List* copy( struct List*p ) {
   struct List*ans = NULL ;
   for( ; p != NULL ; p = p->next )
      ans = cons( p->data , ans ) ;
   return ans ;
}
struct List* set_union( struct List*a, struct List* b ) {
   struct List* ans = copy( b ) ;
   // この後は自分で考えよう。
}

理解確認

• 2進数を用いた集合処理は、どのように行うか？
• リスト構造を用いた集合処理は、どのように行うか？
• 積集合(A ∩ B)、和集合(A ∪ B)、差集合(A – B) の処理を記述せよ。

リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。

bit演算子

2進数を使った処理をする時には、bit演算子を用いる。

bit AND	3 & 5 0011)2 & 0101)2= 0001)2	論理積演算子 if ( a == 1 && b == 2 ) …
bit OR	3 | 5 0011)2 | 0101)2= 0111)2	論理和演算子 if ( a == 1 || b == 2 ) …
bit NOT	~5 ~ 00..00,0101)2= 11..11,1010)2	論理否定演算子 if ( !a == 1 ) …
bit EXOR	3 ^ 5 0011)2 ^ 0101)2= 0110)2
bit 左シフト	3 << 2 0011)2 << 2 = 001100)2	3 * 22 と同じ
bit 右シフト	12 >> 2 1100)2 >> 2 = 11)2	12 / 22 と同じ

#include <stdio.h>

int main() {
   // bit演算子と論理演算子
   printf( "%d¥n" , 12 &  5 ) ;  // 1100 & 0101 = 0100 よって 4が表示される
   printf( "%d¥n" , 12 && 0 ) ;  // 0が表示　論理演算子とbit演算子の違い
   printf( "%d¥n" , 12 |  5 ) ;  // 1100 | 0101 = 1101 よって 13が表示される
   printf( "%d¥n" , 12 || 0 ) ;  // 1が表示 
   // シフト演算子
   printf( "%d¥n" ,  3 << 2 ) ;  // 12が表示
   printf( "%d¥n" , 12 >> 2 ) ;  // 3が表示
   // おまけ
   printf( "%d¥n" , ~(unsigned)12 + 1 ) ;  // 2の補数(NOT 12 + 1) = -12
   return 0 ;
}

2進数を用いた集合計算

リストによる集合の前に、もっと簡単な集合処理を考える。

最も簡単な方法は、要素に含まれる=1 か 含まれない=0 を配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に1を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、演習課題として穴埋めを含むので注意。

• set-array.cxx

しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報を、整数型で保存しているためメモリの無駄である。

データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。

以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc , ba ∪ bc の計算を行う例である。

// 符号なし整数を uint_t とする。
typedef unsigned int uint_t ;

// uint_tのbit数
#define UINT_BITS (sizeof( uint_t ) * 8)

// 集合の内容を表示
void bit_print( uint_t x ) {
   for( int i = 0 ; i < UINT_BITS ; i++ )
      if ( (x & (1 << i)) != 0 )
         printf( "%d " , i ) ;
   printf( "\n" ) ;
}
void main() {     // 98,7654,3210
   // ba = {1,2,3} = 00,0000,1110
   uint_t ba = (1<<1) | (1<<2) | (1<<3) ;
   // bb = {2,4,6} = 00,0101,0100
   uint_t bb = (1<<2) | (1<<4) | (1<<6) ;
   // bc = {4,6,9} = 10,0101,0000
   uint_t bc = (1<<4) | (1<<6) | (1<<9) ;

   bit_print( ba & bb ) ; // ba ∩ bb = {2}                 
   bit_print( bb & bc ) ; // bb ∩ bc = {4,6}
   bit_print( ba | bc ) ; // ba ∪ bc = {1,2,3,4,6,9}
}

このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数探索がある。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。

uint_t prime = 0 ; // 初期値=すべての数は素数とする。

void filter() {
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      if ( (prime & (1 << i)) == 0 ) {
         // iの倍数には、非素数の目印(1)をつける
         for( int j = 2*i ; j < UINT_BITS ; j += i )
            prime |= (1 << j) ;
      }
   }
   for( int i = 2 ; i < UINT_BITS ; i++ ) {
      // 目印のついていない数は素数
      if ( (prime & (1 << i)) == 0 )
         printf( "%d\n" , i ) ;
   }
}

ミニ課題

最初に示した、配列による集合の set-array.cxx で、配列による和集合、エラトステネスのふるいの処理の一部を記述していない。未完成の部分を埋めて、動作を確認せよ。