構造体と実体の違いや、Javaに慣れている学生さんに あらためて、データ構造のイメージを持って欲しいので、 以下のコードを示す。

struct Complex {
   double re ;
   double im ;
} ;
struct Complex2 {
   double* pre ;
   double* pim ;
} ;
void main() {
   // メモリ確保失敗のNULLチェックは省略
   struct Complex a ;
   struct Complex* p ;
   struct Complex2 b ;
   struct Complex2* q ;

   a.re = 1.2 ;
   a.im = 2.3 ;

   p = (struct Complex*)malloc( sizeof( struct Complex ) ) ;
   p->re = 1.2 ;
   p->im = 2.3 ;
   // in Java
   // p = new Complex ;
   // p.re = 1.2 ;
   // p.im = 2.3 ;

   b.pre = (double*)malloc( sizeof( double ) ) ;
   *(b.pre) = 1.2 ;
   b.pim = (double*)malloc( sizeof( double ) ) ;
   *(b.pim) = 2.3 ;

   q = (struct Comple2*)malloc( sizeof( struct Complex2 ) ) ;
   q->pre = (double*)malloc( sizeof( double ) ) ;
   *(q->pre) = 1.2 ;
   q->pim = (double*)malloc( sizeof( double ) ) ;
   *(q->pim) = 2.3 ;
}

上記プログラムのメモリの格納イメージ図を以下に示す。

先週に2分木に対する再帰などを交えたプログラムの説明をしたので、 今週は木の生成について、AVL木などを交えて説明。 後半は、情報処理センターで演習。

#include <stdio.h>
#include <stdlib.h>
// 2分木の宣言
struct Tree {
   int data ;
   struct Tree* left ;
   struct Tree* right ;
} ;
// 木の根
struct Tree* top = NULL ;
// 木のノードを構築する補助関数
struct Tree* tcons( int x , struct Tree* l , struct Tree* r ) {
   struct Tree* n ;
   n = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
   if ( n != NULL ) {
      n->data = x ;
      n->left = l ;
      n->right = r ;
   }
   return n ;
}
// 木を表示する補助関数。枝の左右がわかる様に...
void print( struct Tree* p ) {
   if ( p == NULL ) {
      printf( "x" ) ;
   } else {
      printf( "(" ) ;
      print( p->left ) ;
      printf( " %d " , p->data ) ;
      print( p->right ) ;
   printf( ")" ) ;
   }
}
// 木に1件のデータを追加する補助関数
void entry( int x ) {
   struct Tree** ppt = &top ;

   while( (*ppt) != NULL ) {
      if ( (*ppt)->data == x )
         break ;
      else if ( (*ppt)->data > x )
         ppt = &( (*ppt)->left ) ;
      else
         ppt = &( (*ppt)->right ) ;
   }
   if ( *ppt == NULL )
      (*ppt) = tcons( x , NULL , NULL ) ;
   }
int main() {
   entry( 51 ) ;
   entry( 26 ) ;
   entry( 76 ) ;
   entry( 60 ) ;
   print( top ) ;
   // ((x 26 x) 51 ((x 60 x) 76 x))

   top = NULL ;
   entry( 26 ) ;
   entry( 51 ) ;
   entry( 60 ) ;
   entry( 76 ) ;
   print( top ) ;
   // (x 26 (x 51 (x 60 (x 76 x))))
}

前回の授業で、処理速度のオーダ記法について解説し、 実際例と処理速度の問題について解説する。 後半は、再帰呼び出しの処理速度見積もりのための再帰方程式を示す。

特殊な処理時間の見積もり

前回授業の最後に検討しておくようにと伝えた、 の処理時間のオーダについて、Nが巨大となった時の、最大項を見つければ良いことから、 が、N→∞において 発散するのか収束するのかを求める方法にて説明する。

また、2つのアルゴリズムがNの増加で処理時間が変化する時の事例として、 「データ件数が10件で、最大選択ソートが10msec、クイックソートが20msec出会った場合、 データ100件では、どちらが速いか？、この結果から、 データ件数がいくつ以上であれば、どちらの方法が良いか？」 といった問題について説明する。

最大選択ソートであれば、 より、 であるとする。 一方、クイックソートは、 より、 であるとする。 より、 。 より、 。

これより、データ100件の場合には、 となる。 また、 となりクイックソートの方が速い。

さらに、 となるNを求めれば、N件以上は クイックソートが速い…といった件数を求められる。

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。

// 階乗
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、 で表せる。 これを代入によって解けば、 で表せる。 こういった式は、再帰方程式と呼ばれ、一般式を求めることとなる。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。 ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 ということが予想される。

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。 これより、

ということが言える。 ディスクが 枚で、予想が正しいと仮定すると、 枚では、

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

今回は、情報処理センターの機種更新に伴うパスワード再発行やら、 授業アンケートの作業に前半の時間をとられ、そのまま演習室にて授業。

2分探索法の処理時間分析

最初に、先週説明の単純サーチ と、２重ループの最大選択法 との比較をしながら、 以前のBLOG資料を使って、 2分探索法の処理時間が であることを説明する。

オーダ記法

次に、定番の説明であるけれど、 「単純サーチで、100件で1msecかかった。 データ10000件なら何秒かかる？」 同様に、「最大選択法のプログラムで、100件で10msecかかったら、10000件なら何秒？」 という質問から、オーダ記法の導入を説明する。

最後に、 , , といった、Nが大きな値になった時に、式で大きな値となる主要な部分を抜き出したもの がオーダといった説明を行う。

次回の授業での予習ネタとして、以下の式のオーダについて考えておくように…

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

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

いいプログラムとは？

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

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

処理速度という観点では、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 ;
}

個人的には、なかなか、的を得た数字のように思うな…

• 本の虫：60%の人間はプログラミングの素質がない…

「ふたこぶラクダ」という名前の有名な論文に書かれているんだってさ。

引用：プログラミングの素質は、構築したメンタルモデルを、 ブレずに一貫して適用できるかどうかにかかっているようだ。

それぞれのプログラミング言語の都合に合わせて、動くようにプログラムを書くのだから、 わけのわからない言語のルールに、ブレずにしたがって頭の中で動く様をシミュレートできるか…って感じかな。

引用：一貫したグループにプログラミングを教育するのは、はるかに簡単である。 このグループは、観測的に、さらにふたつに分かれるようだ。 ひとつは、プログラミングを非常に簡単に感じ、プログラミングを楽しみ、 その後も成長してソフトウェアを書く良いプログラマーになるグループ。 もうひとつのグループは、プログラミングはできるものの、 それ自体には楽しみを見出さず、管理職になってUML図に溺れるグループ（やれやれ）。

爆笑….