ホーム » 2020 » 7月 » 30

日別アーカイブ: 2020年7月30日

2020年7月
 1234
567891011
12131415161718
19202122232425
262728293031  

検索・リンク

集合とリスト処理

リストを用いた待ち行列の補足

# リストによる待ち行列を早速に創造工学演習で応用した人からの質問より…

以前に説明したリストを用いた待ち行列(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 ;
}

理解度確認のための小レポート

上記の移動平均の理解のために、以下の資料(講義では印刷資料を配布)の表の中を、電卓などを使って計算せよ。
計算したら、その結果をグラフの中にプロットし、どういった波形となるか確認し、レポートとして提出すること。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー