高等学校産業教育研修講座の協力依頼

福井県教育研究所の方が来校され 「PIC等を用いた組み込み系実験を、工業高校にて実施するための教員向け講習会」の 協力の相談を受ける。今年はマルツ電波の「メイク館」の方に協力してもらい、PIC 制御の 講習会を実施していたとのお話。 次年度で講師の都合も悪そうなのでということで、お呼びがかかった…。 夏休み後半びっしり2日コースの講習会らしい。 PIC でなく、3年実験で実績のある H8/3664 になるとは思うが、協力は可能であろう。

先週のクローズハッシュの説明に続き、文字データを key とする時のハッシュ関数と、 衝突したデータをリスト構造で覚えるチェイン法を説明する。 チェイン法では、処理速度が途中まで O(1) で、表サイズを越えるとO(N)になるという 説明も行う。

緊急連絡システムで事案のメールが送られてきた。 「 住吉町 で不審者うんたらかんたら〜」と書かれている。 町名地理の苦手な私は、今年追加の新機能で、だいたい武生駅の近くみたいと確認。 すると訂正で「先程の事案は 鯖江市住吉町 で、越前市ではありません…」 とのメールが送られてきた。

ちょいとまて、新機能の地図表示機能は、 「本文から、越前市の学校配信の記事なら、越前市○○町と判断して、 越前市に該当町名がなければ「鯖江市○○町」と判断するという方式。
# バグ出しチェックのようなメールとばさねぇでけれ…
おかげで、どちらも、越前市住吉町の地図が表示されました….
# これぐれーの町名誤認ぐらいは許してね…

プログラマーの意地…

うちの奥さんが一番突っ込み入れそうなので、処理を追加。 越前市△△町、鯖江市△△町と明記してある場合の処理を最初に入れる。でも、 「 鯖江市住吉町 でなく 越前市住吉町 でした」と２つ書かれると、誤爆する。許せ！…

地図機能の利用者意外と多いな…

ついでに地図機能の利用者の利用状況をチェック。

≪access.logに約４日分の履歴の中で、地図機能を使った人をカウント≫
# grep gmap.php access.log | wc -l
1081

お、利用者予想外に多いじゃん…と思ったが、

≪今日限定で地図機能を使った人をカウント≫
# grep gmap.php access.log | grep 20/Nov/ | wc -l
949

うーむ、もしかして町名修正のメールが飛んで「面白がって地図チェックした人が大多数…」？

ちなみに webalizer の集計結果を見ると、 受信確認を行った人の3割ほどが、地図を確認している。 やっぱり自分の住んでいる市といっても、町名しらね…というのは多いよな…

ネットワークの基礎の説明ということで、 ネットワークトポロジ(バス接続、リング接続、スター接続、ツリー接続、ネット接続)を紹介し、 Ethernet のバス型接続の特徴である CSMA/CD の通信の考え方を説明する。 その後、IPプロトコルということで、サブネット、ルータ、といった用語と、 IPプロトコルのパケット中継メカニズムや、グローバルアドレス／プライベートアドレスを 説明する。

構造体を使った演習も終わったので、応用ネタ。 最初に、ビットフィールドの説明。 生年月日のデータをメモリに効率よく格納する方法として、 2進数演算により複数の数値を1つの整数型に代入する方法を説明する。 2進数計算の面倒なところを紹介した後、ビットフィールドでの文法を説明する。

ビットフィールドの例

struct YMD {
int  year ;   // 0..2100年程度なら 2^12 = 4096 より 12bit で表現可能
int  month ;  // 1..12 なので      2^4 = 16 より     4bit で表現可能
int  day ;    // 1..31 なので      2^5 = 32 より     5bit で表現可能
} ;              // 本来なら、21bitで十分だけど、4byte×3=12byte(96bit)
// 整数に21bitを押し込む
//   YYYYYYYYYYYYMMMMDDDDD ←2進数
int ymd = (1965 ≪ 9) | (2 ≪ 5) | 7 ; // 1965年 2月 7日のつもり
// ymd から年月日を取り出す
int year  = ymd ≫ 9 ;           //   YYYYYYYYYYYYMMMMDDDDD ymd
//            YYYYYYYYYYYY (ymd ≫ 9)
int month = (ymd ≫ 5) & 0xF ;   //   YYYYYYYYYYYYMMMMDDDDD ymd
//        YYYYYYYYYYYYMMMM ymd ≫ 5
//      & 0000000000001111 ... & 0xF
//        000000000000MMMM
int day   = ymd & 0x1F ;         //   YYYYYYYYYYYYMMMMDDDDD ymd
// & 000000000000000011111 ... & 0x1F
//   0000000000000000DDDDD
// ymd の月を「3月」に修正
ymd = (ymd & ~(0xF ≪ 5)) | (3 ≪ 5) ;
//   000000000000111100000 0xF ≪ 5
//   111111111111000011111 ~(0xF ≪ 5)
//   YYYYYYYYYYYYMMMMDDDDD ymd
//   111111111111000011111 ~(0xF ≪ 5)
//   YYYYYYYYYYYY0000DDDDD ymd & ~(0xF ≪ 5)
// or            001100000 (3 ≪ 5)
// こんな大変な2進数計算じゃ、書き間違いするって...
// ビットフィールドを使うと、
struct YMD {
unsigned int year  : 12 ;
unsigned int month :  4 ;
unsigned int day   :  5 ;
} ;
struct YMD saitoh = { 1965 , 2 , 7 } ;
printf( "%d/%d/%d\n" , saitoh.year , saitoh.month , saitoh.day ) ; // 1965/2/7
saitoh.month = 3 ;
printf( "%d/%d/%d\n" , saitoh.year , saitoh.month , saitoh.day ) ; // 1965/3/7

ワード境界

ビットフィールドで、メモリを効率よく使う話とは反対の話として、ワード境界について話す。 最近のコンピュータであれば、メモリとのデータのやりとりは32bitなり64bitの一括で行う。 ワード境界とは、この一括してやりとりするデータ単位で、次のデータ単位との境界。 (32ビットでメモリアクセスするコンピュータであれば、(4*N-1)バイトと4*Nバイトの境界) この際に、構造体の1データがワード境界をまたがって配置されていると、1ワードのデータ 読み出しでも2回のメモリアクセスが必要となり、速度が低下する。
このためC言語では通常、ワード境界をまたぐような要素の配置はせずに、 使わないメモリを混入させてくれる。

struct A {      // C言語では、通常packしない
char   n[3] ; // 3byte
int    x ;    // 4byte
double y ;    // 8byte
} ;
struct A a[3] ;
| packした時  | packしない時 |
----------+-------------+--------------+--------------------------------------
memory 00 | n0 n0 n0 x0 | n0 n0 n0 --  | ★packした時
memory 04 | x0 x0 x0 y0 | x0 x0 x0 x0  |  printf( "%d" , sizeof( struct A ) ) ;
memory 08 | y0 y0 y0 y0 | y0 y0 y0 y0  |   => 15
memory 12 | y0 y0 y0 n1 | y0 y0 y0 y0  |
memory 16 | n1 n1 x1 x1 | n1 n1 n1 --  | ★packしない時
memory 20 | x1 x1 y1 y1 | x1 x1 x1 x1  |  printf( "%d" , sizeof( struct A ) ) ;
memory 24 | y1 y1 y1 y1 | y1 y1 y1 y1  |   => 16
memory 28 | y1 y1 n2 n2 | y1 y1 y1 y1  |
memory 32 | n2 x2 x2 x2 | n2 n2 n2 --  |
memory 36 | x2 y2 y2 y2 | x2 x2 x2 x2  |
memory 40 | y2 y2 y2 y2 | y2 y2 y2 y2  |
memory 44 | y2          | y2 y2 y2 y2  |
packしてある構造体だと、a[0].x を読み出す時に、
memory 00 と memory 04 の2回メモリアクセスが発生する。

参考資料：

• データ型のアラインメントとは何か

共用体

これまた、メモリを効率よく使うための文法。 データを保存したいけど、文字データ、整数データ、実数データのいずれかで覚えるという場合、

struct STRorINTorREAL {     // printf( "%d" , sizeof( struct STRorINTorREAL ) ) ;
char   string[ 8 ] ;     //  8+4+8 => 20byte
int    integer ;
double real ;
} ;

これでは、どれか1つのデータしか覚えないのなら、メモリがもったいない。 こういう時には、共用体を使う。

union STRorINTorREAL {      // printf( "%d" , sizeof( struct STRorINTorREAL ) ) ;
char   string[ 8 ] ;     // max(8,4,8) => 8byte
int    integer ;
double real ;
} ;
union STRorINTorREAL x ;
strcpy( x.string , "saitoh" ) ;
x.integer = 1965 ;
x.real = 12.3456 ;

しかし、共用体の中に何が入っているのか分からないと、使えないので、一般的には…

struct STRorINTorREAL {
int  type ;              // 本当は列挙型を使いたいけど説明は来週の予定...
union {                  // 無名共用体
char   string[ 8 ] ;
int    integer ;
double real ;
} ;
} ;
void set_integer( struct STRorINTorREAL* p , int x ) {
p->type = 1 ;
p->integer = x ;
}
void set_real( struct STRorINTorREAL* p , double x ) {
p->type = 2 ;
p->real = x ;
}
void set_string( struct STRorINTorREAL* p , char x[] ) {
p->type = 3 ;
strcpy( p->string , x ) ;
}
void print( struct STRorINTorREAL* p ) {
switch( p->type ) {
case 1 : printf( "%d\n" , p->integer ) ; break ;
case 2 : printf( "%f\n" , p->real ) ;    break ;
case 3 : printf( "%s\n" , p->string ) ;  break ;
}
}
void main() {
struct STRorINTorREAL a[ 3 ] ;
set_integer( &a[0] , 12345 ) ;
set_real   ( &a[1] , 12.345 ) ;
set_string ( &a[2] , "abcde" ) ;
for( int i = 0 ; i < 3 ; i++ )
print( &a[i] ) ;              // 12345 , 12.345 , abcde が表示。
}

おまけ(C++やオブジェクト指向を個人的に勉強している人へ…)

配列に違う型のデータでも入れられるのが共用体を使う理由。 だけど C++ であれば、仮想関数を使ってもっとスマートにかける。

#include
#include
class Object {  // 仮想基底クラス
public:
virtual void print() = 0 ; // "=0"の意味：仮想基底クラスでは何もしない
} ;
class Integer : public Object {
public:
int  integer ;
public:
Integer( int x ) { integer = x ; }
virtual void print() { printf( "%d\n" , integer ) ; }
} ;
class Real : public Object {
public:
double real ;
public:
Real( double x ) { real = x ; }
virtual void print() { printf( "%f\n" , real ) ; }
} ;
class String : public Object {
public:
char  string[ 8 ] ;
public:
String( char x[8] ) { strcpy( string , x ) ; }
virtual void print() { printf( "%s\n" , string ) ; }
} ;
void main() {
Object *a[ 3 ] ;  // ポインタじゃないと都合が悪いので...
// 配列a[3]に、整数、実数、文字列の違うデータを入れる
a[ 0 ] = new Integer( 12345 ) ;
a[ 1 ] = new Real( 12.345 ) ;
a[ 2 ] = new String( "abcde" ) ;
// 異なるデータがうまく表示できる
for( int i = 0 ; i < 3 ; i++ )
a[ i ]->print() ;
}

リスト構造から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" が消えたみたい。 もっと伸ばすことも考えたけど、オレオレ証明への自分への警戒の意味もあり、 １年にしておこう。