ホーム » 2009 » 12月 » 18

日別アーカイブ: 2009年12月18日

2009年12月
« 11月   1月 »
 12345
6789101112
13141516171819
20212223242526
2728293031  

最近の投稿(電子情報)

アーカイブ

カテゴリー

高専機構とマイクロソフト包括協定締結

高専では、来年度からOSのライセンスを高専機構で一括取得という話がすすんでいたが、 下記のような、協力協定が結ばれたようだ。

これにより、Visual Studio などの開発系の Dream Spark が、 学生が自宅で無償でダウンロード利用が可能となるらしい。

教室のお引越し

今年度は校舎の改修と新型インフルエンザで、学校行事は特例ばかり。 しかし、ようやく本館の改修もひと段落で、電子情報棟の実験室を仮設教室にしていた 教室を、本来の教室に戻すお引越しの日

担任の教室も本館に移動だけど、移動先も他クラスが今日いっぱい使うし、 出て行く教室にも、他実験室に移動していたクラスが戻ってくる。 ということで、原則教室内のものは、すべて持ち帰り。 HRで持ち帰りと伝えていた割りに、机やロッカーに大量に「教科書」などを蓄えている人も多い。 んで、「今日全部持ち帰りはムリ!」という学生さんがチラホラ。 さて、放課後の移動はスムーズに終わるかな….

一気に雪景色

昨夜より福井県の平野部でも、シーズン最初の本格的な雪。 我が家では車の上に、3cm ほどの積雪であった。 学校につくと、早々に学生さんより「雪で電車が遅れてます」との連絡多数。 1限目の授業にも影響が出た様子。 シーズン最初の雪だし、しかたがないか….

0912180946_320x240.jpg

ハッシュ法

処理速度と関係して説明するアルゴリズムの最後?として、ハッシュ法を解説する。 例年どおりの『電話番号から名前を検索する』という例をもとに、 ハッシュ関数に電話番号末尾2桁をアドレスとする方法を説明する。 また、ハッシュ表サイズ100件に、40件を入れる場合ということで、 電話番号末尾2桁ではハッシュ衝突が発生する場合もあり、 その対応方法を説明。

ハッシュ関数の選び方としては、簡単に計算でき、異なるデータに対するハッシュ値の出現頻度が均一(一見デタラメな値)を選ぶことを説明する。 簡単な計算で、データの保存場所が一発で計算できることから、 一定時間でデータを参照できる。処理時間のオーダは、O(1)となることを説明する。

クローズドアドレス法

ハッシュ衝突が発生した場合の対応として、 「椅子取りゲームで椅子が先にとられている時に、1つ後ろの席に座る」 という対応を概念として説明し、簡単なコードを示す。 衝突してたら、空きが見つかるまで+1を繰り返し、途中でハッシュ表サイズに 達したときは先頭から…という方法を示す。

授業ではクローズハッシュと用語を説明したけれど、 正確にはクローズドハッシュ法(closed hash)であった…

チェイン法

クローズドアドレスハッシュ法は、データ件数がハッシュ表サイズに近づけば、 空椅子を何度も探す状態になり、処理時間がO(N)になってしまうし、データ件数が ハッシュ表サイズ(配列サイズ)を超えることができない。

このことから、同じハッシュ値を持つデータを、リスト構造で保存する方法をとる。 この方式は、オープンアドレスハッシュ法とかチェイン法とか呼ばれている。

文字データのハッシュ関数

電話番号から名前を調べる場合は、電話番号末尾は"100の余り"で簡単に計算できた。 しかし、名前から電話番号を検索したいといった場合は、前述の計算ができない。

文字列のデータからハッシュ値を求める場合、数値だけみればランダムに見えれば いいのだから、文字コードの合計といった方法がとられる。

int hash_func( char *str ) {
   int s = 0 ;
   for( int i = 0 ; str[i] != '¥0' ; i++ )
      s += str[i] ;
   return s % HASH_SIZE ;
}

文字列の順序違いで同じハッシュ値が求まるのが問題であれば、合計の計算部分を、 以下のようにする場合も多い。

s = ( s * (小さい素数) + str[ i ] ) % (大きい素数) ;