リスト構造でのプログラミング
前回説明した、リスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。
簡単なリスト処理の例
// 全要素を表示する関数 void print( struct List* p ) { for( ; p != NULL ; p = p->next ) printf( "%d " , p->data ) ; printf( "¥n" ) ; } // データ数を返す関数 int count( struct List* p ) { int c = 0 ; for( ; p != NULL ; p = p->next ) c++ ; return c ; } void main() { struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ; print( top ) ; printf( "%d¥n" , count( top ) ) ; }
リスト処理を自分で考えて作成
以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。
// 全要素の合計 int sum( struct List* p ) { // sum( top ) → 888 } // リストの最大値を返す int max( struct List* p ) { // max( top ) → 444 (データ件数0の場合0を返す) } // リストの中から指定した値の場所を返す int find( struct List* p , int key ) { // find( top , 444 ) = 1 (先頭0番目) // 見つからなかったら -1 }
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
void insert( struct List*p , int data ) { // あえて、補助関数consを使わずに書いてみる struct List* n ; n = (struct List*)malloc( sizeof( struct List ) ) ; if ( n != NULL ) { n->data = data ; n->next = p->next ; p->next = n ; } // p->next = cons( data , p->next ) ; }
void remove_after( struct List* p ) { struct List* del = p->next ; p->next = del->next ; free( del ) ; }
再帰呼び出しでリスト処理
リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか?
// 全データを表示 void print( struct List* p ) { if ( p == NULL ) { printf( "¥n" ) ; } else { printf( "%d " , p->data ) ; print( p->next ) ; // 末尾再帰 } } // データ数を返す関数 int count( struct List* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->next ) ; // 末尾再帰 } // 全要素の合計 int sum( struct List* p ) { // sum( top ) → 888 自分で考えよう } // リストの最大値を返す int max( struct List* p ) { // max( top ) → 444 (データ件数0の場合0を返す) 自分で考えよう } // リストの中から指定した値を探す。 int find( struct List* p , int key ) { // find( top , 444 ) = 1 // 見つかったら1 , 見つからなかったら 0 自分で考えよう }
図形と仮想関数の継承方法
純粋仮想基底クラスと図形の課題の基本形
課題で取り組んでいるプログラムは、純粋仮想基底クラスFigureと、そこから派生させたクラスと仮想関数で絵を書いている。このような派生の関係を以下のような図で表現する。
class Figure { public: virtual void draw( int x , int y ) = 0 ; } ; class FigureBox : public Figure { private: int width , height ; public: FigureBox( int w , int h ) : width( w ) , height( h ) {} virtual void draw( int x , int y ) { // 四角を描く処理 } } ; class FigureCircle : public Figure { private: int radius ; public: FigureCircle( int r ) : radius( r ) {} virtual void draw( int x , int w ) { // 円を描く処理 } } ;
色付き図形を派生する方法
課題では、上記プログラムを活用して、色付き図形のクラスを作ることを目的とするが、その実装方法には色々な方法がある。
単純なやり方は、FigureBox と同じように、Figure から FigureColorBox を派生させる方法だろう。
class FigureColorBox : public Figure { private: int width , height , color ; public: FigureColorBox( int w , int h , int c ) : width( w ) , height( h ) , color( c ) {} virtual void draw( int x , int y ) { // 色を変える処理 // 四角を描く処理 ... FIgureBox と同じ処理 } } ;
この方法は単純だけど、四角を描く処理を書くため無駄であり、FIgureBox と処理を共通化できればプログラムを書く手間を減らせるはず。
処理を共通化するなら派生すればいい
class FigureColorBox : public FigureBox { private: int color ; // 幅と高さの記述が無い public: FigureColorBox( int w , int h , int c ) : FigureBox( w , h ) , color( c ) {} virtual void draw( int x , int y ) { // 色を変える処理 FigureBox::draw( x , y ) ; // 親クラスの処理を継承 } } ;
同じような色の処理を追加したクラスが沢山ある場合
上記の、FigureBox から FigureColorBox を派生させた場合は、四角を描く処理が継承により共通化ができた。
しかし、同じように FigureCircle から FigureColorCircle を派生させる…といったクラスを沢山作る場合は、色を変える処理を何度も使うことになるが、処理の共有することができない。こういった場合は、以下のような方法がある。
class Color { private: int color ; public: Color( int c ) : color( c ) {} void set_color() { // 色を変える処理 } } ; class FigureColorBox : public FigureBox , public Color { public: // 多重継承のキモ FigureColorBox( int w , int h , int c ) : FigureBox( w , h ) , Color( c ) {} virtual void draw( int x , int y ) { Color::set_color() ; // Colorクラスを使って色を設定 FigureBox::draw( x , y ) ; // FigureBoxクラスで形を描く } } ;
多重継承
上記の FigureColorBox のように、親クラスとして、FigureBox と Color のように複数のクラスをもつ継承は、多重継承と呼ばれる。
ただし、多重継承は後に示すような曖昧さや、実装の際の手間を考えると、多重継承は必ずしも便利な機能ではない。このため、オブジェクト指向のプログラミング言語によっては、多重継承機能が使えない。
Java では、多重継承が使えない代わりに、interface 機能が使えたりする。
ダイヤモンド型の継承と曖昧さ
C++ のような言語での多重継承が問題となる事例として、ダイヤモンド型の継承が挙げられる。
![]() |
![]() |
例えば、動物クラスから鳥クラス・哺乳類クラスを派生して、鳥クラスからニワトリを派生して、哺乳類クラスから人間を派生するというのは、進化の過程を踏まえると、自然な派生と考えられる。
しかし、鳥がクラスメンバーとして羽と足を持ち、哺乳類が手と足を持つとしたとき、鳥のくちばしを持ち卵を生むカモノハシを派生する場合には、どうすれば良いのだろうか?しかし、これを鳥と哺乳類を親クラスとした多重継承で実装をすると、手と羽と足が4本のカモノハシができてしまう。(お前はドラゴンかッ!)
また、大元の動物クラスがインスタンスを持つ場合、このような多重継承をすると、同じ名前のインスタンスを2つ持つことになる。この場合、C++では仮想継承というメカニズムを使うことができる。
class Animal { private: char name[10] ; } ; class Bird : public virtual Animal { } ; class Mammalian : public virtual Animal { } ; class Psyduck : public Bird , public Mammalian { // このクラスは、name は1つだけ。 } ;
また、動物が動くためのmove()というメソッドを持つとした場合、鳥は羽で飛び、哺乳類は足で移動する処理となるだろう。しかし、多重継承のカモノハシは、鳥の羽で動くメソッドmove()と、哺乳類の足で動くメソッドmove()を持つことになり、カモノハシに動け…と命令した場合、どちらのメソッドmove() を使うのだろうか?
こういった、使いにくさ・実装時の手間・処理の曖昧さを考慮したうえで、多重継承のメカニズムが使えるオブジェクト指向プログラム言語は少ない。
リスト構造について
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。
配列の利点と欠点
今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。
int find( int array[] , int left , int right , int key ) { // データは left から right-1までに入っているとする。 while( left < right ) { int mid = (left + right) / 2 ; // 中央の場所 if ( array[ mid ] == key ) return mid ; // 見つかった else if ( array[ mid ] > key ) right = mid ; // 左半分にある else left = mid + 1 ; // 右半分にある } return -1 ; // 見つからない }
しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。
void entry( int array[] , int* psize , int key ) { // データを入れるべき場所を探す処理 for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、 if ( array[ i ] > key ) // O(log N) でも書けるけど break ; // 単純に記載する。 if ( i < *psize ) { // 要素を1つ後ろにずらす処理 for( int j = *psize ; j > i ; j-- ) // O(N)の処理 array[ j ] = array[ j - 1 ] ; array[ i ] = key ; } else { array[ *psize ] = key ; } (*psize)++ ; }
これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。
この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。
順序が重要なデータ列で途中へのデータ挿入削除
例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。
101 102 103 104 105 106 [ 105 | 106 | -1 | 102 | 104 | 103 ]
このように次のデータの場所という概念を使うと、データの順序を持って扱うことができる。
struct LIST { int data ; int next ; } ; struct LIST array[] = { /*0*/ { 11 , 2 } , /*1*/ { 67 , 3 } , // 末尾にデータ34を加える /*2*/ { 23 , 4 } , // { 23 , 5 } , /*3*/ { 89 , -1 } , // 末尾データの目印 /*4*/ { 45 , 1 } , /*5*/ { 0 , 0 } , // { 34 , 4 } , } ; for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) { printf( "%d¥n" , array[ idx ].data ) ; }
この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。
しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。
リスト構造
リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。
struct List { int data ; struct List* next ; } ; struct List* top ; top = (struct List*)malloc( sizeof( struct List ) ) ; top->data = 111 ; top->next = (struct List*)malloc( sizeof( struct List ) ) ; top->next->data = 222 ; top->next->next = (struct List*)malloc( sizeof( struct List ) ) ; top->next->next->data = 333 ; top->next->next->next = NULL ; // 末尾データの目印 struct List*p ; for( p = top ; p != NULL ; p = p->next ) { printf( "%d¥n" , p->data ) ; }
補助関数
上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。
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 ; } struct List* top ; top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
授業アンケートで板書の字が読みづらいといわれつつも、パッパッパッってコードを書いていると「その関数名読めない…」とツッコミが。cons : constructor の意味ですがな…と話しつつ、例年どおり「どーでもいいウンチク」を話す。
今日以降説明していくリスト構造は、古くから使われていて、LISP というプログラム言語があり、この言語でリスト(セル)を生成する関数が cons 。
LISPと関数型プログラミング言語
LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらい。最初は、人工知能のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。
関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しで書けばいい…。
LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。
前期中間テストの答案返却
前期中間試験の返却と解答の解説を行う。
今年の学生は、3年で私がプログラミング応用を担当していないので、私が例年3年に出題していた以下のような問題が苦手だろうということで、出題した問題。ポインタと構造体と配列が絡む問題は、式の意味を理解するためにも、C言語の演算子の優先順位などを踏まえ、こういった問題を知っておくべき。
また、上記のような問題では、C言語でのポインタと配列の意味を理解してもらうために、例年説明する極端なコーディングも紹介しておいた。
int a[5] = { 11 , 22 , 33 , 44 , 55 } ; int* pi ; pi = a + 2 ; printf( "%d¥n" , *pi ) ; // *( pointer + offset ) printf( "%d¥n" , pi[0] ) ; // と pointer[ offset ] は同じ printf( "%d¥n" , *(pi + 1) ) ; // 44 printf( "%d¥n" , pi[ 1 ] ) ; // 44 printf( "%d¥n" , (-1)[ pi ] ) ; // 22 = *( -1 + pi ) printf( "%c¥n" , "abcdef"[ 2 ] ) ; // c
「 printf( “%d¥n” , -1[ pi ] ) ; 」の結果が -44 になった。一瞬なんでや…って思ったけど、-( 1[pi] ) なのね。
様々な移動平均・レポート-No.3
移動平均のレポートでは、表計算ソフトを用いて、移動平均の範囲のとり方などを変えながら、平均をとった結果に、どう影響するのかを考える。
Excel で様々な移動平均の式を入力
表計算ソフトに、移動平均の式を入力する際には、以下の資料を参考にせよ。
上図のB4〜E4にできた移動平均の式は、B5以下にコピーすればいい。
レポート内容
以下のような移動平均を、Excel にて計算し、その結果の違いについて考察せよ。
移動平均で用いる点の数は、自分の出席番号の3の余りによって、条件を与える。
計算方法 | 出席%3=0 | 出席%3=1 | 出席%3=2 |
---|---|---|---|
単純移動平均(狭) | n=3 | n=4 | n=5 |
単純移動平均(広) | n=6 | n=8 | n=10 |
過去の値による単純移動平均(狭) | n=3 | n=4 | n=5 |
過去の値による単純移動平均(広) | n=6 | n=8 | n=10 |
加重移動平均(狭) | n=3 | n=4 | n=5 |
加重移動平均(広) | n=6 | n=8 | n=10 |
指数移動平均(基本) | α=1/2 | α=1/2 | α=1/2 |
指数移動平均(広) | α=1/3 | α=1/4 | α=1/5 |
平均に用いる値は、以下のデータとする。
-
- 2018-06-05-wave.csv 時刻tとx(t)のコンマ区切りファイル
- 時間の遅延がわかるような波形を用い、考察してあることが望ましい
1枚のグラフの中に、元波形+8波形=9本のグラフを記載すると、グラフの内容が分かりにくいので、複数のグラフ結果で図示すること。
プログラミングが得意な人は、上記をExcelで処理するのではなく、C言語にて移動平均を計算し、結果をExcelに取り込んでグラフとして表示することにチャレンジしてほしい。
提出レポートに、全データの計算結果は不要です。動作の確認の意味で、先頭10点ほどの計算結果をつけてください。
様々な移動平均
波形処理をハードウェアで行うかソフトウェアで行うか
組込み用の小型コンピュータが普及する以前は、このような波形に対する処理を行う場合には、電子回路的に波形のフィルタリングを行っていた。しかし電子回路的な方法では、回路の特性が変化してうまく処理ができなくなった場合に、回路の組み換えが発生するかもしれない。ただし回路の変更は基板の作り直しが必要であったりすることから、コストがかかる。
一方、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 + x[t-2] * 1 ; // 数個の移動平均だし、 y[t] = s / (3+2+1) ; // ループを使わずに書いてみる。 }
この様に、過去に遡るにつれ、平均をとる比重を直線的に小さくしながら移動平均をとる方法は、加重移動平均と呼ばれる。以下にその変化をExcelでシミュレーションしたものを示す。
指数移動平均
ここまで説明してきた、単純移動平均や、加重移動平均は、平均をとる範囲の「過去の値」を記憶しておく必要がある。広い時間にわたる移動平均をとる場合は、それに応じてメモリも必要となる。これは、組み込み型の小型コンピュータであれば、メモリが足りず平均処理ができない場合もでてくる。
そこで、荷重移動平均の重みを、は、100%,
は50%,
は25%… というように、過去に遡るにつれ、半分にして平均をとる。
しかし、以降の項で、
を使うと以下のように書き換えることができる。
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 ; }
高専生の毒舌な妹bot より引用
お兄ちゃん、情報処理基礎のプログラミングはできなくてもいいって、それは専門教科で留年するフラグじゃない?
— 高専生の毒舌な妹bot (@Kosen_Sister) 2018年6月4日
移動平均のプログラム
移動平均のプログラム(ダサっ)
#include <stdio.h> #define WIDTH 5 double xt[1000] ; // 元波形データ double yt[1000] ; // 移動平均処理後のデータ int main() { int i ; double t , x ; // 全データを読み込む(入力はコンマ区切りの2データ) for( i = 0 ; scanf( "%lf,%lf" , &t , &x ) == 2 ; i++ ) xt[ i ] = x ; // データ xt[*] の移動平均を yt[*] に求める。 for( i = WIDTH ; i < 1000 - WIDTH ; i++ ) { int j ; double s = 0.0 ; // 合計 // 前後の値の合計を求める for( j = -WIDTH ; j <= WIDTH ; j++ ) s = s + xt[ i + j ] ; // 合計をデータ数で割る yt[ i ] = s / (WIDTH * 2 + 1) ; } // 処理結果を出力する。 for( i = 0 ; i < 1000 ; i++ ) printf( "%d,%lf,%lf\n" , i , xt[i] , yt[i] ) ; return 0 ; }
でも、このプログラムは、以下の点で問題がある。
- 範囲のデータを加算しているけど、加算の繰り返しが多い。
- 配列にデータを最初に全て読み込んでいるけど、長時間のデータならば大量のメモリが必要。
- 測定しながら移動平均を計算する場合、データはどうする?
移動平均のプログラム(ちょっと改良)
全部のデータを覚えるのはメモリの無駄なので、移動平均する直近のデータだけを覚えるように改良する。
しかし、データを保存する度に、配列をずらす処理も無駄なので、データを保存する場所(以下の例ではbp)を保存したら次の場所を示すように記述してみる。
#include <stdio.h> #define WIDTH 10 double buff[ WIDTH ] ; // 直近のWIDTH個だけ保存 int bp = 0 ; // 最新データの場所 double bs = 0.0 ; // 直近のWIDTH個の合計 int main() { int i ; double t , x ; for( i = 0 ; scanf( "%lf,%lf" , &t , &x ) == 2 ; i++ ) { // WIDTH個前のデータを捨てるために合計から引く bs = bs - buff[ bp ] ; buff[ bp ] = x ; // 最新データを保存 bs = bs + x ; // 最新のデータで合計 // 直近のデータを覚える場所を移動 bp++ ; if ( bp >= WIDTH ) bp = 0 ; // 移動平均を出力 printf( "%d %lf\n" , i , bs / WIDTH ) ; } return 0 ; }
仮想関数
仮想関数
前回の派生したプログラムで継承の説明をしたが、以下のようなプログラムでは、Student 型が混在した family[] の配列でも、Person へのポインタに「格下げ」されて保存されているため、
family[i]->print() では、Student 型でも Person型で表示処理が行われる。
class Student : public Person { : void print() { Person::print() ; // 名前と年齢を表示 printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示 } } ; void main() { Person saitoh( "t-saitoh" , 53 ) ; saitoh.print() ; // t-saitoh 53 Student mitsu( "mitsuki" , 18 , "E" , 4 ) ; Student ayuka( "ayuka" , 16 , "EI" , 2 ) ; mitsu.print() ; // mitsuki 18 / E 4 名前,年齢,所属,学年を表示 ayuka.print() ; // ayuka 16 / EI 2 名前,年齢,所属,学年を表示 Person* family[] = { &saitoh , &mitsu , &ayuka , // 配列の中に、Personへのポインタと } ; // Studentへのポインタが混在している // 派生クラスのポインタは、 // 基底クラスのポインタとしても扱える for( int i = 0 ; i < 3 ; i++ ) family[ i ]->print() ; // t-saitoh 53/mitsuki 18/ayuka 16 } // が表示される。
しかし、Student型とPerson型の機能を活かせないだろうか?
仮想関数
このような場合、オブジェクト指向では、仮想関数の機能が便利である。
class Person { : virtual void print() { printf( "%s %d\n" , name , age ) ; } } ; class Student : public Person { : virtual void print() { Person::print() ; // 名前と年齢を表示 printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示 } } ; void main() { Person saitoh( "t-saitoh" , 53 ) ; saitoh.print() ; // t-saitoh 53 Student mitsu( "mitsuki" , 18 , "E" , 4 ) ; Student ayuka( "ayuka" , 16 , "EI" , 2 ) ; mitsu.print() ; // mitsuki 18 / E 4 名前,年齢,所属,学年を表示 ayuka.print() ; // ayuka 16 / EI 2 名前,年齢,所属,学年を表示 Person* family[] = { &saitoh , &mitsu , &ayuka , } ; for( int i = 0 ; i < 3 ; i++ ) family[ i ]->print() ; // t-saitoh 53/mitsuki 18,E 4/ayuka 16,EI 2 }
仮想関数が宣言されると、基底クラスの中に「型情報(PersonなのかStudentなのか)」が自動的に埋め込まれる。仮想関数を呼び出すと、型情報を使って、Person::print()を呼び出すか、Student::print()を呼び出すか、を選んでくれる。
仮想関数が生まれた背景
仮想関数は、GUI のプログラム記述に向いていた。例えば、GUIシステムでは、画面にデータを表示するための基本型として、座標と幅,高さの情報を持つ Window 型がある。
また、画面のアイコンは、Window型に、表示する絵の画像を追加した派生クラス WindowIcon 型、画面のテキストは、Windows型に、表示するテキストやフォント情報を持った、WindowText といった型のようなものとする。そうなると仮想関数の概念が無いと、display() を呼び出すためには、派生型の種類が大量ならばデータの型に応じた if 文を大量に書き並べないといけないし、データ型を区別するための情報(下記の例ならばtype)に、型毎に異なるマジックナンバーを埋め込む処理を自分で書かないといけない。
class Window { // 概念を説明するための例にすぎない private: int x , y , w , h ; int type ; // 型を区別するための情報 public: void display() { // 表示する処理 } } ; class WindowIcon : public Window { private: Image img ; public: void display() { // 画像を表示する処理 } } ; class WindowText : public Window { private: Font font ; char* text ; public: void display() { // テキストを表示する処理 } } ; void main() { WindowIcon wi( アイコンのコンストラクタ ) ; WindowText wt( テキストのコンストラクタ ) ; Window* wins[] = { &wi , &wt , ... } ; for( int i = 0 ; i < 配列すべて ; i++ ) { if ( wins[i]->type が アイコンならば ) wins[i]->display() ; // アイコンを表示する else if ( wins[ i ]->type が テキストならば ) wins[i]->display() ; // テキストを表示する。 else if .... : } }
関数ポインタ
では、仮想関数はどのようなテクニックを用いて実装されているのだろうか?
これには、関数ポインタが用いられる。
int add( int x , int y ) { return x + y ; } int mul( int x , int y ) { return x * y ; } int main() { int (*func)( int , int ) ; func = add ; // add() ではない printf( "%d¥n" , (*func)( 3 , 4 ) ) ; // 7 func = mul ; printf( "%d¥n" , (*func)( 3 , 4 ) ) ; // 12 return 0 ; }
仮想関数を用いると、基底クラスにはクラス毎の仮想関数への「関数ポインタ」などの型情報を保存する場所が自動的に作られ、基底クラス・派生クラスが使われると、そのオブジェクト毎に型情報を初期化する処理が行われる。仮想関数が呼び出されると、関数ポインタにより、各型毎のメソッドが呼び出されるため、大量の if 文は不要となる。
純粋仮想基底クラス
// 純粋仮想基底クラス class Object { public: virtual void print() = 0 ; // 中身の無い純粋基底クラスを記述しない時の書き方。 } ; // 整数データの派生クラス class IntObject : public Object { private: int data ; public: IntObject( int x ) { data = x ; } virtual void print() { printf( "%d\n" , data ) ; } } ; // 文字列の派生クラス class StringObject : public Object { private: char data[ 100 ] ; public: StringObject( const char* s ) { strcpy( data , s ) ; } virtual void print() { printf( "%s\n" , data ) ; } } ; // 実数の派生クラス class DoubleObject : public Object { private: double data ; public: DoubleObject( double x ) { data = x ; } virtual void print() { printf( "%lf\n" , data ) ; } } ; // 動作確認 int main() { Object* data[3] = { new IntObject( 123 ) , new StringObject( "abc" ) , new DoubleObject( 1.23 ) , } ; for( int i = 0 ; i < 3 ; i++ ) { data[i]->print() ; } return 0 ; } ;
この書き方では、data[]には、整数、文字列、実数という異なるデータが入っているが、 Objectという純粋仮想基底クラスを通して、共通な型のように扱えるようになる。 そして、data[i]->print() では、各型の仮想関数が呼び出されるため、 「123 abc 1.23」 が表示される。
ここで、Object の様な一見すると中身が何もないクラスを宣言し、 このクラスから様々な派生クラスを用いるプログラムテクニックは、 広く利用され、Objectのような基底クラスは、純粋仮想基底クラスなどと呼ばれる。
移動平均の処理
前回の授業で説明したようなA/D変換した数値データを読み取った場合、どのようなことが発生するか考える。
例えば、以下に示すような測定値があったとする。
このデータの一部をグラフ化してみると、次のような波形であった。
この波形をみると、大きく見ればsinカーブだが、細かい点を見るとデータにブレがある。
誤差の原因
このような測定結果が得られた場合、本来コンピュータで処理したいデータは何であろうか?
原因は様々なものが考えられるが、
(1) 回路のノイズ対策が不十分で、外部の電気的な影響が混入してしまうこともある。
(2) 一方で、D/A 変換を行う場合には、量子化誤差もある。
青線:元波形、赤線:4段階で量子化
この例は、-1〜1の範囲を、4段階に量子化することで、本来の波形とは異なった値になっている。
例えば、最初の波形が、加速度センサーの値であったとして、船の上で揺れているために、大きな周期で加速度が変化しているかもしれない。一方で、船自体がエンジンによる揺れで加速度が変化しているかもしれない。
船の中で波の揺れと、エンジンの揺れが観測されている加速度センサーの情報で、船の揺れの大きさ・揺れの周期を知りたい場合、どうすればいいだろうか?単純なsinカーブの波形であれば、波形の最大値・最小値・0との交点の場所を探せば、振幅や周期が求めることができるが、このようなノイズが入った波形では、正しく振幅・周期が求まらない。
移動平均
このデータを見ると、10個のデータまでの間で、波形が上下に変動している。船の揺れとエンジンの揺れが原因であれば、10個ぐらいのデータのゆらぎが、エンジンによる揺れと考えられる。では、この10個ぐらいの範囲で値が上下の影響を減らしたければ、どうすればいいか?一番簡単な方法は、前後10個のデータで平均を取ればいいだろう。まずは、Excel で前後データの平均をとってみよう。
Excelで前後11点の平均を求める式をセルに入れる
青線:元波形データ(B列)、赤線:前後11点の平均(C列)
このように、データの前後の決められた範囲の平均を平均する処理は、移動平均(単純移動平均)と呼ぶ。
時間tにおけるデータをとした場合、前後5点の移動平均
は、以下のような式で表せるだろう。
自宅学習の課題(レポート提出は不要)
表計算ソフトで、移動平均を計算させてみよう。 ※
- 元波形
- 前後5点で移動平均
- 前後11点で移動平均
- 前後51点で移動平均
をとるような表計算の式を書き込んで、その結果の波形がどんなグラフになるのか確認しておくこと。
移動平均の応用
例えば、以下のような心電図のデータがあったとする。心電図では、波の高さで心臓が正常か判断するが、この青のグラフでは、大きな周期の変動が含まれるため、波の高さを正確に測れない。この波形から診断するときに、移動平均が使えないだろうか?
このような場合には、測定値の波形の移動平均をとり心拍データの変動を取り除き、測定値から移動平均の値を引くことで、心拍データだけを取り出すことが可能となる。