先週は、配列の固定長サイズによる問題の対応として、malloc() + free() による 動的メモリの管理手法の演習をしていたので、 その続きとして配列の欠点の挿入削除問題を説明。

配列に単純にデータを入れる処理でも、様々な方法がある。 最も簡単な方法は、配列とサイズを保存しデータを追加したい場合は、 末尾に入れる方法。

int array[ 100 ] ;
int size = 0 ;
void entry( int x ) {
array[ size ] = x ;
size++ ;
}

しかしこの方法では、デタラメな順序でデータが与えられれば、配列内は デタラメな順序となり、中身のデータ検索は「単純検索」をするしかなくなり、 処理時間のオーダは、O(N)となってしまう。

データを素早く見つけたいのであれば、2分探索法をするためにも、 配列が昇順に並んでいなければならない。 そうなると、昇順に並んだデータ列の途中に、与えられた情報を挿入する 必要が出てくる。

理解力を確認するために、昇順配列への追加処理ではどんな処理をするか 聞いてみると、「末尾に追加してクイックソートすればいい…」といった 考えの人が多かった。クイックソートはほぼ昇順に並んでいるといった データは苦手であり、O(N^2)になるから極めて遅いって…

void insert( int index , int x ) {    // 領域が重複している時は
for( i = size ; i > index ; i-- ) // 後ろからコピーが必要かも。
array[ i ] = array[ i - 1 ] ;
array[ index ] = x ;
size++ ;
}

しかし、この処理には、O(N)の処理時間を要する。

この対策として次のデータの場所を保存する方式であれば、 挿入作業はO(1)にできることを説明する。 実際のリスト構造でのプログラムは来週とし、 課題未消化のひとが多いので後半は課題時間とした。

例年、文字列-数値変換(atoi,itoa)の課題をやっていると、 「型」という視点が弱いことがわかる。 そこで型など基本的な間違ったプログラム例をあげて、 型の違いで動かないという例を様々なパターンで説明する。 またポインタの概念についても説明を行う。

型の間違いの例の前に、関数でも引数の型の話の中で、 #include の説明も兼ねて、プロトタイプ宣言と古いK＆R文法を紹介。 動かない例の中では、引数の型間違い,"C"と'C'の違い,未初期化ポインタの使用,配列あふれなどを説明する。

• 配布資料(eval,#include,動かない例)

次に、ポインタの説明。 ポインタ+整数での指示場所の移動や、p[i] は *(p+i) と等価であることの説明など。 ポインタをずらしながらのループの説明がまだ。 for(…; p++ )

• 配布資料(ポインタの使い方)

今日は、創造工学演習で自分たちがこの後作ろうとするシステムの アイデアをまとめた資料の提出日。 高専プロコンへの応募を想定しているので、その書式に沿ったパワポA4 x 12枚の資料。

でも提出資料だけれど、見て何をするシステムなのか、さっぱり解らない資料もぞろぞろ。 例年だったらプロコン応募締め切りがあるので、 ボツネタ回収になっちゃうけど今年は、時間的な余裕もあるのでダメだしを行う。

資料が解らない原因は、利用者がどう使うのかが明確に書かれていなかったり…。 機材をどう使うのか分かるような、イメージ図(ポンチ絵)とか、 利用者が実際に使う状況のシナリオとか重要だよねぇ〜…と伝える。

今年は舞鶴さんを招待しての交歓試合。 運営バタバタだけど…

先週の整数型の数値範囲の続きということで、浮動小数点の数値の範囲の話の後、 数字の文字列を、N進数の考え方を元に数値に変換したり、 その逆の変換をするプログラムを説明。 来週は、演習室で数値変換の演習。 最後に時間が余ったので、#define 文などの説明を行う。

浮動小数点データの値の範囲

最初に浮動小数点データの正規化を分かってもらうために、 実験データの精度の話を行う。「1.2345の真値と1.222という実験値の誤差を求めよ」 と聞いてみると、みんな1.013%と答える。 でも実際には、桁落ちが発生し誤差を考えると1.0%と2桁で記載すべきことを説明する。

この桁落ちで、有効桁が減ったままだと後々の計算がさらに精度が悪くなるので、 浮動小数点では計算後で桁落ちなどがあった場合、 最初の意味のある桁まで小数点を移動すること…ということで正規化を説明する。

このように指数部を変化させながら…という説明をした後で、floatやdoubleが 以下のように数値を扱うことを説明。

	符号(s)	仮数部(e)	指数部(d…)	意味
float	1bit	8bit	23bit
double	1bit	11bit	52bit

文字列数値変換プログラム

次に、文字と文字コード、文字配列、N進数変換を理解するための定番のネタということで、文字列数値変換プログラムの説明。

// 文字列を数値に変換
int my_atoi( char s[] ) {
int ans = 0 , i ;
for( i = 0 ; s[i] != '¥0' && s[i] >= '0' && s[i] <= '9' ; i++ )
ans = ans * 10 + ( s[i] - '0' ) ;
return ans ;
}
// 数値を文字列に変換
#define SINT_WIDTH 5
char* my_itoa( char ans[] , int x ) {
int i ;
ans[ SINT_WIDTH ] = '¥0' ;
for( i = 0 ; i < SINT_WIDTH ; i++ ) {
int d = x % 10 ;
ans[ SINT_WIDTH - 1 - i ] = '0' + d ;
x = x / 10 ;
}
return ans ;
}

いつも授業中には「質問ありません？」としつこく聞くんだけど、授業が終わったら 何人かの学生が、my_itoa の返り値が char* な説明を聞きにくる。 このプログラムでは、printf( "%s" , my_itoa( temp , 1234 ) ) みたいな 使い方を想定していることを説明し、文字配列の先頭(ポインタ)を返していることを 説明。

#define文

説明後に時間も余っているし、来週の演習後に説明予定であった#defineの説明を 行う。プログラム中の利用目的が解らない定数は、一般的にマジックナンバーと呼ばれ、プログラム修正が困難になることを説明し、定数宣言が便利であると解説。

C言語でこれに相当するのが、#define… と言う前に、プリプロセッサ処理を 説明し、Cソース→[プリプロセッサ]→[コンパイラ]→中間コード→[リンカ]→機械語 といった流れも説明する。
#defineマクロについては、演習後に説明の予定。

ずーっと、講義録をMovableTypeでメモしており、数式部分には mimetex.cgi を使っている。しかしながら、MobableTypeのバージョンが上がったためか、最近、数式内で ¥times とかを書くと「¥」にエスケープ処理が入るため、正しく×が表示されない。 TeXで「¥」が使えなかったら、¥frac…ほとんどダメじゃん…

• 05/13 ぐはっ…でも状況からすれば避けられん… #fnct 国家公務員給与：「１０％減」　政府、労組と交渉へ – 毎日ｊｐ(毎日新聞) http://mainichi.jp/select/seiji/news/201… via @mainichijpnews

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。

前回の再帰処理の再帰方程式をたてた処理時間予測の話の次として、 クイックソートの処理時間について解説を行う。 といっても、直感的に分かりにくいので、同じ アルゴリズムのマージソートを使って説明。 後半では、次に説明する動的メモリの説明の前説として、 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などを説明予定。