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

ハノイの塔

ハノイの塔は、３本の塔に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は不要…