集合とリスト処理
リストを用いた待ち行列の補足
# リストによる待ち行列を早速に創造工学演習で応用した人からの質問より…
以前に説明したリストを用いた待ち行列(queue)において、時間的都合から詳しく説明できなかった点の注意点を説明する。
待ち行列の説明では、get() の処理を以下のように示していた。しかし、このままでは、待ち行列が1件の状態で、以下のような get() を実行するとポインタが以下のような図に示される状態となり、tail ポインタがおかしい状態となる。
struct List* queue = NULL ; struct List** tail = &queue ; // 待ち行列の先頭から取り出す。 int get() { struct List* d = queue ; int ans = d->data ; queue = queue->next ; free( d ) ; }
このため、待ち行列内のデータ件数が 0 件になる時だけ、tail ポインタが正しくなるような特別処理を加える必要がある。こういった特別処理は、以後の授業で説明する双方向リスト(deque:double-ended queue)などでは、プログラムを複雑化させてしまうので、別途「番兵」というテクニックが使われる。
リスト処理による積集合
前述の方法は、リストに含まれる/含まれないを、2進数の0/1で表現する方式である。しかし、2進数であれば、unsigned int で 32要素、unsigned long long int で 64 要素が上限となってしまう。 (32bitコンピュータ,gccの場合)
しかし、リスト構造であれば、リストの要素として扱うことで、要素件数は自由に扱える。また、今までの授業で説明してきた cons() などを使って表現すれば、簡単なプログラムでリストの処理が記述できる。
// 先週までに説明してきたリスト構造と補助関数 struct List { int data ; struct List* next ; } ; // リストの入れ物を1つ作る struct List* cons( int x , struct List* n ) { struct List* ans ; ans = (struct List*)malloc( sizeof( struct List ) ) ; if ( ans != NULL ) { ans->data = x ; ans->next = n ; } return ans ; } // リストを表示 void print( struct List* p ) { for( ; p != NULL ; p = p->next ) { printf( "%d " , p->data ) ; } printf( "\n" ) ; } // リストの中に指定要素があるか判定(有れば1,無ければ0) int find( struct List* p , int key ) { for( ; p != NULL ; p = p->next ) if ( p->data == key ) return 1 ; return 0 ; }
例えば、積集合(a ∩ b)を求めるのであれば、リストa の各要素が、リストb の中に含まれるか find 関数でチェックし、 両方に含まれたものだけを、ans に加えていく…という考えでプログラムを作ると以下のようになる。
// 集合積の計算 struct List* set_prod( struct List* a , struct List* b ) { struct List* ans = NULL ; for( ; a != NULL ; a = a->next ) { // aの要素がbにも含まれていたら、ansに加える if ( find( b , a->data ) ) ans = cons( a->data , ans ) ; } return ans ; } void main() { struct List* a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ; struct List* b = cons( 2, cons( 4, cons( 6, NULL ) ) ) ; struct List* c = cons( 4, cons( 6, cons( 9, NULL ) ) ) ; print( set_prod( a , b ) ) ; print( set_prod( b , c ) ) ; }
例題として、和集合、差集合などを考えてみよう。
リストの共有と削除の問題
リスト処理では、mallocを使うが、メモリリークをさせないためには、使用後のリストの廃棄は重要である。リストの全要素を捨てる処理であれば、以下のようになるであろう。
void list_free( struct List* p ) { while( p != NULL ) { struct List* d = p ; p = p->next ; free( d ) ; // 順序に注意 } }
一方、前説明の和集合(a ∪ b)のプログラムを以下のように作った場合、list_freeの処理は問題となる。
// 集合和 struct List* set_union( struct List*a, struct List*b ) { struct List* ans = b ; for( ; a != NULL ; a = a->next ) if ( !find( b , a->data ) ) ans = cons( a->data , ans ) ; return ans ; } void main() { struct List*a = cons( 1, cons( 2, cons( 3, NULL ) ) ) ; struct List*b = cons( 2, cons( 3, cons( 4, NULL ) ) ) ; struct List*c = set_union( a , b ) ; // a,b,cを使った処理 // 処理が終わったので、a,b,cを捨てる list_free( a ) ; list_free( b ) ; list_free( c ) ; // c = { 1 , (bのリスト) } // (b)の部分は先のlist_free(b)で解放済み }
このような、リストb,リストcで共有されている部分があると、データの廃棄処理をどのように記述すべきなのか、問題となる。
これらの解決方法としては、(1) set_union() の最初で、ans=b となっている部分を別にコピーしておく、(2) 参照カウンタ法を用いる、(3) ガベージコレクタのある言語を用いる…などがある。(2),(3)は後期授業で改めて解説を行う。
// 同じ要素を含む、新しいリストを作る struct List* copy( struct List*p ) { struct List*ans = NULL ; for( ; p != NULL ; p = p->next ) ans = cons( p->data , ans ) ; return ans ; } struct List* set_union( struct List*a, struct List* b ) { struct List* ans = copy( b ) ; // この後は自分で考えよう。 }
理解確認
- 2進数を用いた集合処理は、どのように行うか?
- リスト構造を用いた集合処理は、どのように行うか?
- 積集合(A ∩ B)、和集合(A ∪ B)、差集合(A – B) の処理を記述せよ。
差分とフィードバック制御
情報制御基礎の授業を通して、入力値を制御するため、コンピュータを使う場合の数値処理の基礎的な話として、信号の平滑化を説明してきたので、最後に差分について説明をする。また、実際には、入力値を制御に利用する一般的な構成のフィードバック制御について説明する。
変化の検出
例えば、以下のような若干のノイズが混ざった入力信号が与えられたとする。この波形で「大きな山が何ヶ所ありますか?」と聞かれたら、いくつと答えるべきであろうか?山の判断方法は色々あるが、4カ所という答えは、1つの見方であろう。では、この4カ所という判断はどうすればいいだろうか?
こういった山の数を数えるのであれば、一定値より高いか低いか…という判断方法もあるだろう。この絵であれば、15ステップ目、32ステップ目付近は、100を越えていることで、2つの山と判断できるだろう。
こういった予め決めておいた値より「上か?/下か?」で判断するときの基準値は、しきい値(閾値:threshold)と呼ぶ。
しかし、この閾値では、40ステップ目から50ステップ目も100を越えており、以下のようなプログラムを書いたら、40ステップ目~50ステップ目すべてをカウントしてしまう。
#define THRESHOLD 100 int x[ 100 ] = { // 波形のデータが入っているとする。 } ; int count = 0 ; for( int i = 0 ; i < 100 ; i++ ) { if ( x[i] >= THRESHOLD ) count++ ; }
また、65ステップ目の小さな山も1個とカウントしてしまう。
この問題を避けるために、閾値を130にすると、今度は最初の2つの山をカウントできない。どうすれば、山の数をうまくカウントできるのだろうか?
差分を求める
前述のような問題で山の数を数える方法を考えていたが、数学で山を見つける時には、何をするだろうか?
数学なら、山や谷の頂点を求めるのならば、微分して変化量が0となる場所を求めることで、極大値・極小値を求めるだろう。そこで、山を見つけるために入力値の変化量を求めてみよう。
表計算ソフトで差分を計算するのであれば、セルに図のような式を入力すればいいであろう。このようなデータ点で前の値との差を差分と呼ぶ。数学であれば、微分に相当する。
このグラフを見ると、波形が大きく増加する部分で、差分が大きな正の値となる。さらに波形が大きく減少する部分で差分が負の大きな値となる。特にこのデータの場合、山と判断したい部分は差分が20以上の値の部分と定義することも考えられる。
#define TH_DIFF 20 int x[ 100 ] = { // 波形のデータが入っているとする。 } ; int count = 0 ; for( int i = 0 ; i < 100 ; i++ ) { if ( x[i] - x[i-1] >= TH_DIFF && x[i+1] - x[i] <= -TH_DIFF ) count++ ; }
しかし、このプログラムでは、山の数をうまくカウントしてくれない。うまく、山の数を数えるためには、差分の値を山と判断するための閾値(この場合は20)を調整することになるだろう。
制御工学の概要
以下に、制御工学ではどのようなことを行うのか、概要を述べる。
ここで紹介する制御理論は、古典制御理論と呼ばれる。
制御工学では、入力値と、何らかの処理を施し出力値
が得られるシステムで、どのように制御するかを考える。
例えば、電気ポットの温度制御をする場合、設定温度の値を入力値とし、何らかの処理を行い、出力となるヒーターの電流を制御し、最終的には温度
が測定される。ヒーターは、設定温度
と温度計の値
の差
に応じて電流量を変化させる。このように一般的な制御では、最終的な温度が入力に戻っている。このように目標値に近づけるために、目標値との差に応じて制御することをフィードバック制御という。
制御の仕方には様々な方法があるが、 がとある時間で0からYに変化した場合を考える。入力と出力で制御された波形の例を示す。
この波形では、黒のように入力値が変化した場合、それに追いつこうと出力が変化する。(1)理想的には、速やかに追いつく赤のように変化したい。しかし、(2)慎重に制御をする人なら、変化への制動が大きい過制動(青点線)となり、目標値に追いつくまでに時間がかかる。(3)一方、すこしでもずれたら直そうとする人なら、時間的には速い反応ができるかもしれないが、目標値を追い越したり、増えすぎ分を減らしすぎたりして脈動する過制御(赤点線)となるかもしれない。
PID制御
目標値、出力
、ずれ(偏差)
、制御量
とした時、基本的なフィードバック制御として偏差の使い方によってP動作,I動作,D動作がある。参考 Wikipedia PID制御
比例制御(P制御)
偏差に比例した制御を行う方式(を比例ゲインと呼ぶ)
今年のコロナ騒動を例にとるならば、比例制御は、今日の感染者数y(t)と目標としたい感染者数x(t)の差に応じて、対策の強さu(t)を決めるようなもの。
積分制御(I制御)
偏差のある状態が長い時間続く場合、入力値の変化を大きくすることで目標値に近づけるための制御。(は積分ゲイン)
積分制御は、目標の感染者数x(t)を感染者数y(t)が超えた累積患者数に応じて、対策を決めるようなもの。
微分制御(D制御)
急激な出力値の変化が起こった場合、その変化の大きさに応じて妨げようとする制御。(は微分ゲイン)
微分制御は、目標数と感染者数の差が、前日よりどのぐらい増えたか(患者の増減の量:変化量)に応じて、対策を決めるようなもの。
PID制御
上記のI制御やD制御だけでは、安定させることが難しいので、これらを組み合わせたPID制御を行う。
この中で、の値は、制御が最も安定するように調整を行うものであり、数値シミュレーションや、ステップ応答を与えた時の時間的変化を測定して調整を行う。
様々な移動平均
波形処理をハードウェアで行うかソフトウェアで行うか
組込み用の小型コンピュータが普及する以前は、このような波形に対する処理を行う場合には、電子回路的に波形のフィルタリングを行っていた。しかし電子回路的な方法では、回路の特性が変化してうまく処理ができなくなった場合に、回路の組み換えが発生するかもしれない。ただし回路の変更は基板の作り直しが必要であったりすることから、コストがかかる。
一方、A/D変換機能を内蔵した組込み用小型コンピュータも極めて安価になってきた。
こういったコンピュータの普及で、最近ではアナログ値をコンピュータに取り込んでデジタルの数値的な処理で余計な情報を取り除く。この方法であれば、プログラムを変更するだけなので、安価に変更が可能となる。ただし、アナログ値をA/D変換するのには時間がかかることから、周波数の高い信号には不向きである。
単純移動平均
前回説明を行った単純移動平均は、時刻tの平均を、その前後のデータで平均を求めた。この方式は、実際には与えられた波形のデータを全部記録した後に、単純移動平均をとる場合に有効である。
しかし、時々刻々変化する測定値の平均をその都度使うことを考えると、上記の方法は、未来の測定値
を使っていることから、現実的ではない。
// 単純移動平均(未来の値も使う) #define NS 3 int x[ SIZE ] ; // 入力値 int y[ SIZE ] ; // 出力値 for( int t = NS ; t < SIZE-NS ; t++ ) { int s = 0 ; for( int i = -NS ; i <= +NS ; i++ ) // 2*NS+1回の繰り返し s += x[t+i] ; y[t] = s / (2*NS + 1) ; }
過去の値だけを使った移動平均
そこで、過去の値だけで移動平均をとることも考えられる。
この、単純移動平均と、過去の値だけを使う単純移動平均を、適当な測定値に対して適用した場合のグラフの変化を Excel によってシミュレーションした結果を以下に示す。
しかし、このグラフを見ると、波形後半の部分に注目するとよく分かるが、過去の値だけを使った移動平均では、測定値が立ち上がったのを追いかけて値が増えていく。これでは移動平均は時間的な遅れとなってしまう。
// 未来の値を使わない単純移動平均 for( int t = NS ; t < SIZE ; t++ ) { int s = 0 ; for( int i = 0 ; i <= NS ; i++ ) // NS+1回の繰り返し s += x[t-i] ; y[t] = s / (NS+1) ; }
加重移動平均
過去の値を使った移動平均では遅れが発生する。でも、平均を取る際に、「n回前の値」と「現在の値」を考えた時、「その瞬間の平均値」は「現在の値」の方が近い値のはず。であれば、平均を取る時に、「n回前の値は少なめ」「現在の値は多め」に比重をかけて加算する方法がある。
for( int t = 3 ; t < SIZE ; t++ ) { // 数個の移動平均だし、 // ループを使わずに書いてみる。 int s = x[t] * 3 // 現在の値は大きい重み + x[t-1] * 2 // 1つ前の値 + x[t-2] * 1 ; // 2つ前の値(重みは最小) y[t] = s / (3+2+1) ; }
この様に、過去に遡るにつれ、平均をとる比重を直線的に小さくしながら移動平均をとる方法は、加重移動平均と呼ばれる。以下にその変化をExcelでシミュレーションしたものを示す。
指数移動平均
ここまで説明してきた、単純移動平均や、加重移動平均は、平均をとる範囲の「過去の値」を記憶しておく必要がある。広い時間にわたる移動平均をとる場合は、それに応じてメモリも必要となる。これは、組み込み型の小型コンピュータであれば、メモリが足りず平均処理ができない場合もでてくる。
そこで、荷重移動平均の重みを、は、100%,
は50%,
は25%… というように、過去に遡るにつれ、半分にして平均をとる。
しかし、以降の項で、
を使うと以下のように書き換えることができる。
// 指数移動平均は、プログラムがシンプル // 1つ前の平均y[t-1]を覚えるだけでいい。 for( int t = 1 ; t < SIZE ; t++ ) { y[t] = ( x[t] + y[t-1] ) / 2 ; }
この方法であれば、直前の平均値を記録しておくだけで良い。このような移動平均を、指数移動平均と呼ぶ。
ここで示した指数移動平均は、過去を遡るにつれとなっているが、これをさらに一般化した指数移動平均は、以下の式で示される。前述の移動平均は、
とみなすことができる。
#define ALPHA 0.5 for( int t = 1 ; t < SIZE ; t++ ) { y[t] = ALPHA * x[t] + (1.0 - ALPHA) * y[t-1] ; }
以下のプログラムは、うまく動かない。理由を説明せよ。
#define RVA 4 for( int t = 1 ; t < SIZE ; t++ ) { // 以下はy[t]は全部ゼロになる。 y[t] = 1/RVA * x[t] + (1.0 - 1/RVA) * y[t-1] ; // 以下は、整数型演算だけで、正しく動くだろう。 // y[t] = ( x[t] + (RVA-1) * y[t-1] ) / RVA ; }
理解度確認のための小レポート
上記の移動平均の理解のために、以下の資料(講義では印刷資料を配布)の表の中を、電卓などを使って計算せよ。
計算したら、その結果をグラフの中にプロットし、どういった波形となるか確認し、レポートとして提出すること。
集合とビット演算
リスト構造は、必要に応じてメモリを確保するデータ構造であり、データ件数に依存しないプログラム が記述できる。その応用として、集合処理を考えてみる。
bit演算子
2進数を使った処理をする時には、bit演算子を用いる。
bit AND | 3 & 5 0011)2 & 0101)2= 0001)2 |
論理積演算子 if ( a == 1 && b == 2 ) … |
bit OR | 3 | 5 0011)2 | 0101)2= 0111)2 |
論理和演算子 if ( a == 1 || b == 2 ) … |
bit NOT | ~5 ~ 00..00,0101)2= 11..11,1010)2 |
論理否定演算子 if ( !a == 1 ) … |
bit EXOR | 3 ^ 5 0011)2 ^ 0101)2= 0110)2 |
|
bit 左シフト | 3 << 2 0011)2 << 2 = 001100)2 |
3 * 22 と同じ |
bit 右シフト | 12 >> 2 1100)2 >> 2 = 11)2 |
12 / 22 と同じ |
#include <stdio.h> int main() { // bit演算子と論理演算子 printf( "%d¥n" , 12 & 5 ) ; // 1100 & 0101 = 0100 よって 4が表示される printf( "%d¥n" , 12 && 0 ) ; // 0が表示 論理演算子とbit演算子の違い printf( "%d¥n" , 12 | 5 ) ; // 1100 | 0101 = 1101 よって 13が表示される printf( "%d¥n" , 12 || 0 ) ; // 1が表示 // シフト演算子 printf( "%d¥n" , 3 << 2 ) ; // 12が表示 printf( "%d¥n" , 12 >> 2 ) ; // 3が表示 // おまけ printf( "%d¥n" , ~(unsigned)12 + 1 ) ; // 2の補数(NOT 12 + 1) = -12 return 0 ; }
2進数を用いた集合計算
リストによる集合の前に、もっと簡単な集合処理を考える。
最も簡単な方法は、要素に含まれる=1 か 含まれない=0 を配列に覚える方法であろう。数字Nが集合に含まれる場合は、配列[N]に1を覚えるものとする。この方法で積集合などを記述した例を以下に示す。ただし、演習課題として穴埋めを含むので注意。
しかし、上述のプログラムでは、要素に含まれる/含まれないという1bitの情報を、整数型で保存しているためメモリの無駄である。
データ件数の上限が少ない場合には、「2進数の列」の各ビットを集合の各要素に対応づけし、要素の有無を0/1で表現する。この方法を用いるとC言語のビット演算命令で 和集合、積集合を計算できるので、処理が極めて簡単になる。
以下のプログラムは、0〜31の数字を2進数の各ビットに対応付けし、 ba = {1,2,3} , bb = {2,4,6} , bc= {4,6,9} を要素として持つ集合で、ba ∩ bb , bb ∩ bc , ba ∪ bc の計算を行う例である。
// 符号なし整数を uint_t とする。 typedef unsigned int uint_t ; // uint_tのbit数 #define UINT_BITS (sizeof( uint_t ) * 8) // 集合の内容を表示 void bit_print( uint_t x ) { for( int i = 0 ; i < UINT_BITS ; i++ ) if ( (x & (1 << i)) != 0 ) printf( "%d " , i ) ; printf( "\n" ) ; } void main() { // 98,7654,3210 // ba = {1,2,3} = 00,0000,1110 uint_t ba = (1<<1) | (1<<2) | (1<<3) ; // bb = {2,4,6} = 00,0101,0100 uint_t bb = (1<<2) | (1<<4) | (1<<6) ; // bc = {4,6,9} = 10,0101,0000 uint_t bc = (1<<4) | (1<<6) | (1<<9) ; bit_print( ba & bb ) ; // ba ∩ bb = {2} bit_print( bb & bc ) ; // bb ∩ bc = {4,6} bit_print( ba | bc ) ; // ba ∪ bc = {1,2,3,4,6,9} }
このような、2進数を用いた処理で有名なものとして、エラトステネスのふるいによる素数探索がある。このアルゴリズムでは、各bitを整数に対応付けし、素数で無いと判断した2進数の各桁に1の目印をつけていく方式である。
uint_t prime = 0 ; // 初期値=すべての数は素数とする。 void filter() { for( int i = 2 ; i < UINT_BITS ; i++ ) { if ( (prime & (1 << i)) == 0 ) { // iの倍数には、非素数の目印(1)をつける for( int j = 2*i ; j < UINT_BITS ; j += i ) prime |= (1 << j) ; } } for( int i = 2 ; i < UINT_BITS ; i++ ) { // 目印のついていない数は素数 if ( (prime & (1 << i)) == 0 ) printf( "%d\n" , i ) ; } }
ミニ課題
最初に示した、配列による集合の set-array.cxx で、配列による和集合、エラトステネスのふるいの処理の一部を記述していない。未完成の部分を埋めて、動作を確認せよ。
スタックと待ち行列
前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。
計算処理中に一時的なデータの保存として、stackとqueueがよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。
スタック
配列を用いたスタック
一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。
#define STACK_SIZE 32 int stack[ STACK_SIZE ] ; int sp = 0 ; void push( int x ) { // データをスタックの一番上に積む stack[ sp++ ] = x ; } int pop() { // スタックの一番うえのデータを取り出す return stack[ --sp ] ; } void main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d\n" , pop() ) ; // 3 printf( "%d\n" , pop() ) ; // 2 printf( "%d\n" , pop() ) ; // 1 }
++,–の前置型と後置型の違い
// 後置インクリメント演算子 int i = 100 ; printf( "%d" , i++ ) ; // これは、 printf( "%d" , i ) ; i++ ; // と同じ。100が表示された後、101になる。 // 前置インクリメント演算子 int i = 100 ; printf( "%d" , ++i ) ; // これは、 i++ ; printf( "%d" , i ) ; // と同じ。101になった後、101を表示。
リスト構造を用いたスタック
しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。
struct List* stack = NULL ; void push( int x ) { // リスト先頭に挿入 stack = cons( x , stack ) ; } int pop() { // リスト先頭を取り出す int ans = stack->data ; struct List* d = stack ; stack = stack->next ; free( d ) ; return ans ; }
キュー(QUEUE)
2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。
配列を用いたQUEUE / リングバッファ
配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。
#define QUEUE_SIZE 32 int queue[ QUEUE_SIZE ] ; int wp = 0 ; // write pointer(書き込み用) int rp = 0 ; // read pointer(読み出し用) void put( int x ) { // 書き込んで後ろ(次)に移動 queue[ wp++ ] = x ; if ( wp >= QUEUE_SIZE ) // 末尾なら先頭に戻る wp = 0 ; } int get() { // 読み出して後ろ(次)に移動 int ans = queue[ rp++ ] ; if ( rp >= QUEUE_SIZE ) // 末尾なら先頭に戻る rp = 0 ; return ans ; } void main() { put( 1 ) ; put( 2 ) ; put( 3 ) ; printf( "%d\n" , get() ) ; // 1 printf( "%d\n" , get() ) ; // 2 printf( "%d\n" , get() ) ; // 3 }
このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか?
リスト構造を用いたQUEUE
前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。
この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。
struct List* queue = NULL ; struct List** tail = &queue ; void put( int x ) { // リスト末尾に追加 *tail = cons( x , NULL ) ; tail = &( (*tail)->next ) ; } int get() { // リスト先頭から取り出す int ans = queue->data ; struct List* d = queue ; queue = queue->next ; free( d ) ; return ans ; }
ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。
理解確認
- 配列を用いたスタック・待ち行列は、どのような処理か?図などを用いて説明せよ。
- リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
- スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか?欠点があるか説明せよ。
オブジェクト指向とソフトウェア工学
オブジェクト指向プログラミングの最後の総括として、 ソフトウェア工学との説明を行う。
トップダウン設計とウォーターフォール型開発
ソフトウェア工学でプログラムの開発において、一般的なサイクルとしては、 専攻科などではどこでも出てくるPDCAサイクル(Plan, Do, Check, Action)が行われる。 この時、プログラム開発の流れとして、大企業でのプログラム開発では一般的に、 トップダウン設計とウォーターフォール型開発が行われる。
トップダウン設計では、全体の設計(Plan)を受け、プログラムのコーディング(Do)を行い、 動作検証(Check)をうけ、最終的に利用者に納品し使ってもらう(Action)…の流れで開発が行われる。設計の中身も機能仕様や動作仕様…といった細かなフェーズになることも多い。 この場合、コーディングの際に設計の不備が見つかり設計のやり直しが発生すれば、 全行程の遅延となることから、前段階では完璧な設計が必要となる。 このような、上位設計から下流工程にむけ設計する方法は、トップダウン設計などと呼ばれる。また、処理は前段階へのフィードバック無しで次工程へ流れ、 川の流れが下流に向かう状態にたとえ、ウォーターフォールモデルと呼ばれる。
引用:Think IT 第2回開発プロセスモデル
このウォーターフォールモデルに沿った開発では、横軸時間、縦軸工程とした ガントチャートなどを描きながら進捗管理が行われる。
引用:Wikipedia ガントチャート
一方、チェック工程(テスト工程)では、 要件定義を満たしているかチェックしたり、設計を満たすかといったチェックが存在し、 テストの前工程にそれぞれ対応した機能のチェックが存在する。 その各工程に対応したテストを経て最終製品となる様は、V字モデルと呼ばれる。
引用:@IT Eclipseテストツール活用の基礎知識
しかし、ウォーターフォールモデルでは、(前段階の製作物の不備は修正されるが)前段階の設計の不備があっても前工程に戻るという考えをとらないため、全体のPDCAサイクルが終わって次のPDCAサイクルまで問題が残ってしまう。巨大プロジェクトで大量の人が動いているだから、簡単に方針が揺らいでもトラブルの元にしかならないことから、こういった手法は大人数巨大プロジェクトでのやり方である。
ボトムアップ設計とアジャイル開発
少人数でプログラムを作っている時(あるいはプロトタイプ的な開発)には、 部品となる部分を完成させ、それを組合せて全体像を組み上げる手法もとられる。 この方法は、ボトムアップ設計と呼ばれる。このような設計は場当たり的な開発となる場合があり設計の見直しも発生しやすい。
また、ウォーターフォールモデルでは、前工程の不備をタイムリーに見直すことができないが、 少人数開発では適宜前工程の見直しが可能となる。 特にオブジェクト指向プログラミングを実践して隠蔽化が正しく行われていれば、 オブジェクト指向によるライブラリの利用者への影響を最小にしながら、ライブラリの内部設計の見直しも可能となる。 このような外部からの見た挙動を変えることなく内部構造の改善を行うことはリファクタリングと呼ばれる。
一方、プログラム開発で、ある程度の規模のプログラムを作る際、最終目標の全機能を実装したものを 目標に作っていると、全体像が見えずプログラマーの達成感も得られないことから、 機能の一部分だけ完成させ、次々と機能を実装し完成に近づける方式もとられる。 この方式では、機能の一部分の実装までが1つのPDCAサイクルとみなされ、 このPDCAサイクルを何度も回して機能を増やしながら完成形に近づける方式とも言える。 このような開発方式は、アジャイルソフトウェア開発と呼ぶ。 一つのPDCAサイクルは、アジャイル開発では反復(イテレーション)と呼ばれ、 短い開発単位を繰り返し製品を作っていく。この方法では、一度の反復後の実装を顧客に見てもらい、 顧客とプログラマーが一体となって開発が行われる。
引用:コベルコシステム
エクストリームプログラミング
アジャイル開発を行うためのプログラミングスタイルとして、 エクストリームプログラミング(Xp)という考え方も提唱されている。 Xpでは、5つの価値(コミュニケーション,シンプル,フィードバック,勇気,尊重)を基本とし、 開発のためのプラクティス(習慣,実践)として、 テスト駆動開発(コーディングでは最初に機能をテストするためのプログラムを書き、そのテストが通るようにプログラムを書くことで,こまめにテストしながら開発を行う)や、 ペアプログラミング(2人ペアで開発し、コーディングを行う人とそのチェックを行う人で役割分担をし、 一定期間毎にその役割を交代する)などの方式が取られることが多い。
リーンソフトウェア開発は、品質の良いものを作る中で無駄の排除を目的とし、本当にその機能は必要かを疑いながら、優先順位をつけ実装し、その実装が使われているのか・有効に機能しているのかを評価ながら開発をすすめる。
伽藍(がらん)とバザール
これは、通常のソフトウェア開発の理論とは異なるが、重要な開発手法の概念なので「伽藍とバザール」を紹介する。
伽藍(がらん)とは、優美で壮大な寺院のことであり、その設計・開発は、優れた設計・優れた技術者により作られた完璧な実装を意味している。バザールは有象無象の人の集まりの中で作られていくものを意味している。
たとえば、伽藍方式の代表格である Microsoft の製品は、優秀なプロダクトだが、中身の設計情報などを普通の人は見ることはできない。このため潜在的なバグが見つかりにくいと言われている。
これに対しバザール方式の代表格の Linux は、インターネット上にソースコードが公開され、誰もがソースコードに触れプログラムを改良してもいい。その中で、新しい便利な機能を追加しインターネットに公開されれば、良いコードは生き残り、悪いコードは淘汰されていく。
バザール方式は、オープンソースライセンスにより成り立っていて、このライセンスが適用されていれば、改良した機能はインターネットに公開する義務を引き継ぐ。このライセンスの代表格が、GNU パブリックライセンス(GPL)であり、公開の義務の範囲により、BSD ライセンス、Apacheライセンスといった違いがある。
移動平均の処理
前回の授業で説明したようなA/D変換した数値データを読み取った場合、どのようなことが発生するか考える。
例えば、以下に示すような測定値があったとする。
このデータの一部をグラフ化してみると、次のような波形であった。
この波形をみると、大きく見ればsinカーブだが、細かい点を見るとデータにブレがある。
誤差の原因
このような測定結果が得られた場合、本来コンピュータで処理したいデータは何であろうか?
原因は様々なものが考えられるが、
- 回路のノイズ対策が不十分で、外部の電気的な影響が混入。
オシロスコープで周期を図ると、60Hz なら、交流電源だったり… - D/A 変換を行う場合には、量子化誤差かもしれない。
例えば、最初の波形が、加速度センサーの値であったとして、船の上で揺れているために、大きな周期で加速度が変化しているかもしれない。一方で、船自体がエンジンによる揺れで加速度が変化しているかもしれない。
船の中で波の揺れと、エンジンの揺れが観測されている加速度センサーの情報で、船の揺れの大きさ・揺れの周期を知りたい場合、どうすればいいだろうか?
移動平均
このデータを見ると、10個のデータまでの間で、波形が上下に変動している。船の揺れとエンジンの揺れが原因であれば、10個ぐらいのデータのゆらぎが、エンジンによる揺れと考えられる。では、この10個ぐらいの範囲で値が上下の影響を減らしたければ、どうすればいいか?一番簡単な方法は、前後10個のデータで平均を取ればいいだろう。増減する値を加えれば、プラスの部分とマイナスの部分の値が相殺されて0に近くはず。そこでは、Excel で前後データの平均をとってみよう。
Excelで前後11点の平均を求める式をセルに入れる
青線:元波形データ(B列)、赤線:前後11点の平均(C列)
このように、データの前後の決められた範囲の平均を平均する処理は、移動平均(単純移動平均)と呼ぶ。
時間tにおけるデータをとした場合、前後5点の移動平均
は、以下のような式で表せるだろう。
移動平均のプログラム
Excel で計算と同じ処理をプログラムで行うと以下のようになるだろう。
// moving-average.c #include <stdio.h> #define WIDTH 5 double data[ 1000 ] ; // 元データ double ans[ 1000 ] ; // 平均後のデータ int main() { int t , i , size ; // 最初に全部のデータを読み込む for( size = 0 ; size < 1000 ; size++ ) { int num ; // コンマ区切りのデータを読む // 2つのデータが読み込めない時は入力を終了 if ( scanf( "%d,%lf" , &num , &data[size] ) != 2 ) break ; } // 移動平均を求める for( t = WIDTH ; t < size - WIDTH ; t++ ) { // t番目のデータの前後WIDTH個の合計 double sum = 0 ; for( i = -WIDTH ; i <= WIDTH ; i++ ) sum += data[ t + i ] ; ans[ t ] = sum / (2*WIDTH + 1) ; } // 計算後のデータをコンマ区切りで出力 for( t = 0 ; t < size ; t++ ) { printf( "%d, %10.6lf, %10.6lf\n" , t , data[ t ] , ans[ t ] ) ; } return 0 ; }
このプログラムを動かすと、データ番号とデータ値をコンマ区切りで与えること。
入力リダイレクトと出力リダイレクト
上記のプログラムでは、キーボードからデータを入力しなくてはいけない。これでは入力が大変なので、保存したファイルを使ってプログラムにデータを与える。
上記のプログラムを、パソコンの Z:¥課題¥moving-average.c に保存したとする。このプログラムを「コンパイル&実行」すれば、Z:¥課題¥moving-average.exe という実行プログラムが作られ、プログラムが起動する。このままでは、キーボードからデータを入力する必要がある。
(1) ファイルから入力した値を使って処理を行うのであれば、コマンドを起動。
タスクバー左側の検索バーに、cmd.exe と入力すれば、命令入力画面が表示される。
(2) コマンド画面で、以下のように入力し、moving-average.exe があるか確認する。
C:¥WINDOWS¥System32> Z: 青は表示される部分、赤が入力 Z:¥> cd Z:¥課題 Z:¥課題¥> dir *.exe 06/21/2019 12:30PM 12345 moving-average.exe
(3) 最初のデータの記録されたCSVファイルを Z:¥課題 に保存する。
(4) コマンド画面で、以下のようにプログラム名の後ろに “< ファイル名” をつけて起動すると、キーボード入力の代わりに、ファイルから読み込んでプログラムが動く。このような起動は、入力リダイレクトと呼ぶ。
Z:¥課題¥> moving-average.exe < 2018-06-05-wave.csv xx, xxx.xxxx, xxx.xxxx ←結果が画面に表示される
(5) これでは、結果がよく分からないので、ファイルに保存し Excel でグラフ化する。コマンド画面で、以下のようにプログラム名の後ろに“> ファイル名” をつけて起動すると、結果を画面に出力する代わりに、ファイルに結果を保存してくれる。このような起動は、出力リダイレクトと呼ぶ。
Z:¥課題¥> moving-average.exe < 2018-06-05-wave.csv > out.csv
出力された out.csv は、データがコンマ区切りなので、Excel でひらけば、結果を表として簡単に読み込める。後は、グラフ化したい範囲を、マウスでドラッグ(もしくはシフトキーを押しながらカーソル移動)し、[挿入]-[グラフ]-[散布図]-[折れ線グラフ] でグラフ化すればいい。
自宅学習の課題
表計算ソフトで、移動平均を計算させてみよう。 ※
- 元波形
- 前後5点で移動平均
- 前後11点で移動平均
- 前後51点で移動平均
をとるような表計算の式を書き込んで、その結果の波形がどんなグラフになるのか確認しておくこと。
リスト処理基本の回答
前回授業の、sum(),max(),mean(),find() のループ版や、再帰版のプログラム例
// 合計ループ版 int sum( struct List* p ) { int s = 0 ; for( ; p != NULL ; p = p->next ) s += p->data ; return s ; } // 合計再帰版 int sum( struct List* p ) { if ( p == NULL ) return 0 ; else return p->data + sum( p->next ) ; // 場所のデータと以降の合計 } // 最大値ループ版 int max( struct List* p ) { if ( p == NULL ) { return 0 ; } else { int m = p ->data ; // 先頭を仮の最大値 for( p = p->next ; p != NULL ; p = p->next ) if ( m < p->data ) // それ以降から大きい物を見つけたら m = p->data ; // その値を最大値として保存 return m ; } } // 最大値再帰版 int max( struct List* p ) { if ( p == NULL ) // data0件で0を返すことにする return 0 ; else if ( p->next == NULL ) return p->data ; else { int m = max( p->next ) ; // 以降のデータの最大値より if ( m < p->data ) // その場所のデータが大きい return p->data ; else return m ; } } // 平均ループ版 double mean( struct List* p ) { int c = 0 , s = 0 ; for( ; p != NULL ; p = p->next ) { c++ ; s += p->data ; } return (double)s / (double)c ; } // 平均の再帰版 // ただし、 mean( top , 0 , 0 ) のように呼び出す。 double mean( struct List* p , int s , int c ) { // s はリストの合計 if ( p == NULL ) // c はリストの件数 return (double)s / (double)c ; else return mean( p->next , s + p->data , c + 1 ) ; } // C++なら、meanの宣言に引数のデフォルト値を指定すれば // double mean( struct List* p , int s = 0 , int c = 0 ) { ... } // printf( "%lf" , mean( top ) ) ; みたいな使い方ができる。 // findループ版 int find( struct List* p , int key ) { int i = 0 ; for( ; p != NULL ; p = p->next ) if ( p->data == key ) return i ; // 見つかったらi番目 else i++ ; return -1 ; // 見つからなかったら(-1) } // find再帰版 // ループ版とは返り値の取り扱いが違うので注意 int find( struct List* p , int key ) { if ( p == NULL ) return 0 ; // 見つからなかった else if ( p->data == key ) return 1 ; else return find( p->next , key ) ; }
リストへの追加処理
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。
最も単純なリスト挿入
struct List { int data ; struct List* next ; } ; // 保存するリストの先頭 struct List* top = NULL ; void print( struct List* p ) { for( ; p != NULL ; p = p->next ) // ~~~~~~~(A) printf( "%d " , p->data ) ; // ~~~~~(B) printf( "¥n" ) ; }//~~~~~~~~~~~~~~(C) int main() { int x ; while( scanf( "%d" , &x ) == 1 ) { // ~~~~~~~~~~~~~~~~~~(D) top = cons( x , top ) ; } print( top ) ; // 前回示したリスト全要素表示 return 0 ; } // (1) 入力で、11 , 22 を与えるとどうなる? - 下図参照 // (2) 練習問題(A),(B),(C),(D)の型は? // (3) 入力で、11,22 の後に 33 を与えるとどうなる? // C++ コンテナクラスで書くと...(auto を使うには C++11 以上) // #include <iostream> // #include <forward_list> // #include <algorithm> // int main() { // std::forward_list<int> top ; // int x ; // while( std::cin >> x ) // top.push_front( x ) ; // for( auto i = top.cbegin() ; i != top.cend() ; ++i ) // std::cout << *i << std::endl ; // return 0 ; // }
ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい。
要素を末尾に追加
前に示した方法は、逆順になるので、与えられた要素が末尾に追加する方法を示す。
struct List* top = NULL ; struct List** tail = &top ; int main() { int x ; while( scanf( "%d" , &x ) == 1 ) { // ~~~~~~~~~~~~~~~~~~~~~~~(A) *tail = cons( x , NULL ) ; tail = &((*tail)->next) ; }//~~~~~~~~~~~~~~~~~~~~~~~(B) 下記の解説参照 print( top ) ; // 前回示したリスト全要素表示 // ~~~~~~~~~~~~(C) return 0 ; } // (1) 入力で 11,22 を与えるとどうなる? - 下図参照 // (2) 練習問題(A),(C)の型は? // (3) 11,22の後に、さらに 33 を与えるとどうなる?
この方法は、次回にデータを追加する場所(末尾だからNULLが入っている)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。
理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
void insert( struct List*p , int data ) { // あえて、補助関数consを使わずに書いてみる struct List* n ; n = (struct List*)malloc( sizeof( struct List ) ) ; ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A) if ( n != NULL ) { n->data = data ; ~~~~(B) n->next = p->next ; ~~~~~~~(C) p->next = n ; } // consを使って書けば、簡単 // p->next = cons( data , p->next ) ; } int main() { struct List* top = cons( 11 , cons( 22 , cons( 44 , NULL ) ) ) ; // ↑ insert( top->next , 33 ) ; // ここに33を挿入したい return 0 ; }
void remove_after( struct List* p ) { struct List* del = p->next ; p->next = del->next ; free( del ) ; } int main() { struct List* top = cons( 11 , cons( 22 , cons( 33 , cons( 44 , NULL ) ) ) ) ; remove_after( top->next ) ; // ↑ return 0 ; // これを消したい }
理解度確認
上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。
レポート課題
以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) の番号の課題に取り組むこと。
- 緯度(latitude)経度(longitude)とその場所の都市名(city)
- 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
- 複素数(re,im)
このようなプログラムを作るのであれば、以下の例を参考に。
struct NameAgeList { char name[ 20 ] ; // 名前 int age ; // 年齢 struct NameAgeList* next ; // 次のデータへのポインタ } ; struct NameAgeList* na_cons( char* nm, int ag, struct NameAgeList*p ) { struct NameAgeList* ans ; ans = (struct NameAgeList*)malloc( sizeof( struct NameAgeList ) ) ; if ( ans != NULL ) { strcpy( ans->name , nm ) ; ans->age = ag ; ans->next = p ; } return ans ; } int main() { struct NameAgeList* top = NULL ; struct NameAgeList* p ; char buff[ 1024 ] ; // 1行読み込みの繰り返し while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { char nm[ 100 ] ; int ag ; // 1行の中から名前と年齢があったら na_cons で挿入保存 if ( sscanf( buff , "%s%d" , nm , &ag ) == 2 ) { top = na_cons( nm , ag , top ) ; } } // 読み込んだデータを全部出力 for( p = top ; p != NULL ; p = p->next ) printf( "%s %d¥n" , p->name , p->age ) ; return 0 ; }
バックスラッシュと円マーク
授業のC言語のプログラムで printf 関連でいくつか質問を受けることが多いのでメモ
Visual Studio では printf_s() , scanf_s() を使う
Microsoft の Visual Studio でプログラミングの勉強をする人も多いだろうが、C 言語の基本関数 printf() とか scanf() を使ったプログラムが動かないというトラブルを聞く。
C言語の scanf() がバッファオーバーフロー対策が怪しいため、Visual Studio(Microsoft) では保護対策してある scanf_s() があり、これを使えということになっている。バッファオーバーフローの危険があるのは、scanf() なんだけど、同様に printf() の代わりに、printf_s() が用意されている。
C言語標準関数 | Microsoft関数 | 備考 |
---|---|---|
scanf() | scanf_s() | 汎用フォーマット入力 |
printf() | printf_s() | 汎用フォーマット出力 |
strcpy() | strcpy_s() | 文字列コピー 同様の関数: strncpy() |
strdup() | _strdup() | 文字列をヒープメモリにコピー |
すでに提出されているレポートを見ると、同様に strcpy() もセキュリティ対策の strcpy_s() を使っている人も多いようです。
マイクロソフト御謹製の strcpy_s() を使わなくても、C言語標準関数には strncpy() があるが、若干動きが違うみたい。
バックスラッシュ∖ と円マーク ¥
元々コンピュータの 8bit で表現する基本的な英数字には、ASCII コード表が決められている。ASCII コード表の中では、0x5C には、バックスラッシュ「∖」が割り振られている。コンピュータが日本で使われるようになると、ASCII コード表に、半角カタカナを追加した JIS コード表(1バイト文字) が決められている。文字コード 0x00~0x7F までは ASCII コードと基本的に同じであるが、唯一 0x5C には、∖ の代わりに円マーク「¥」が割り振られた。
このため、C言語の 改行文字を表す “∖n” は、日本のパソコンで表示すると“¥n”と表示されるし、日本語のコンピュータの教科書では、”¥n”にて記載されていることが多い。同様に、Windows のディレクトリ区切り文字は本来∖であり、ファイルパスは“C:∖Users∖foobar” のように示されるが、日本のパソコンでは、“C:¥Users¥foobar” と表示される。
プログラムのエディタでC言語のプログラミングをする際は、以前であれば、キーボードの¥マークをタイプすれば、¥が表示されるが、内部的には文字コード 0x5C で保存される。最近の開発環境なら、¥マークをタイプすれば、∖ が表示されるものも増えてきた。
ただ、エディタによっては、今まで内部コードでの 0x5C を、英文字フォントならバックスラッシュ ∖(Unicode 0x5C) 、日本語フォントなら 円マーク ¥ (Unicode 0xA5) と明確に区別している場合がある。
私の講義資料では、改行は “¥n” にて見えるはず。入力時には状態によって∖に見えたり¥に見えたりするので、Web画面で表示される時の文字フォントの影響を受けているようだ。
このため、私の講義資料をコピー&ペーストで、∖と¥を明確に区別するエディタに張り付けると、0x5C でなく 0xA5 として扱われることがある。この内容をC言語でコンパイルしてprintf(“Hello World.¥n”);を実行すると、行末で改行されず「Hello World¥n」と表示されることがある。
この資料を書くにあたって、∖と¥をWordPressのエディタで入力しているが、実は∖は「差集合記号」で記載しているし、¥は「全角円マーク」で記載している。