先輩講座で進路トーク
本科二年生に、就職進学の意識を早々と持ってもらうための、先輩講座が行われました。 五年生の進学／就職で、頑張っていた人に、進路を決めるまでの心境や頑張ったことを、インタビュー形式で語ってもらいました。
2012年11月11日(第294回)
誠市、ご縁市開催中でした！
- 11月11日ということでお菓子の話
- 食べ物の話
担当：松島（１Ｃ）、山野（１Ｃ）、西（教員）
田中君がご縁市でお手伝いしている露店から豚汁を持ってきてくれました！
ハッシュ法
2分木なども終わって、検索処理のさらなる高速化として、 ハッシュ法を説明する。
オープンアドレス法
電話番号が記録されているのかどうかを探す処理を考えると、 最も単純な方法は、電話番号を配列の添字にする方法となる。
int array[ 1000000 ] ; // 局番2桁+4桁
void entry( int phone ) {
array[ phone ] = phone ;
}
int search( int phone ) {
if ( array[ phone ] == 0 )
return 0 ;
else
return 1 ;
}
しかしこの方法では、0778621111 といった番号も考えると、 巨大なメモリを必要として、非現実的となる。 この際の解決法がハッシュ法で、データ件数が少なければ、 例えば電話番号の末尾2桁がおなじデータの発生する確率は低い。 もし、電話番号末尾2桁が同じでも、その番号の次の場所に保存するなどすればよい。
#define SIZE 100 // ハッシュ表のサイズ
int hash[ SIZE ] ; // ハッシュ表
int hash_func( int phone ) { // ハッシュ関数
return phone % SIZE ;
}
void entry( int phone ) {
int idx = hash_func( phone ) ;
while( hash[ idx ] != 0 ) // データ件数100で無限ループだけど...
idx = (idx + 1) % SIZE ;
hash[ idx ] = phone ;
}
int search( int phone ) {
int idx = hash_func( phone ) ;
while( hash[ idx ] != 0 ) {
if ( hash[ idx ] == phone )
return 1 ;
idx = (idx + 1) % SIZE ;
}
return 0 ;
}
チェイン法
オープンアドレス法では、次の空き場所を探して保存するが、 表サイズよりもデータ件数を多く保存することはできない。
表が埋まって、同じハッシュ値のデータがでてきたら、同じハッシュ値同士を リスト構造で保存する方法はチェイン法と呼ばれる。
struct List *hash[ SIZE ] ; // ポインタはNULLで全て初期化
void entry( int phone ) {
int idx = hash_func( phone ) ;
hash[ idx ] = cons( phone , hash[ idx ] ) ;
}
int search( int phone ) {
int idx = hash_func( phone ) ;
struct List* p ;
for( p = hash[ idx ] ;
p != NULL ;
p = p->next )
{
if ( p->data == phone )
return 1 ;
}
return 0 ;
}
認証評価を前にWebサーバダウン
自宅にてくつろいでいるなか、 11/7,20:18に、学校の www.fukui-nct.ac.jp のサーバが 動いていないとの警告メールが携帯に届く。 nagios3 での監視状況からすると、学内の他のサーバは どれも稼働中で、落ちているのはメインサーバだけっぽい。
ただ、明日の認証評価の実地審査では、学内グループウェアや エビデンス系のデータサーバなどが使われる。 んで、さすがにこれらのサーバは動作監視の対象外だし、 これが落ちていたら朝から学校中、冷や汗仕事になるのは必至。 しかたなく学校に出向いて状況確認。
まずは自室で確認すると、メインWebサーバ以外安定稼働中。 情報処理センターの内藤さんも駆けつけてくれたので、 サーバ室にて状況を確認すると、WebサーバのUPSが、 ピーピー鳴って出力停止でフリーズしてた。 壊れた状況は、また明日確認ということで、電源直結にして 帰宅となった。
はぁ。
ワードアライメントとビットフィールド
先週の構造体の演習が1週2コマでは不足っぽいので、前半座学+後半演習とした。
ワードアライメント
struct FOO {
char a[ 6 ] ;
int b ; // sizeof( data ) は (6+4)*10=100byte?
} data[ 10 ] ; // 実際は、(6+2+4)*10=120byte。
このような構造体を作ったら、構造体1件あたりのメモリの使用量は何バイトであろうか？ 6+4の10byteと思うかもしれないけど、32bitコンピュータなどであれば、12byte になるのが一般的。
これは、CPUとメモリのデータの速度を比べると、メモリの速度の方が遅い。 このため、CPUがメモリとデータのやり取りをする時は、1ワード(32bit)など まとめて読み書きをするのが一般的。
pack状態 隙間あり +|0|1|2|3| +|0|1|2|3| 00|a|a|a|a| 00|a|a|a|a| 04|a|a|b|b| 04|a|a|x|x| packされた状態では、 08|b|b|a|a| 08|b|b|b|b| data[0].bは、6,7,8,9番地になる。 12|a|a|a|a| 12|a|a|a|a| するとワード単位の読み出しでは、 16|b|b|b|b| 16|a|a|x|x| 04行と08行の2回に分けて読まれる。
構造体のchar a[6]とint bが隙間なく配置されると、ワード単位の読み書きでは メモリの読み出し回数が増えて、機械語の実行速度が遅くなる。 このため、構造体ではデータがワード単位の区切り(ワードアライメント) をまたがないように、データ間に隙間を入れるのが一般的。
ビットフィールド導入
struct Birthday {
int year ;
int month ;
int day ;
} ;
このような構造体を考えると、1件あたり4×3=12byteを要する。 しかし、年は西暦であれば2047までであれば、11bit で十分であり、 monthは0〜11までの4bitで十分。dayであれば1〜31の5bitで十分。 西暦を4095までの12bitとしても、21bitで1ワードに収まるデータであり、 最初の誕生日構造体はメモリ上無駄がある。
また、この誕生日データでは、年齢の比較をする際にyear,month,dayの比較を 要し、処理的にも煩雑となる。この様な時は、10進数の桁を使って、 以下の様なテクニックもよく使われる。
int ymd( int y , int m , int d ) {
return y * 10000 + m * 100 + d ; // 1999年7月14日は、19990714
}
int month_ymd( int ymd ) {
return (ymd / 100) % 100 ; // 19990714から7を取り出す
}
しかし、この方法では、合成や分解で100といった2進数的に切りの悪い、 乗除算計算の遅い組込系のCPUでは処理が遅くなる。 それに、月を0〜99までの数値として扱いメモリもちょっと無駄。 そこで2進数を使って、year=12bit,month=4bit,day=5bitで扱う方法であれば、 以下のようになるであろう。
int ymd( int y , int m , int d ) {
return (y << 9) | (m << 5) | d ;
}
int month_ymd( int ymd ) { // YYYYYYYYYYYYMMMMDDDDDから
return (ymd >> 5) & 0xF ; // MMMMを取り出す。
}
2012年11月4日(第293回)
- 遠足の報告
Ｆ１クラスは金沢、Ｆ４クラスは京都に行ってきました - 資格試験について
危険物取扱者試験 - ハロウィンの話
担当：松島（１Ｃ）、山野（１Ｃ）、西（教員）
いつもミキサーを担当している前田君は見学旅行明けのためお休みでした。
Facebookの福井高専ページ
Facebookにて、福井高専の名前が変な人に使われないようにと、 "福井工業高等専門学校"のページを作ってある。 さらに"いいね!"をしてもらえるように、高専の速報記事が 自動的に掲載するようにしてある。
この状態で約半年近く運用をしてきて、それなりに認知されている状態。 ということで、管理者パネルでみれる情報の一部をキャプチャで公開。
VMware ESXiのインストール
次期学科サーバは、余力のある多機能な仮想サーバ上で動かそうと、 VMware ESXi(free)を入れてみた。ゲストOSに、DebianとWindows Server2008 を入れてひとまずお試し。
ただ、インストールの際は、自室のMac環境では、Mac用の vSphere client が無い。そこで、Parallels Desktopで Windows 7を動かしてその中で、 Windows用 vSphere client を動かしてインストール。
あまりにも仮想環境のためにCPU無駄遣いとは思いながらも、 vSphere client 越しに、仮想サーバのWindows Serverが普通に立ち上がる。 ここまで来たら、 無駄の極みの処理速度を実感してみようと、 ゲストOSのDebianとWindowsの間を、 リモートデスクトップでつないで動かしてみた。
それでも、遅いと思いながらも使える速度で Firefox が立ち上がった。
(Mac OS X Snow Leopard) - Parallels Desktop for Mac (Windows 7 Ultimated) - vSpere client for Windows (VMware ESXi 5.1) (Windows Server 2008r2) - Remote Desktop for Windows (Debian 6.0/testing) XRDP - gnome / Firefox
