1/31(Mon)現在、昨日からの積雪で、JR・高速道路もあんまり動いていない様子。 今日は7:00頃に学生さんは雪で休業ということが決まりました。 自宅にて、自分の車の周りでラッセルしながら雪かき中、 部屋に戻り緊急連絡網でお休みを担任クラスに連絡で、色々と疲れた….

今日は、豊橋技術科学大学の先生が、学部などの再編成などもあって、 そのPRも兼ねて来校。説明などをうけた。 私自身、豊橋技科大の出身なので、母校の変革といういみで興味深かった。

学系が、今までは機械・生産・電気電子・情報・物質・建設・知識情報・エコロジー であったが、再編成をうけて、次年度から 「機械・電気電子情報・情報知能・環境生命・建築都市システム」という５学系に なる。でもこれは、丁度うちの高専の５学科とまるっきり重なるので、 分かりやすくなったともいえる。

特に、電子情報工学科からの関連がある、２学系については、内部の講座としても 以下のようになったらしい。

• 電気電子情報工学科
  • 材料エレクトロニクス
  • 機能電気システム
  • 集積電子システム
  • 情報通信システム
• 情報知能工学課程／専攻
  • 情報工学(基礎理論・計算機アーキテクチャ・ソフト・並列分散・組み込み)
  • 知能情報システム(マルチメディア情報・様々学問での情報技術応用)

これらの再編成に伴い、H24年度からの３年次編入生も60名の定員増となる。

　電気電子情報　推薦40＋学力40
　情報知能　　　推薦40＋学力40
　成績優秀な合格者の入学料を全額免除(100人=1/3程度?)
　多彩な教育プログラム
　　社会環境即応型リーダー技術者育成プラン
　　　MOT指向生産システム技術科学教育によるリーダー人材の養成
　　テーラーメイドバトンゾーン教育プログラム

情報構造論も先週でだいたい説明を終えたので、 簡単に全体を総括して演習。

演習テーマは、「ハッシュ法もしくはグラフのプログラム作成」とする。 ハッシュ法は、チェイン法にて実装したプログラムで、ハッシュ関数の選択やオープンアドレス法との比較が望ましい。 グラフでの演習では、無向グラフ・有向グラフでのプログラムとして、 2つのノードが、ノード経由で移動可能かを判定するプログラムとする。

先週のB木の説明を受け、実際のデータベースで利用されているB+木について説明を行う。 また、インデックスファイルでの高速検索を行うためのハッシュ法なども説明する。

単純なB木では、全データ対象のシーケンシャル処理などが面倒になるので、 B木に相当する部分と、シーケンシャルアクセスのための"シーケンシャルセット"で データを扱う。

このようにすることで、全データへの処理はシーケンスセットで横断し、 個別のキーで検索を行う場合は、B木のインデックスで目的データを見つける。

また、このようなB木やB+木では、データを消す場合、各ノード内のデータ数が半分を切らない間は、各ノード内でデータを消去する(あるいは使わない目印をつけるだけ)。 データ数が半分を切ると、次のノードとくっつけるなどの処理が行われる。

このように、B+木を用いることで、特定のデータの検索・全データ参照が容易になる。 実際のデータベースでは、データの記録順序とは別のキーでの検索も必要となる。 この場合は、別途インデックスファイルを作ることになる。 このインデックスファイルでは、ハッシュ法が用いられる場合もある。 ハッシュ法では、データよりハッシュ関数で計算したハッシュ値を、データの保存場所に利用する。ただし、別データでも同じハッシュ値となる「ハッシュ衝突」が発生するため、 オープンアドレス法や、チェイン法が使われる。

卒研にて「Google App Engine を使って緊急連絡システムを作ると…」 というネタをやっていて、その運用面での有用性の論証ということで、 現在の緊急連絡システムと比較しようという話になった。 そこで、メールの送信量を知りたいとの話。 ということで、簡単にプログラムを書いて、カウントしてみた。

発信されたメールの件数:9286件
そのメールを受け取った延べ人数:993302件
取り扱い組織数: 88組織
管理しているメールユーザ数: 12632件
(2006/01月より2011/01/25現在)
# ただし送信確認のテストメールや、受信フィルタで
# 実際には保護者に届かなかった人数(メール数)も含む。

運用が広がった段階で、約1万のメールアドレスを超えていて、我ながらすげーと思っていた。 んで、個人に送ったメールが、のべ約100万通か…すげー多いな…

C++の再学習にて、「C++クックブック」を見ているんだが、ライブラリにてboostの事例も多い。 んで、調べていると、昨日書いていたc++0xを使ったvectorの初期化だけど、 boost だと、boost::assign::list_of なんてぇ～のを使うと、c++0xを使わなくても書けちゃう。

#include <iostream>
#include <vector>
#include <boost/assign/list_of.hpp>
using namespace std ;
int main() {
// 初期化リストの要素が() で囲まれているのがポイント、
// operator()() の演算子オーバーライドで実装しているみたい。
vector<int> v = boost::assign::list_of (1) (2) (3) ;
for( vector<int>::iterator it = v.begin() ;
it != v.end() ;
it++ ) {
cout << *it << endl ;
}
}

変態チックだな…当然、bitset<8>でも動くぜ…変態…

昨日は、c++0xのラムダ計算を試した(gcc4.5入れてなくって、コンパイルでけんかったけど) けど、boost にもラムダ計算がある…。 g++側に依存しないという意味では、boost の方が便利だけど、ここまでいくとなぁ… 参考サイト見つけたけど、さらに変態度が増している。

#include <iostream>
#include <vector>
#include <boost/assign/list_of.hpp>
#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
int sum = 0 ;
int main() {
using namespace std ;
using namespace boost::lambda ;
vector< int > v = boost::assign::list_of ( 1 ) ( 2 ) ( 3 ) ;
for_each( v.begin() , v.end() , sum += _1 ) ;
cout << sum << endl ;
}

追記：んでも、使う前にBoostのインストール。Mac と Debian にもいれてみた。

(( Mac OS X ))
# fink list | grep boost
# fink install boost1.35.systempython
## boost-jam,boost1.35.systempython,
## boost1.35.systempython-shlibs がインストールされる。
(( Debian GNU/Linux ))
# aptitude search boost
# aptitude install boost-all-dev
## debianでは様々なライブラリが細かくパッケージ化されている。
## 何を使うか解らないので、ともかく全部いれてみた。
## 変態な、boost/lambda も入っちゃう。

グラフィックスの基本ということで、 座標の拡大縮小・回転・移動などの説明を行い、 説明プリントを見ながら、値渡し・ポインタ渡し・配列渡しの再確認。

配布資料を見ながら、座標の拡大縮小・回転・移動などの概念を説明し、 行列表記に慣れてもらう。線対称・点対称・拡大・移動・回転は、資料参照。 最終的に、すべての２次元の座標変換は、以下のような行列積と和で表せる。

特に、その結果を、以下のように扱うものはアフィン変換と呼ばれる。

(行列式の画像などは、ここを引用)

この他に、グラフィックス処理では、大量の計算を伴い、計算速度の高速化への理解も 重要なので、最適化について紹介する。 基本的な、不変値計算のループ前移動や、整数演算化による高速化、最近CPUでの積和演算命令といったものをいくつか紹介する。

前述のグラフのプログラムで、隣接行列を"vector< bitset<8> > a ;"で宣言すると、 その初期化において、"a.push_back( bitset<8>( … ) ;" を使って、 手作業で要素を初期化していた。 文法的にも、ややこしそうなものをクラスに渡すことになるし、しかたがないと思っていた。 でも、改めてC++の解説を読んでいたら、C++0xであれば、使えそうな文法が…

// bitsetのベクトル
vector< bitset<N> > a = {
bitset<N>( 0x02 ) ,
bitset<N>( 0x0D ) ,
bitset<N>( 0x42 ) ,
bitset<N>( 0x12 ) ,
bitset<N>( 0x28 ) ,
bitset<N>( 0xD0 ) ,
bitset<N>( 0xA4 ) ,
bitset<N>( 0x60 ) ,
} ;

ただし、この機能は、g++4.4.5であれば、"error: in C++98 'a' must be initialized…" とエラーが 表示されてしまう。コンパイルするときには、次のように書くみたい。

$ g++ -std=c++0x graph-bitset.cxx

C++0xを読んでいたら、LISP屋の飛びつくラムダ式なんてのが書いてあったので、 思わず試さずにはいられなかった。

vector<int> a = {
1,2,3,4,5
} ;
int main() {
int sum = 0 ;
for_each( a.begin() ,
a.end() ,
[&sum]( int x ) {
sum += x ;
} ) ;
return 0 ;
}

試してみたけど、動かんじゃん….でも調べてみると、g++4.5以降とな…