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

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図に溺れるグループ（やれやれ）。

爆笑….

再帰呼び出しを含む処理の、速度分析の説明として、ハノイの塔とマージソートを 説明する。

ハノイの塔

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

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

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

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

マージソートの処理速度分析

最も高速なソートアルゴリズムとして、クイックソートがあげられる。 しかし、説明が分かり難いので、同じ処理速度のオーダとなる、 マージソートの分析で説明する。

マージソートのアルゴリズムは、

• データが１件の時は、そのまま。
• それ以上の件数では、
  • データを中央で２分割して、それぞれをマージソートを行う。
  • 出来上がった２つのデータ列を、先頭から２つを比較し小さい方から移し替える。

この方式であれば、再帰方程式として、以下の式が示される。

N=1,2,4,8,…と、代入を繰り返すと、処理時間は、 であることがわかる。

プロコンの競技部門の学生さんたちが、最後の追い込み。 各パーツに分かれて動作確認が取れてきたし、 １つのプログラムに合成する最後の段階になっている様子。 しかしながら、合成した後プログラムが動かないとの相談。 1度目の処理は動くけど、2回目で動かないという状態なので、 不完全な初期化データを使って動かなくなっているのではと想像する。 といっても、そう簡単に間違いが見つかる訳もないけど、 ひとまずコードを見せてもらう。 すると、覚えたての分割コンパイルで、ヘッダファイルの中に、 static int array[…] ; といった記載が見つかる。

このままでは、array[] が、各C言語ファイル毎に、file-scope の別な実体を持つため、 大域変数渡しの副作用が伝わらなかったり、その結果として未初期化が発生したり。

ファイルスコープ

C言語では、静的変数の局所変数を作りたい場合、関数ブロック内で "static"キーワードを指定すればよい。 しかしながら、関数ブロック外で static キーワードをつけると、 分割コンパイルした場合、file-scope を持つようにコンパイルされる。 つまり、各ファイル毎の大域変数は、たとえ同じ名前の大域変数が別ファイルに あったとしても、別な記憶領域を確保してくれる。

(( aaa.c ))
int x1 ;         // 静的変数・大域変数
static int x2 ;  // 静的変数・大域変数・ファイルスコープを持つ
void foo() {
static int x3 ; // 静的変数で局所変数
:
}
(( bbb.c ))
extern int x1 ;  // aaa.c の x1と同じ実体を参照できる。
static int x2 ;  // aaa.cのx2とは大域変数だけど別の実体をもつ

分割コンパイルして、各ファイルで共通の変数や関数を定義する場合は、 以下のように行う。 ポイントは、extern によって宣言すると、実体は別のところにある変数となる。

(( common.h ))
int foo() ;      // プロトタイプ宣言
extern int bar ; // 実体はどこかで確保される変数として宣言
(( aaa.c ))
#include "common.h"
int bar = 123 ;  // 変数barの実体
int foo() {
// 関数foo()の実体
}
(( bbb.c ))
#include "common.h"
void main() {
bar = 234 ;              // aaa.c の大域変数barに代入
printf( "%d" , foo() ) ; // aaa.c の関数foo()を呼び出し
}

今週は、福井高専では『学力強化週間』ということで、前期授業で理解が浅い学生さんのために、 補講を行うことになっている。 ということで、3年のプログラミング応用、4年の情報構造論について補講を行った。

4年情報構造論

前期では、リスト構造のプログラミングが中心であったので、以下のような課題を、 実際に黒板に書いてもらいながら、説明をしたり、穴埋めや処理の目的を聞きながら、 補講となった。補講は2コマ分しかないので、必要最小限でかつ自分で考えることを目標に行った。

• 昇順の配列の途中にデータを挿入。(挿入場所を探して、後続のデータを1件分後ろにずらして挿入)
• 配列中のデタラメな順序の配列と、昇順になるように次のデータの配列添え字の配列で、 リストもどき。(配列添え字をたどりながら全データ表示)
• リスト処理の宣言の後、リストのデータを1件づつ表示。

やはり成績不振の学生さんは、2年レベルの配列処理でさえもコードが書けない。 すこしづつ経験と、処理を追いかけることができるようになることが重要。 ということで、ループの処理順序と値の変化を追う練習ということで、 上記課題の処理順序と値の変化を処理終了まで記載する課題をだして終了。

3EIプログラミング応用

前期では、2年の復習およびファイル処理とポインタの基礎だったので、 これを踏まえ処理の順序を追いかける練習を中心に補講を行った。

• forループ途中でbreakのプログラムの処理トレース、およびフローチャートを記述
• forの2重ループで、処理のトレース、およびフローチャートの記述
• 配列中の最大値・最小値の差を表示プログラムを作成
• ファイルからのデータ入力の基礎プログラムを説明。(fopen,fclose,fscanf)
• ファイルに記載されているデータを読み込み、最大最小値の差を表示

メモリー利用の問題点として、C言語の固定配列サイズの 問題点を紹介し、その対応として、malloc/freeを紹介。

たとえば、複数の名前を配列に記憶する場合、

char name[ 100 ][ 20 ] ;

では、平均名前長が8文字ぐらいだと、12文字/件の無駄が 発生するし、ジュゲムのような長い名前は覚えられない。

そこで、その対応として、

char heap[ 2000 ] ;
char* name[ 100 ] ;

として、

               ↓name[1]      ↓name[3]
heap: t-saitoh$tomoko$mitsuki$jugemujyugemu......$ayuka$
      ↑name[0]       ↑name[2]

といった、最初に巨大配列を一括して確保しておき、 データに応じて細切れにして使う手法を説明する。 こうすれば、メモリ空間は「詰めて」保存ができ、 無駄が排除できる。 でも、この領域で、途中途中のデータが不要になったら、 その隙間の管理は面倒。

malloc/free

そこで、malloc/free はこれらをうまく活用してくれる。

int size ; //サイズが入っているとする。
int* p ;
// size*sizeof(int) byte のメモリを確保。
// その先頭アドレスを返してくれる。
// 型キャストののち、p に代入。
p = (int*)malloc( size * sizeof( int ) ) ;
// 処理後に領域が不要になったら、freeで解放。
// 必要に応じて再利用してくれる。
free( p ) ;

ただし、通常は、malloc はメモリ確保時に、NULL を返すので、 if でチェックの必要がある。一般的な使い方は、

int size ;
int* array ;
scanf( "%d" , &size ) ;
array = (int*)malloc( size * sizeof( int ) ) ;
if ( array != NULL ) {
   for( int i = 0 ; i < size ; i++ )
      scanf( "%d" , &array[ i ] ) ;
   :
   free( array ) ;
}

ただし、free を忘れると、メモリリークが発生し、メモリの無駄な利用は、 仮想記憶の利用から、補助記憶への読み書きを発生させ、処理速度低下を 招くかもしれない。その他の内容は、以下の通り。

• 終了直前のfreeならなくてもよい。
• ネットワークプログラミングでは、子プロセス終了時に自動解放がよく使われる。
• スタック領域を使うんなら、alloca() という関数もある。
• C++なら new / delete 演算子を使う。
• ガベージコレクタのある処理系(java/C#)なら、freeは不要…