2011年5月29日(第218回)
- マニアックタイムズ 第3回 2年電子情報工学科 山田さん
最近のライトノベルについて - 台風2号の接近について
創造工学演習・テーマ提出
今日は、創造工学演習で自分たちがこの後作ろうとするシステムの アイデアをまとめた資料の提出日。 高専プロコンへの応募を想定しているので、その書式に沿ったパワポA4 x 12枚の資料。
でも提出資料だけれど、見て何をするシステムなのか、さっぱり解らない資料もぞろぞろ。 例年だったらプロコン応募締め切りがあるので、 ボツネタ回収になっちゃうけど今年は、時間的な余裕もあるのでダメだしを行う。
資料が解らない原因は、利用者がどう使うのかが明確に書かれていなかったり…。 機材をどう使うのか分かるような、イメージ図(ポンチ絵)とか、 利用者が実際に使う状況のシナリオとか重要だよねぇ〜…と伝える。
2011年5月22日(第217回)
- サイエンスクラブの活動について
- 修学旅行、工場見学旅行について
浮動小数点と、文字列数値変換プログラム
先週の整数型の数値範囲の続きということで、浮動小数点の数値の範囲の話の後、 数字の文字列を、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…ほとんどダメじゃん…
2011年5月15日(第216回)
- 鯖江のB級グルメについて
- 5月7日に行われたキャンパスウォークについて
- 寮祭について
ぐはっ…でも状況からす…(05/13)
- 05/13 ぐはっ…でも状況からすれば避けられん… #fnct 国家公務員給与:「10%減」 政府、労組と交渉へ – 毎日jp(毎日新聞) 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などを説明予定。
数値の範囲と負の数の取り扱い
前回が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になる 状況では、本来なら2乗の和で負の数にはなりえないはずだけど、 負の数の平方根(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年以降ではトラブルの原因となる。
午前中の部がそろそろ終…(05/07)
この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。