2011年5月15日(第216回)
- 鯖江のB級グルメについて
- 5月7日に行われたキャンパスウォークについて
- 寮祭について
ぐはっ…でも状況からす…(05/13)
- 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などを説明予定。
数値の範囲と負の数の取り扱い
前回が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年以降ではトラブルの原因となる。
午前中の部がそろそろ終…(05/07)
2011年5月8日(第215回)
収録でお届けしました。
- 先生紹介 機械工学科 五味先生
コンピュータゲームとの出会い
2011年5月1日(第214回)
収録でお届けしました。
- 先生紹介 機械工学科 五味先生
- 第４７回体育祭について 関係学生インタビュー
今日は体育祭
4/29の祝日ですが、学校日程の都合もあり本来昨日予定の 体育祭が雨で延期になって、今日が体育祭です。 雨が降ったりして、競技が一部中止になったり…
再帰処理の速度分析
例年通りの進み方なんだけど、再帰処理の速度分析をするための説明を行う。 最初に、fact(N) , 配列の2分割積算 , fib(N) のプログラムを示し、 処理の流れのトレースを解説。 この後に、ハノイの塔の再帰方程式と数学的帰納法による証明を説明する。
ハノイの塔のディスクの移動回数を、 で表す。 ハノイの塔のルールより、N枚のディスクの移動には、(1)最下層の1枚の上にある、(N-1)枚を 隣に移動、(2)最下層の1枚を移動、(3)一旦隣に動かしておいた(N-1)枚を、目的の塔に 移動というステップを経由する。このため、
ただし
また、最終的には、
が成り立つ。
ハノイの塔は、少ない枚数での移動を解いてみると、 が予想される。 この式が常に成り立つことを証明するため、
枚についてこの予想が成り立つものと仮定する。 この時、
枚については、
が成り立つので、
となり、 でも仮定が成り立つことが示される。よって、数学的帰納法により仮定は全ての 自然数について成り立つ。
この証明のような、式の中に自分自身が含まれるような方程式を、再帰方程式と呼ぶ。 再帰処理の速度予測では、これと同じように再帰方程式をたてる事ができる。
プログラムと再帰方程式
int fact( int N ) {
if ( N == 1 )
return 1 ;
else
return N * fact( N - 1 ) ;
}
このプログラムの処理時間は、N=1においては、if,==,return の一定の処理が行われるので、
Nが2以上では、if,==,*,-1,returnの処理と、fact()の再帰が行われる。よって、
この再帰方程式を、代入を繰り返しながらとけば、
が導き出せる。よって、階乗の再帰プログラムの処理時間のオーダは、 となる。
創造工学の導入実験でPerlと正規表現
4年の前期実験では、2週分を創造工学でのシステム作りの導入とするための、 基礎実験を行っている。クラスを3グループに分け、私の担当は初回にPHPによる、 Webプログラミングの説明。これにより簡単な掲示板やアンケートを作ってもらった。
2回目の今日は、1日実験でPerlと正規表現の実験を行った。 最初に、超単純英語によるBot作りをネタに、Perlの基本文法と、正規表現を体験してもらう。 理解度が速い人向けに、後半はメールデータを題材にしながら、 Jcode.pmを用いた文字コード変換、headerのmime_decodeを説明し、 このメールデータの中から、From,Toの部分を抽出するプログラムを作ってもらう。
#!/usr/bin/perl
# 超基本英語によるBot
while( <> ) {
$line = $_ ;
if ( $line =~ /like/ ) {
if ( $line =~ /^(.*)\s+like(|s)\s+(.*)\.$/ ) {
print "$1 は $3 が好きです。\n" ;
}
}
}
#!/usr/bin/perl
# メールデータの文字コード変換
use Jcode ;
my $head = 1 ;
while( <> ) {
$line = $_ ;
if ( $head ) {
print Jcode->new( $line )->mime_decode->utf8 ;
if ( $line =~ /^$/ ) {
$head = 0 ;
}
} else {
print Jcode->new( $line )->utf8 ;
}
}
Perlを初めて使ってもらうので、 暗黙変数$_とのマッチングや、 「式 if ( 条件 ) ;」といった Perl らしい節操のない書き方は、説明を避けた。