電子情報工学科

双方向リストと、宣言的には同じなんだけど、データ検索用のリスト構造として、 2分木構造を説明する。

struct Tree {
int data ;
struct Tree*left ;  // 左の枝のポインタの先にはdataより小さいもの
struct Tree*right ; // 右の枝のポインタの先にはdataより大きいもの
} ;

導入部なので、データ生成の補助関数を説明し、直接2分木のデータを生成し、 そのデータに対する処理の例を記述し、解説する。 例として、count,min,sum,printなどのプログラムを再帰などの例を示しながら解説する。

再帰のオマケとして、末尾再帰呼び出しの処理は、ループに機械的に書き換え可能といった 補足も説明を行った。

どうも台風18号が接近しており、予想では福井も直撃しそう。 このため、明日10/8(木)AM7:00時点で、 「暴風警報」が発令されている場合には、 臨時休業とすることになった。 自分の担任クラスには、別途緊急連絡メールで連絡することになるだろう。

• 気象庁の台風情報

追記：10/8 AM7:00 予想通り『暴風警報』がでていて、台風にて休業となりました。 自宅を6:45に出るという学生さんには先に連絡を入れ、 7:00に緊急連絡メールで担任クラスに連絡する。 風も強いし、こちらも有給を出して、在宅勤務としておこう。

先日のロボットフェスティバルにて利用例も多かったオムニホイールを注文したらさっそく届いた。 んで、今年の専攻科１年の実験は、オムニホイールとArduino Nanoで自走するネタの予定。

EIのT先生に、双子のお子さんが生まれたとのことで、 出産祝いをプレゼントした。 子供1人の世話だけでも大変なのに、×2は大変だろうということで、 実用品ということで肌着を贈った。 男女で性格も違うのか、昼泣き＆夜泣きに別々で、大変とのお話しでした….

後期の授業予定として、構造体とグラフィックスを予定していることを説明し、授業開始。 まず最初は、構造体の説明ということで、 FORTRANの後に、商用計算のCOBOLにてデータの構造化が行われ、 ALGOLあたりで命令の「{,}」によるブロックによる、手続きの構造化により、 構造化プログラミングが一般化していった経緯を説明する。 さらに、初心者にみられる手続き優先記述も、大きなプログラムになるとデータ優先記述に 変化していき、最終的にはデータ構造に命令というスタイルが分かりやすく、 データを擬人化してとらえ直感的といったことから、オブジェクト指向プログラミングが 発生したことを説明する。このあとC++,Javaといった言語が開発されていったことを述べる。

構造体

構造体を使わないデータ記述での問題点を解説。 この中で、マジックナンバーが有害であること、同じような構造が複数必要な時の問題点を 述べ、構造体の文法を解説する。

• 構造体の説明の配布資料

この中で、構造体の定義と宣言、プログラム中の要素の参照、構造体の初期化、構造体の入れ子構造などを説明する。 また、タグ名の説明にて、変数名のルールが '[a-zA-z_][a-zA-Z0-9_]*' であることを解説する。

専攻科の計算機システムの講義の初回。 ということでシラバスを配布し、ガイダンスを行う。 本来は生産システム専攻向けだけど、環境システムの学生さんも7割がた受講するので、 細かい内容には突っ込めない部分がある。

計算機の歴史

計算機システムでの前半の自分の担当では、OSやネットワークといったソフトウェアの視点で、 技術解説をすることを宣言し、まずは歴史の紹介。 WWII以前のネタでは、バベッジの計算機あたりの写真を紹介しながら、 ENIAC,EDSACの写真を交えながら、第1世代:真空管、第2世代:半導体、第3世代:IC、3.5世代LSI…と説明をしていく。

途中からは、身近なパソコンということで、Intel 4004あたりのネタから、 8008,Z80の8ビットの時代を説明する。 んで、この頃からビルゲイツやジョブズ、ウォズニアックなどの写真を見せながら、 TinyBASIC,MS-DOS,Windowsと発展していくMicrosoft社と、Apple1あたりのApple社の発展を 簡単に説明する。 特に、8bit-80系から16bit-8086への変遷で命令互換性を重要視したIntelの成功、 アーキテクチャの外部非公開によるApple(Macintosh)の衰退、および IBM/PCのアーキテクチャ公開による3rdパーティ参入による低価格化と発展が注目点として紹介する。

写真は、改めて調べてみると、スチームパンク的な視点でデザインが、 かっこよく思えたので…

今日は、卒研の中間発表のレジメ提出の締切日。 概念の基礎となるところの説明は、参考資料からコピペすればいいから、 それなりにちゃんと書けているけど、研究の目的だったり、自分で作る部分の 説明で、肝心な部分が抜けまくり。 それに資料がたったA4×1ページの制限なので、 基礎説明で「資料完成!!」って勘違いしているのかな… ということで、なにが抜けていてどう分かりにくいのかを説明しながら、 添削攻撃!!

創造工学演習とプロコン参加に向けて作品を作っていたチームのために購入した、ミニプラネタリウムが届いた。プロコンは本戦参加はできなかったけど、来年やふくいソフトコンペに向けて作成継続中。電動プラネタリウムを、Wiiなどのリモコンで制御するテーマで取り組んでいるところ…

初めて担当するデータベースの授業で、少し不安要素もあるけど、 まず最初にシラバス配布とデータベースシステムの重要性を解説する。 以下の話は、DBエンジンを使う利点の説明でもあり、 一方でDBの内部スキーマでどういう技術が必要となるかの説明でもある。 説明の中では、データベースに要求されるACID特性も交えている。

データベースエンジンを使わないなら

データベースの重要性を理解してもらうために、データベースエンジンを使わない場合は、 どういう方法を使っていたのかを解説。使用教科書には、データベースを使わない場合の直接ファイルを触る話が実例を交えて書いてないので、その辺をちょっぴり具体的に書いてみる。

データをまるごと読み込み

4年の情報構造論であれば、目的のデータを探す処理といっても、 ポインタや処理速度のオーダなどの理解を 深めるためにも、全データを最初に目的のデータ構造で一括読み込みをして、 リスト構造なり2分木なりハッシュという演習をしていた。 しかし、こういう方法は

• データ件数が数万件を越えてきたら、主記憶がデータで埋め尽くされ、メモリが不足すれば仮想記憶が使われ性能低下といった問題や、
• readonly でなければ、 途中でシステムダウンでデータ消失といった不安がつきまとう(耐久性:D)

といった問題がつきまとう。

シーケンシャルファイル

大量のデータを主記憶にすべて読み出しておくことは、 主記憶の浪費や、永続性記憶資源でないという点で、 問題がある。 であれば、必要に応じて読み出せばいいけど、 C言語初心者の fscanf() しか理解していなければ、 先頭から１件１件必要に応じて順次ファイル(シーケンシャルファイル)として 読み出すことになる。ただし、O(N)の時間がかかり、それこそン万件であれば、非現実的。

struct Data {
   char  name[ 10 ] ;
   int   age ;
} ;
struct Data data ;
while( ... ) {
   if ( fscanf( fp , "%s %d" ,
                     data.name , &data.age ) == 2 ) {
      // 読み込んだデータの処理
   }
}

ランダムアクセスファイル

先頭からアクセスを繰り返す時間が非現実的なのであれば、 配列のように、N番目のデータを一定時間で読み出せればいい。 こういう場合、データが固定長であれば、データサイズ×データ件数が、 そのまま並んでいるファイルをつくって、N件目を読み出したければ、 ファイル先頭から、fseek()などで先頭から、データサイズ×N[byte]目から、 データサイズだけ読み込めばいい。

// N番目アクセスを強調するために逆順アクセス
FILE * fp ;
fp = fopen( "filename.dat" , "rb" ) ;  // バイナリモードで開くこと
:
for( int n = SIZE - 1 ; n >= 0 ; n-- ) {
   struct Data data ;
   if ( fseek( fp , sizeof( Data ) * n , SEEK_SET ) == 0
        && fread( &data , sizeof( Data ) , 1 , fp ) == 1 ) {
      printf( "%s %d\n" , data.name , data.age ) ;
   }
}

fseek( fp , offset , SEEK_SET ) は、ファイル先頭から offset[byte] に、 読み書きの位置を移動させる関数。
fread( ポインタ , size , n , fp ) は、ポインタの先に、size[byte]のデータをn件分読み込む関数。 同様に書き込み版は、fwrite( … ) がある。

しかしながら、この方法は１件あたりのデータ長が一定だからできる方法。 また、途中でデータに追加や削除が発生したら、そのデータ領域を後ろに 移動させたり、前に詰めるといった処理をすることは、データ件数が巨大であれば、 非現実的。一般的には、追加ならファイル末尾に追加するなり、削除であれば 空き領域を詰めることはせずに、消えた無効データという目印だけつけておき、 利用者の少ない時間帯に、無効データの目印の場所を切り詰める処理を実行 することになるであろう。(トランザクション処理の一例) それに、N番目アクセスに fseek() + fread/fwrite のプログラムを書くのは、面倒だし、 複数の人が読み書きすると、一貫性:C , 隔離性:I のことを考え排他制御が必要。 また、書き込み処理の最中に、アプリケーションやOSなどが落ちた場合、 どこまでデータが書き込まれているのかという問題は、原子性:A,一貫性:C の 点でDBを使わない時には、極めて面倒な話となる。

ファイルシステムをデータベースの様に扱う

特定のキーで、データベースを検索する必要があって、削除データの切り詰めや、 可変長データのデータの取り扱いが必要であれば、ファイルシステムを データベースのように扱うプログラムを書く場合も多い。 例えば、名前から個人情報を探すプログラムであれば、名前自身をファイル名に して１件１ファイルで保存すれば、データ削除はファイル消去=unlink() になるし、 １件１ファイルであれば、データの追加で後続データを 後ろに移動させるといった手間もない。 可変長のデータであっても問題ない。

char fname[ 1024 ] ;
char* filename( char* s ) {
   sprintf( fname , "DataDirectory/%s.txt" , s ) ;
   return fname ;
}
void data_write( char* name , int age ) {
   FILE* fp ;
   if ( (fp = fopen( filename( name ) , "wt" )) != NULL ) {
        fprintf( fp , "%s\n%d\n" , name , age ) ;
      fclose( fp ) ;
   }
}
int data_read( char* name ) {
   FILE* fp ;
   char n[ 100 ] ; int age = -1 ;
   if ( (fp = fopen( filename( name ) , "rt" )) != NULL ) {
        && fscanf( fp , "%s%d" , n , &age ) == 2 )
      return age ;
   } else {
      return -1 ;
   }
}

こういった方法は、アプリケーションプログラムが無くても、OSの命令で 簡単にデータを作ったり消したりができるため、データの取り扱いが楽なのが特徴。 しかしながら、この方法には、以下のような問題がある。

• nameに"../../../"といった文字が含まれていれば、目的ディレクトリ以外を触れるかも…
• また、一般的なシステムでは、1つのディレクトリ内に保存できるファイル数には、上限があり、1万件以上は書き込めないかもしれない。
• それにディレクトリ内のファイル情報は、配列的な単純テーブルだったり、単純線形リストだったりするため、ファイル数が巨大になれば、データ検索速度はO(N)で遅くなる。最近は、こういう問題に対応するために、ディレクトリ内のファイルをBTreeなどで保存するファイルシステムも開発されてきている。

RDBでない、古くから使われているDB

データベースで古くから使われているデータベースの１例は、 "Berkeley DB"が有名。 SQLなどのデータ操作言語を使うことなく、関数呼び出しで追加検索などを行う。 トランザクションや排他制御などが実装されているので、単純なデータベースであれば、 以前は、Berkeley DB を使うことが多かった。