前年度のプログラミング応用の次のステップとしての情報構造論として、 どういった内容を行うのかガイダンスを行う。

最初に、使用する教科書のタイトルにもある、アルゴリズムという言葉の説明として、 アルゴリズムとは、計算の方法の考え方、 そのアルゴリズムをどう表現するのかがパラダイム、 そのパラダイムに沿って実際に書いたものがプログラム。

いいプログラムとは？

次に、ある程度プログラム記述を学んできたところだし「あなたはどうプログラムを書くといいと思うか？」 を次々と聞いてみた。 学生さんから帰ってくる言葉は、 「わかりやすい、行数が短い、関数が使われている、変数名が解りやすい、バグが少ない…」 といった物がほとんど。 中には、「プログラムが再利用しやすい」といったオツな答えもあったけど、 どれも大きくまとめれば「わかりやすい」という観点。

途中で、「処理速度が速い」という答えもあったけど、「メモリの使用量が少ない」という 観点がなかなか出てこない。

処理速度という観点では、3秒ルールなどの雑談を交えながら計算時間について説明。 また、メモリの使用量という観点では、限られた主記憶を有効に使わないと、 プログラムが動かなかったり、仮想記憶などを使うことになり、頻繁なスワップ処理で 処理速度の低下につながることを説明する。

これらの「プログラムの分かりやすさ」、「処理速度」、「メモリの使用量」は、一般的に、 どれかを優先すれば、ほかの観点が悪化してしまうトレードオフの関係にあることを説明。

処理時間を式で表現

まず、プログラムの処理時間を分析するために、簡単なプログラムがどんな式で表現できるかを示す。

// 配列(順序はデタラメ)の中の特定データを探す処理。
int data[ N ] ;
   for( i = 0 ; i < N ; i++ ) {
      if ( data[ i ] == key )
         break ;
}

このようなループ処理であれば、ループ回数の平均を考えて式にすると、

で表現できることを説明。

// 最大選択法の並び替え
int data[ N ] ;

for( i = 0 ; i < N-1 ; i++ ) {
   int m = i ;
   for( j = i+1 ; j < N ; j++ ) {
      if ( data[m] > data[j] )
         m = j ;
   }
   tmp = data[ m ] ;
   data[ m ] = data[ i ] ;
   data[ i ] = tmp ;
}

このような処理であれば、ループ回数をΣなどを用いて表しながら、以下のような式で示されることを説明。

授業進度が予定よりも早いため前半講義で、後半はまだ提出者の少ないことから 課題の時間とした。

前回のハッシュ法では、数値(電話番号)をキーとする検索であった。 このためハッシュ関数は、数値の不規則性の部分を取り出すだけでよかった。 それでは、文字をキーとしてデータを探す場合はどのようにすればよいか？

文字の場合は、文字コードを用いてハッシュ値を作れば良い。

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

しかし、この方法では、文字の並び順が違うだけ(“ABC”,”CBA”,”BBB”)に対して、 同じハッシュ値となってしまう。 英文字の場合は文字数も限られ、文字コード的には末尾4bitが変化するだけであり、 上位ビットは文字数に左右されることになる。 この場合、同じような文字数であれば、末尾4bitの不規則性も平均化されて、 近いハッシュ値になることが懸念される。

そこで、文字コード的に変化のある部分が、数値的に全体に影響を及ぼし、 最終的な値が広く分布するように以下のような計算とする場合が多い。

// 積算部のみ
sum = ( sum * (小さめの素数) + s[i] ) % (大きめの素数) ;

このような考え方は、疑似乱数を生成する方式と近い部分が多い。

2分木なども終わって、検索処理のさらなる高速化として、 ハッシュ法を説明する。

オープンアドレス法

電話番号が記録されているのかどうかを探す処理を考えると、 最も単純な方法は、電話番号を配列の添字にする方法となる。

int array[ 1000000 ] ; // 局番2桁+4桁
void entry( int phone ) {
   array[ phone ] = phone ;
}
int search( int phone ) {
   if ( array[ phone ] == 0 )
      return 0 ;
   else
      return 1 ;
}

しかしこの方法では、0778621111 といった番号も考えると、 巨大なメモリを必要として、非現実的となる。 この際の解決法がハッシュ法で、データ件数が少なければ、 例えば電話番号の末尾2桁がおなじデータの発生する確率は低い。 もし、電話番号末尾2桁が同じでも、その番号の次の場所に保存するなどすればよい。

#define SIZE 100     // ハッシュ表のサイズ
int hash[ SIZE ] ;   // ハッシュ表
int hash_func( int phone ) { // ハッシュ関数
   return phone % SIZE ;
}
void entry( int phone ) {
int idx = hash_func( phone ) ;
   while( hash[ idx ] != 0 )   // データ件数100で無限ループだけど...
      idx = (idx + 1) % SIZE ;
   hash[ idx ] = phone ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   while( hash[ idx ] != 0 ) {
      if ( hash[ idx ] == phone )
         return 1 ;
      idx = (idx + 1) % SIZE ;
   }
   return 0 ;
}

チェイン法

オープンアドレス法では、次の空き場所を探して保存するが、 表サイズよりもデータ件数を多く保存することはできない。

表が埋まって、同じハッシュ値のデータがでてきたら、同じハッシュ値同士を リスト構造で保存する方法はチェイン法と呼ばれる。

struct List *hash[ SIZE ] ; // ポインタはNULLで全て初期化
void entry( int phone ) {
   int idx = hash_func( phone ) ;
   hash[ idx ] = cons( phone , hash[ idx ] ) ;
}
int search( int phone ) {
   int idx = hash_func( phone ) ;
   struct List* p ;
   for( p = hash[ idx ] ;
        p != NULL ;
        p = p->next )
   {
      if ( p->data == phone )
         return 1 ;
   }
   return 0 ;
}