マウスやタッチパネル操作の分析に関係したテーマで 特別研究をしている学生さんの、修了認定試験の仮想問題のネタで、 雑談。 こんな問題出るかもよ…ということで、 「操作対象が小さくなると、作業時間にどう影響でるか？」という質問をしてみた。

こんな話をするのは、高専就職前の職場ではIE課という所で、 作業効率化のためのコンピュータ導入ネタをやっていた。 ただ、本来の生産管理(IE:Industrial Engineering)では、 行程作業者の作業のムダの分析も重要な仕事。 んで、その課の勉強会では、作業因子法(Work Factor plan)という分析手法を 習っていた。 んで今回のタッチパネル操作の研究テーマだと、 ターゲットまでの距離や大きさや注意の必要性を考えれば、 Work Factor法でパネル操作に要する標準時間が求められるはず…。 というアドバイスをしてあげたかったんだけど、 IE仕事をしてたのは、ほぼ20年前の話。 Work Factor法という単語にたどり着くのに、ずいぶんとググらなければいけなかった。

データ構造に関係するアルゴリズム説明が一通り終わったので、 ここからは動的メモリの管理方法の解説。 まずは最初に、参照カウンタ法とガベージコレクタについて説明する。

参照カウンタ法

データにポインタによって共有が発生すると、 不要になったデータの廃棄が問題になるという例を示す。

/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = q ;
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
list_free( p->next ) ;
free( p ) ;
}
}
void main() {
struct List* a = 適当なリスト生成 ;
struct List* b = 適当なリスト生成 ;
struct List* c = set_or( a , b ) ;
list_free( c ) ;
list_free( b ) ;  // 実はリストは前処理で捨てられている
list_free( a ) ;
}

こういったプログラムであれば、リストを捨てる処理が気軽に書けなくなってしまう。 根本の原因は、データ間で共有されている部分が発生しているため。 この解決方法の１つが参照カウンタ法。

/* 参照カウンタ法を使うリスト */
struct List {
int refc ; //参照カウンタ。生成時は1で初期化
int data ;
struct List* next ;
} ;
/* コピー(共有?)が発生する時にはこれを使え! */
struct List* share( struct List* p ) {
if ( p != NULL )
p->refc ++ ;
}
/* 共有の発生するリストによる和集合 */
struct List* set_or( struct List* p , struct List* q ) {
struct List* n = share( q ) ; // カウントアップ
for( ; p != NULL ; p = p->next ) {
if ( ! find( q , p->data ) )
n = cons( p->data , n ) ;
}
return n ;
}
/* リストを全部捨てる関数 */
void list_free( struct List* p ) {
if ( p != NULL ) {
p->refc-- ; // カウントダウン
if ( p->refc == 0 ) {
list_free( p->next ) ;
free( p ) ;
}
}
}

このような参照カウンタは、ハードディスクでのファイル管理でも使われている。 ハードディスクでは、障害時に参照カウンタ管理が異常になるとゴミデータが残るようになる。 このため障害復旧時には、全HDD領域の参照カウンタの異常チェックが重要。 しかしながら、復旧処理に時間がかかるようになるので、ジャーナリングという方法がとられる。

一方、参照カウンタ法の問題点として、循環リストのようなデータの場合、カウンタが0にならないけど、 他のデータから孤立したデータが発生してしまう。

ガベージコレクタ

参照カウンタ法は単純だけど、万能ではないため、不要となったデータ領域の回収は、 どうするのが理想的なのか？ ひとつの解決方法はガベージコレクタ。 ガベージコレクタ(Garbage Collector)では、不要となったデータ領域はあえて回収しない。 (free()関数は使わない) しかしこのままではメモリ空間がゴミだらけになってしまう。 そこで、メモリ空間がゴミであふれたら、ゴミ回収(Garbage Collect)を行う。 マーク＆スイープ法では、ゴミであふれたら使用中のメモリ空間をたどりながら、 使用中目印をつける(marking)。　その後、目印のついていない領域は回収(sweep)。

ただし、GCが起動すると、他の処理ができなくなるので、処理の中断が発生する。 対話的なシステムでは、GCは処理の遅延になるので、嫌われていた。 最近のガベージコレクタでは、参照カウンタ法も併用した方式がとられるため、 早い段階で不要な領域の回収が可能となり、処理の遅延が問題になることはなくなってきた。

例年より規模を縮小でしたが、ホストファミリーを交え楽しく歓談できました。

データベースの設計の続きとして、 最初に先週説明が不完全であったボトムアップ設計の説明を追加する。 特にボトムアップ設計で、項目をレベルに分類し、データグループを作成・分離・統合 といった作業を説明する。

データベースの論理設計では、実際に出来上がったER図などから関係モデルに変換される。 しかし、実際には業務に応じて、処理のタイミング・処理の量・トラヒック、処理の要求条件 などを勘案しながら問題点を整理することを説明する。 テーブルの統合の検討として、複数のリレーションの直積(結合)をとりながらの 処理は、時間のかかる処理であったりするため、業務によっては統合が必要となったりする。 また、テーブルの分解の検討として、 同じリレーションへの処理の集中、特に更新作業が頻発する場合は、排他処理などが 発生し、データロックなどで処理が停滞する場合もあるため、必要に応じてテーブルの分解が 必要になるかもしれない。 インデックス情報の検討として、 参照の高速化ではインデックスファイルを用いたりする。しかしながら更新作業によっては、 インデックスファイルの更新の負荷が高まる場合もある。

データベースの物理設計では、実際にハードディスクの容量見積もり、メモリの容量見積もり、 ログファイルの見積もりなどが必要となる。 特にハードディスクの容量見積もりでは、PCTFREE(可変長データの増加による実体の移動を減らすためのデータ間のギャップ)や、PCTUSED(ページ内に空きが発生した時に他のレコードを収容するか？)に伴う、空き領域も勘案すべきである。

緊急連絡システムの配信されるメールの内容の相関を分析したくって、準備。文章比較を自分で書くと大変そうだし、便利なツールを Perl でできないかと探す。

文章をMecabで単語分割して、diff で差分を確認して、差分の行の量に応じてスコアをつければ簡単と思われる。かといって、テキストを子プロセスで MeCab や diff に渡すのは、中間ファイルが大量そうだし避けたい。 Perlモジュールを探すけど、やっぱり節操のない Perl だと、すべてが揃う…(^_^;

• Text::Diff – テキストの差分 / Perlモジュール徹底解説
• Perlメモ / MeCab モジュール

# aptitude search text-diff | grep perl
p   libtext-diff-perl  - Perl module to find differences in files a
# aptitude install libtext-diff-perl
# aptitude search mecab | gerp perl
p   libmecab-perl      - Perl 用 mecab バインディング
# aptitude install mecab libmecab-perl

簡単な実験プログラム。

#!/usr/bin/perl
use MeCab ;
use Algorithm::Diff 'sdiff' ;
my $a = "This is a pen.晴れた！"
."今日の天気は晴れています。"
."明日は雪がふるかな？"
."でもたぶん雨でしょう。" ;
my $b = "That is a pencil."
."今日の天気はどんよりと晴れてるよー。"
."明日はアラレがふるかな？"
."でもたぶん雪でしょう。" ;
sub mecab_split { # MeCabで単語分割
my $str = shift ;
my $mecab = new MeCab::Tagger( "" ) ; # コマンドライン引数
return map  { my @z = split( /\s+/ ) ; $z[0] }
split( /\n+/ , $mecab->parse( $str ) ) ;
}
my @a = mecab_split( $a ) ;
my @b = mecab_split( $b ) ;
my @diff = sdiff( \@a , \@b ) ;
foreach ( @diff ) {
my ($sign , $a , $b) = @$_ ;
print "$sign/$a/$b/\n" ;
}

(( 動作例 u:同じ,c:変更,+:追加,-:削除 ))
$ perl text-diff.pl
c/This/That/
u/is/is/
u/a/a/
c/pen/pencil/
:
u/たぶん/たぶん/
c/雨/雪/
u/でしょう/でしょう/
u/。/。/
u/EOS/EOS/

プログラム応用のテストの返却を行う。

構造体やポインタ・配列が絡む出題だったので、式の意味を正確に把握できていない人も多い。 解説の際には、式の部分がどういった型なのかを説明しながら、 優先順位を交えて説明を行う。

今回は、出題で解りにくい出題や出題ミスもちょっとあったので、配点には苦慮。

グラフィックス追加説明

テスト解説では、時間が微妙に余るので、補足説明を行った。 CMYKの解説問題で関連する式色系として、 色相Hue・彩度Satulation・明度ValueによるHSV系などを追加説明する。

また、グラフィックスの課題において、様々な開発環境があることを紹介。

• C,C++
  • Microsoft Visual C++(Visual Studio)
  • Borland C++
  • GrWinグラフィックスライブラリ
• Java
  • Java SDK(Sun:Oracle)
  • Processing

情報構造論のテストを返却。 25点満点5問出題で4問選択だから、普通に勉強していれば80点 (平均79点)といった状態。 テストとレポートを返却して、解説を行う。 時間が少し余ったので、テスト前の続きということでハッシュ法(チェイン法)を説明する。

チェイン法

チェイン法の最初に説明した方法は、オープンアドレス法で、 ハッシュ衝突が発生したデータは、本来の場所をはずれて次の場所に保管… といった方法をとっていた。しかしながら、単純なオープンアドレス法では、 ハッシュ表サイズ以上のデータを覚えられない。

チェイン法では、同じハッシュ値になったデータをリストに連結して保存する方式。

// 電話番号をハッシュ法で保存する。
struct List {
int  phone ;
struct List* next ;
} ;
struct List* hash[ SIZE ] ; // NULLで初期化
void entry( int ph ) {
int idx = hash_func( ph ) ;
// 授業ではリストの説明の際の補助関数で説明
// hash[ idx ] = cons( ph , hash[ idx ] ) ;
struct List* p ;
p = (struct List*)malloc( sizeof( struct List ) ) ;
if ( p != NULL ) {
p->phone = ph ;
p->next = hash[ idx ] ;
hash[ idx ] = p ;
}
}
// hash表に登録されているか？
int find( int ph ) {
int idx = hash_func( ph ) ;
struct List* p ;
for( p = hash[ idx ] ; p != NULL ; p = p->next ) {
if ( p->phone == ph )
return 1 ;
}
return 0 ;
}

チェイン法の処理速度を考えると、データ件数がハッシュ表より小さい間は、 ほぼリストの先には1件のデータしか入っていない。 このため検索時間は、ほぼハッシュ値計算の一定時間であり、 となる。

しかし、データ件数Nが、ハッシュ表のサイズを超えると、 リストの先に平均「データ件数/ハッシュ表サイズ」件の要素が連なる。 よって、検索時間はデータ件数に比例し、 となる。

うーむ、説明用にいい図はないかと、「チェイン法、オーダー」で画像検索したら、 オーダーメードの装飾品ばっかり…