リスト構造から2分木と、高速の検索をする手法として説明したけど、 もっと高速なデータ検索として、ハッシュ法を示す。

メモリ無駄遣い

// 電話番号から名前を調べるために、電話番号自身を保存場所に使えばいい
// しかし、メモリが無駄遣い。
char phone[ 1000000 ][ 10 ] ;
strcpy( 272925 , "斉藤" ) ;

ハッシュ法(衝突無視の場合)

であれば、電話番号の末尾2桁なら、他の人とかぶらないのであれば、 以下の様にすれば、メモリの無駄遣いが防げる。 しかし、末尾2桁が偶然、他の人と同じ場合もありえる。こういう場合をハッシュ衝突と呼ぶ。

#define HASH_SIZE 100
int hash_func( int phone ) {   // ハッシュ関数
return phone % HASH_SIZE ;
}
char phone[ HASH_SIZE ][ 10 ] ;
strcpy( hash_func( 272925 ) , "斉藤" ) ;

クローズドハッシュ法

じゃあハッシュ衝突が発生したら、イス取りゲームの様に、使っていない次のイスに座ればいいじゃん…というのが、クローズドハッシュ法。 授業で説明したときは、うまく配列を定義していなかったので…

struct PhoneName {
int  phone ;       // 電話番号=0 なら「空き」と判定することにする。
char name[ 10 ] ;
} ;
struct PhoneName hash_table[ HASH_SIZE ] ; // hash_table[..].phone = 0 で初期化しておく
void entry( int tel , char name[] ) {
int index = hash_func( tel ) ;
// 空き席を探す                            // 説明の簡略化のため
while( hash_table[ index ].phone != 0 ) {  // 全部の席が埋まっていたときに
index = (index + 1) % HASH_SIZE ;       // 処理を抜ける対策を書かない...
}
// 空いていた席にデータを登録
hash_table[ index ].phone = tel ;
strcpy( hash_table[ index ].name , name ) ;
}
int find( int tel ) {
int index = hash_func( tel ) ;
for( ;; ) { // 説明を簡単にするため、無限ループ対策は書かない。
if ( hash_table[ index ].phone == 0 )
return -1 ;    // 空き席にたどりついた＝見つからない。
else if ( hash_table[ index ].phone == tel )
return index ; // 電話番号が一致したので見つかった
else
index = (index + 1) % HASH_SIZE ; // 次の席
}
}

EI5年との交流会に参加し、蕎麦うちを体験しました。

きしめん？(縦に太いか横に太いか…)

他の学生の麺が太く、「きしめん？」と突っ込みを入れていたけど、 最後に食べた時の感想では、私＆O先生の麺は、そばをシート状に伸ばした時の厚さが 分厚かったようで、なかなか食べ堪えのある太い麺になりました…

一部関係者用に https 経由で接続するページを公開しているが、 サイト証明も面倒でいわゆる「オレオレ証明」で運用中。 しかし、パッケージの更新をしたら、証明の有効期限が短くなった。

make-ssl-cert の証明期間の延長 をみて、有効期限を伸ばしていたけど、make-ssl-cert の更新で、"-days 365" が消えたみたい。 もっと伸ばすことも考えたけど、オレオレ証明への自分への警戒の意味もあり、 １年にしておこう。

OS の説明も終り、今週からはネットワーク物理層。 シリアル、パラレル、の説明と、Ethernet の説明。 例年説明していた CSMA/CD については、計算機システム１と２が １つになったこともあり、割愛。 WAN,LAN,10BASE/5,100BASE/T などの説明。

研究室の都合で授業にでれなかった学生さんが、 授業の音を録音用にパソコンを置いていたと、事後了承を伝えてきた。 どちらにしろ、授業に出ていても寝ている学生さんがいるのに、 そこまで熱心に録音してくれるなんて、逆に「嬉しい」と感じる。

歯みがきロボットでの技術デモ的にあえて、 画像処理によって動くロボットを作っているが、 ようやくそれなりに動き出す。

２足歩行でもなければ、ロボットは 「ガンタンクのように、キャタピラの方がかっこいい」と、 足周りは、キャタピラを使っていた。 しかし今日の走行実験では、 ラインマーカー用のガムテープとキャタピラの摩擦が大きく、 遅い速度ではトルク不足で方向転換がままならない。

動かなくなった状態をすこしそのままにしていたら、 基板のコゲ臭いが漂い出す。 動かないモータに長時間電流が流れ、モータドライバが加熱するのが原因。 昨年の車体も、最初はキャタピラだったけど、 動きが悪くタイヤにしたけど、 さすがに部品が焼けるのはヤバイので、 今年も「キャタピラ」に拘るのは諦め、タイヤに切替える。 タイヤのおかげでスムーズに動き、 ようやく大仏前まで移動できるようになった。 すっげー遅いけど…

簡単なルールの歯磨きロボコンのネタで講習会を開催しました。 時間と共に凝った技の機体が次々と作られました。

名前と誕生日といった複合データを、２分木で管理するプログラムを作成する演習を行う。 自信のある人は、整数の木を、ツリーっぽく表示する課題でも良い。 締め切りは中間テストまで。

無線LAN-WEPはもう危険

我が家でも無線LANは便利に使っているけど、無線だからこそ傍受するだけなら合法 FN 電波法では内容を他人に話すと違法。 /FN ってのもあり、最悪の場合、踏台にされて悪用される可能性もある。 だからこそ、無線LANは勝手に使われないように設定する必要がある。

勝手に使われないためには、暗号化が重要で、最近はWEPだと普通のパソコンで10秒で 解析できるため、しっかりとした暗号のWPA/WPA2が重要というネタ。

どうせ、まだWEPだよ！

といっておきながら、我が家の状況は WEP である。MACアドレスで接続制限している とはいえ、やっぱり危険。だけど Nintendo DS ×2のおかげで、やっぱり WEP。 最初は、使っていた Linux ノートで WEP より難しい暗号化だと、動かない場合が 多かったので、しかたがなかったけど、そろそろ考え頃か…

逆に、プライベートな接続と、他人の接続を分けたうえで、 積極的に他人に無線LAN接続を許可して、みんなでネットワークを使うと言うプロジェクトの FON も面白い。 みんなで共用が歌い文句のおかげで、ルータが2,000円というのもGood! 我が家の Nintendo DS 接続専用のルータとして購入してもいいかな… と思いきや、 パブリックAPではちょいと技がいるみたい。
最悪、中身のファームを書き換えて、 DD-WRT にもできるんだし…