週初めなのにやたらと体がだるい朝、 テンション落ちまくりですが、出勤時に２重の虹が見えました。 すこしテンション上がったかな。

職場は、昨日あたりに風が強かったのだろうか、 外も内も、風で飛ばされたようなゴミがチラホラ散乱していました。

• 11/18 全車両が同時に同じコースを走る自律ロボコンのタイムトライアル・ロボコンって面白そうじゃねぇ!? !? "組込み総合技術展2011" http://tinyurl.com/796ts4d #fnct
• 11/18 ヴィストンの二足歩行ロボットが39,900円!! 安い!! http://tinyurl.com/ygb3wos #fnct
• 11/18 学校もこういう対応が必要な時代なのか… "ブランドイメージを守るのだ！ ドメインを買いあさる大学が増えています" http://www.gizmodo.jp/2011/11/colleges-a… via @gizmodojapan #gizjp #fnct

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

今年は高専に勤めて、はや20年になりました。 学校からも(機械的にもらえるとはいえ) 永年勤続者表彰なるものを頂きました。
# こういう記念品が貰えるとは思ってなかったけど…

授業を前にひとまず、話のネタを整理しながらメモ。 授業が終わったら、加筆しまーす。 んで、今日はハッシュ法について説明を行う。 テスト前が今日を含め2回なので、説明は終わるだろう。 後期中間試験後は、参照カウンタなどのネタから説明の予定。

ハッシュ法

リスト構造や2分木などを今までの授業で解説してきたが、 O(N)やO(log N)の検索時間がかかる処理。 さらなる高速化にはハッシュ法が取られる。

電話番号でデータベースを作る場合、電話番号自身を配列の添字にすれば、 検索時も添字でアクセスするだけで、検索時間も一定でありO(1)にできる。

// 電話番号XX-XXXXの6桁で名前を検索
char name[ 1000000 ][ 20 ] ;
strcpy( 272925 , "t-saitoh" ) ;

しかしながら、この方法では大量のメモリ空間が必要となる。 ハッシュ法では、データの一部を配列の添字とする方式。 データの保存場所はハッシュ値、ハッシュ値を取り出す関数をハッシュ関数と呼ぶ。 データの一部を取り出すことから、異なるデータなのに同じハッシュ値となる場合がある。 これをハッシュ衝突と呼ぶ。

実際には、ハッシュ衝突の対策が問題となる。 例として、電話番号が使われているのかチェックする処理を考える。

#define SIZE 100
int  table[ SIZE ] ; // ハッシュ表には電話番号を保存
int hash_func( int tel ) { return tel % SIZE ; }
int idx = hash_func( 272925 ) ;
table[ idx ] = 272925 ;

上記のような処理でデータを扱う場合、ハッシュ衝突対策の例は以下のようになる。

void entry( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] != 0 ) {  // 先着データがあれば+1に保存
idx = ( idx + 1 ) % SIZE ;
}
table[ idx ] = tel ;
}
int search( int tel ) {
int idx = hash_func( tel ) ;
while( table[ idx ] == 0 ) {
if ( table[ idx ] == tel )  // 見つかった
return tel ;
idx = ( idx + 1 ) % SIZE ;
}
return 0 ; // 見つからない
}

ただし上記のプログラムでは、ハッシュ表がすべて埋まったら無限ループになってしまうので、その対処を追加する必要がある。

最初に、SQLで説明のしてなかった、CREATE VIEW を補足説明し、 後半はデータベースの設計の話をする。 悪い設計の例ということで、学校で使っている緊急連絡システムや授業アンケートを 例にとりながら、手抜きでOKな部分と不整合などの問題点を、 設計の腕の見せ所…という点で説明を行う。

SQLの補足

CREATE VIEW 命令は、アプリケーションプログラマーが データベースを扱いやすいように、 SELECT命令で取り出されたテーブルを、あたかもそういうテーブルが あるように見せかける機能。 これにより、外部スキーマとして分かりやすくプログラムが書ける。

CREATE VIEW 名前( 要素 ... )
AS
SELECT 要素 FROM テーブル WHERE ... ;

教科書では、ホスト言語での取り扱いが記載されていたが、 授業ではホスト言語と連携する際のプログラムの問題として、 SQLインジェクションの危険性を示した。

データベースの設計

データベースの設計の話として、学生が授業を受講する際のデータベースを例にしながら、 悪い設計と、不整合の問題を説明する。 これらの不整合を解決するには、データベースの設計が重要であり、一般的には ER図などを書きながら設計を行う。

ER図の１つは実体(Entity)であり、図に示す際は四角枠に名前を記載。 これに属性を丸枠で囲んで、線で結ぶ。丸枠内の属性名は、主キーであれば 下線をつけて記載する。 関連(Relationship)は、複数の実体間の相互関係を表すもので、 菱形の四角で示す。

改めて、ネットでER図を探すと、属性をUMLのクラス図と同様に書く方が主流になってきているみたい。

前回の割り込みの説明の補足として、 システムコールについて説明する。

システムコールなど

OSでは、資源保護のために、CPUの特権モードなどを活用する。 周辺装置やCPU内の重要な情報の制御は、特権モードでしか使えない。 ユーザモードでは、入出力機器の制御などの命令は「不当命令エラー」で実行できない。

ユーザが入出力命令を使うためには、システムコールが利用される。 これはソフトウェア割り込み機能を用いて実現される。 システムコールが実行されると、特権モードに移行し実際の周辺機器の制御の前に、 不当な資源アクセスをしていないか、チェックが行われる。 ユーザがシステムコールを経由せずに、入出力命令を実行すれば、 不当命令エラーとなるため、不正に資源を操作することができなくなる。

メモリ管理の説明として、上限・下限レジスタによる許可範囲外のメモリアクセスを 止める機能を解説する。 また、メモリ管理機能として、メモリ階層構造の話をする。 メモリは、CPUレジスタ・キャッシュ・DRAMによる主記憶・HDDによる補助記憶の４段階に分けられ、高速＆高価＆小容量なメモリから、低速＆安価＆大容量なメモリに分類できる。 これらのメモリでは、利用頻度の高いデータを、高速メモリ側にコピーしながら使うことで、 高速＆大容量のメモリがあるかのように使える。

ネットワークの導入説明

ネットワークの利用目的の説明として、プリンタ共有・ファイル共有・リモート接続での計算能力の共有などの「共有」の視点と、処理能力不足を補うための負荷分散、コンピュータ故障対策としてのリスク分散などの「分散」の視点を説明する。

ネットワークの物理層の説明として、様々なインタフェースの例を示す。 パラレル接続では、単位時間あたりの通信量を増やすために、複数の信号線を使う。 しかし、ケーブル本数が増え全体の太さから取り扱いが難しい。 シリアル接続では、本数が少ないためケーブルの取り扱いが容易で、長距離配線などで よく利用される。 通信速度の高速化をするためには、マイクロインダクタンスや線間容量などの影響で、 信号波形の劣化が問題となる。これらの対策としてインピーダンスマッチングなどが重要で、 SCSIなどでは、末端抵抗(ターミネータ)が重要となる。

最近のシリアル通信では、信号劣化対策を少ない信号線に施すことで、パラレル方式より高速化された方式が増えてきた。

プログラミング応用の後半で、グラフィックスのネタをするため、まずはグラフィックスの 構造について説明を行う。

最初に、CRT(陰極管方式)の説明として、電子銃から出た電子が、表示面の蛍光体を 光らせる構造を説明する。 これらを利用した表示方法に、ベクタスキャン方式（一筆書きの要領でXY座標情報で制御）と ラスタスキャン方式（走査線方式）を説明する。 ラスタスキャンでは、電子のぶつかる場所を、左右に移動させながら水平線を描き、 その水平線の場所を上下に移動させながら全体を描く説明を行う。

ラスタスキャンのCRTをカラー化する場合の構造を説明し、利点・欠点をまとめる。 利点は、色の再現性や残像が無い点だけど、欠点として、 表示面が平面にしづらい・四隅に色にじみが発生しやすい・巨大化できない、奥行きサイズを 薄くできないなど。

これらの改善として、液晶ディスプレイがある。液晶は電圧により偏光方向を制御ができる。 この液晶を、透明電極の間にはさみ、光源からの振動方向のまざった光から、一方向に 偏光した光をとりだす。これを偏光板を通して明るい点・暗い点を表示する。 利点として薄い構造のディスプレイを作れるが、欠点として斜め方向からの視野で 見づらい点や、色再現性が低い、残像が残るなどの問題点を紹介。

有機ELは、おおざっぱに言えば、発光ダイオードを面上に並べたような構造。 発光体が並ぶことから、液晶のようなバックライトが不要で薄型化ができることや、 斜め方向から見ても問題がないことを紹介する。

プラズマディスプレィは、高圧をかけたプラズマで発光するものを面上にならべた構造。 巨大ディスプレイに向いている。

後半では、ディスプレイなどでの色の扱いや、情報量について説明。

色は、光の三原色(赤,緑,青)の配合ですべての色を表現する(加色系)。 逆に、絵の具の三原色は、シアン・マゼンダ・黄色で色を表現する方法。 ただし黒をきれいに印刷するために、黒のインクの4色が一般的。(減色系)

R,G,Bは、一般的に各色が0～255の8bit、256諧調で１画素を表現することから、 絵の情報量を解説。情報そのままでは、メモリを浪費してしまうため、圧縮などの 必要性を説明し、JPEGなどを紹介する。