前回の再帰処理の再帰方程式をたてた処理時間予測の話の次として、 クイックソートの処理時間について解説を行う。 といっても、直感的に分かりにくいので、同じ アルゴリズムのマージソートを使って説明。 後半では、次に説明する動的メモリの説明の前説として、 C言語の固定サイズ配列のメモリ使用効率の悪さを説明する。

マージソートとは、与えられたデータを2分割し、それぞれをマージソート処理で 並び替え、その2つのデータの先頭から比べて大きいほうから格納しなおすアルゴリズム。 このため、再帰方程式は、以下のようになり、

代入を繰り返すことで一般式として、 を導きだすことができる。

この後、クイックソートと最大選択法の比較として、データ件数に応じた アルゴリズムを選択するための考え方を示す。 例えば、最大選択法で100件で2msec、クイックソートで同じく100件で1msec で処理が可能だった場合、何件以上であればクイックソートを使うべきか… という分析方法を示す。

よって、 =0.2μsec, =5μsec
よって、クイックソートの処理時間の一般式と、最大選択の一般式を イコールとして求まったデータ件数が、分岐点となる。 これを解くと、25=N/log N を満たすNであり、ニュートン法などで解けば、 この例ではN=40ぐらいとなる。 よって、40件以上ではクイックソートを採用すべきという結論が導ける。

このことから、一般的なC言語の組み込み関数のqsortなどでも、 データ件数が少なくなってくると、 O(N^2)のアルゴリズムに切り替えるようにプログラムされている。

C言語の固定サイズ配列の問題点

次に、固定サイズ配列の大きさの問題点を説明するために、 「名前と電話番号のデータベースを作りたい。宣言は？」 と聞いてプログラムを書いてもらい、その問題点を説明。

struct DataA {
char name[ 20 ] ;
int   phone ; // 09020932925は2^31より大きい
} table[ 45 ] ;
struct DataB {
char name[ 10 ] ;
char phone[ 12 ] ; // (0778)-27-2925#1234##
} table[ 100 ] ;

電話番号だってトーン機能を使うことも考えたら、12桁では足りないし、 名前も漢字5文字だったら、16bit×5=10byte で、足りないかも。 ひねくれた話をすれば、名前がジュゲムだったらどうするのとか、 1クラスではなく、1学年、1学科、1学校とかになれば、 配列は足りないし、使う可能性も低いのに配列サイズに巨大な値を 使えば、メモリ不足が発生する。

ということで次週にmallocなどを説明予定。

前回がN進数の話だったので、負の数の取り扱いや数値範囲について説明。 1byte 整数の話も含め、簡単に char 型の話をしたあと、 signed(符号あり) , unsigned(符合なし) , short int(通常16bit) , int(通常32bit) , long int(処理系によっては64bit) という型の数値範囲を説明する。

// 昔の16bitパソコンで動かない事例
//   640x480なモニタで、マウス座標とターゲットの距離
int distance( int x1,int y1, int x2,int y2 ) {
return sqrt( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) ) ;
}

上記のプログラムは、16bitパソコンでは動かない可能性がある。 x2,x1が200離れていただけでも、40000を超えた数値になり、(2^15-1)=32767 を超えてしまう。整数型で上限を超えた場合、符号ビットが1になる 状況では、本来なら２乗の和で負の数にはなりえないはずだけど、 負の数の平方根(sqrt)の処理より、異常終了となる。

// 32bitコンピュータで、int(32bit)でunix時間を扱う場合
int mid_time( int t1 , int t2 ) {
return (t1 + t2) / 2 ; // t1 + (t2 - t1)/2 と書くべき
}

この他に、2000年問題の話をしたあと、unix時間が1970年からの経過秒数であり、 時間を32bitで扱う場合、2037年には(2^31-1)を超えて時間の処理に 失敗擦る可能性を説明する。また、下記のような時間の「なか日」を求める 処理でも、1970年+(68年/2) = 2004年以降ではトラブルの原因となる。