ホーム » スタッフ » 斉藤徹

斉藤徹」カテゴリーアーカイブ

2022年6月
 1234
567891011
12131415161718
19202122232425
2627282930  

最新の投稿(電子情報)

アーカイブ

カテゴリー

表計算ソフトの使い方(絶対参照・相対参照)

前回課題の答え合わせ

前回のレポートでは、sin(83度)(例)といった数値の有効数字を考えるというものを考えてもらったので、この有効数字をどう記載すべきか考えてみる。

課題を示す Excel ファイルでは、75度~89度あたりの角度で出題をするようにしてあった。注意しないといけない点は、sinは90度に近づくほど、1に近づく。このため、0.99…といった数値が求まるが、角度がちょっと変化しても、0.99といった部分はほぼ変化しない。だから、83が有効数字2桁ということで、0.99 といった有効数字2桁の書き方では、ちょっと不十分かもしれない。

そこで、83度(有効数字2桁)が小数点以下を丸められた数値と仮定する。この場合、元の数値は 82.5度~83.5度 の可能性がある。これらの値のsinを計算すると、0.9914から0.9935の間であり、小数点以下3桁目は、1~3 の値であり、結果を 0.992 (有効数字3桁) と記載しても良いかもしれない。

 sin(82.5°) = 0.991444861
 sin(83.0°) = 0.992546152
 sin(83.5°) = 0.993571856

表計算ソフトの使い方

情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。

セルの場所と簡単な式

簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。

Excel では、表のには左から、A,B,C,D… , 表のには上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に¥80、C5に4 が入っている。

例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、

=B2*C2

を書き込めば、その場所には360が表示される。

Excelでは、入力する文字列の先頭が”=”の場合は、残り部分は計算式として扱われる。

D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。

この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。

ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)

関数式

例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー&ペーストし、A3,B3 を A4~A6にペーストすればいい。

B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。

また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。

絶対参照と相対参照

最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。

この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。

ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。

こういった場合には、絶対参照を用いる。D3 に記入する式を

=B3*C3*(1+$B$2)

とし、この D3 の式を D4 にコピー&ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。

このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。

絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時にF4ボタンを押す度に、B2$B$2B$2$B2B2 と変化する

$B2 は、式をコピーすると列部分はBのまま行部分は場所に合わせて変化する。

B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。

レポート課題(第5回)

Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。この時、計算式の入力をどのように行なったのか(相対参照や絶対参照をどのように使ったのか)説明を、グラフの下に入力欄を設け記入せよ。

そして出来上がった Excel のファイルを、Teams のこちらのフォルダに提出せよ。

 

多重継承の問題

派生や継承について、一通りの説明が終わったので、最後に特殊な継承の問題を説明し、2回目のレポート課題を示す。

動物・鳥類・哺乳類クラス

派生や継承を使うと、親子関係のあるデータ構造をうまく表現できることを、ここまでの授業で示してきた。

しかしながら、以下に述べるような例では、問題が発生する。

// 動物クラス
class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
  virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public Animal {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s fry.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

// 哺乳類クラス
class Mammal : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay baby.\n" , get_name() ) ;
  }
} ;

int main() {
  Bird chiken( "piyo" ) ;
  chiken.move() ;
  chiken.birth() ;
  Mammal cat( "tama" ) ;
  cat.move() ;
  cat.birth() ;
  return 0 ;
}

ここで、カモノハシを作るのであれば、どうすれば良いだろうか?

鳥類・哺乳類とは別にカモノハシを作る

class SeaBream : public Animal {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s walk.\n" , get_name() ) ;
  }
  virtual void birth() {
    printf( "%s lay egg.\n" , get_name() ) ;
  }
} ;

この例では、簡単な処理だが、move() の中身が複雑であれば、改めて move() を宣言するのではなく、継承するだけの書き方ができないだろうか?

多重継承

C++ には、複数のクラスから、派生する多重継承という機能がある。であれば、鳥類と哺乳類から進化したのだから、以下のように書きたい。

class SeaBream : public Bird , Mammal {
} ;

しかし、カモノハシに move() を呼び出すと、鳥類の move() と哺乳類の move() のどちらを動かすか曖昧になる。また、派生クラスは親クラスのデータ領域と、派生クラスのデータ領域を持つため、鳥類の name[] と、哺乳類の name[] を二つ持つことになる。

足と羽のクラスを作る場合

class Animal {
private:
  char name[ 10 ] ;
public:
  Animal( const char s[] ) {
    strcpy( name , s ) ;
  }
  const char* get_name() const { return name ; }
  virtual void move() = 0 ;
} ;
// 羽
class Wing {
public:
   const char* move_method() { return "fly" ; }
} ;
// 
class Leg {
public:
   const char* move_method() { return "walk" ; }
} ;
class Bird : public Animal , Wind {
public:
  Bird( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;
class Mammal : public Animal , Leg {
public:
  Mammal( const char s[] ) : Animal( s ) {}
  virtual void move() {
    printf( "%s %s.\n" , get_name() , move_method() ) ;
  }
} ;

C++では、以下のような方法で、ダイヤモンド型の継承問題を解決できる。

class Animal {
private:
   char name[ 10 ] ;
public:
   Animal( const char s[] ) {
      strcpy( name , s ) ;
   }
   const char* get_name() const { return name ; }
   virtual void move() = 0 ;
   virtual void birth() = 0 ;
} ;

// 鳥類クラス
class Bird : public virtual Animal {
public:
   Bird( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s fry.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay egg.\n" , get_name() ) ;
   }
} ;

// 哺乳類クラス
class Mammal : public virtual Animal {
public:
   Mammal( const char s[] ) : Animal( s ) {}
   virtual void move() {
      printf( "%s walk.\n" , get_name() ) ;
   }
   virtual void birth() {
      printf( "%s lay baby.\n" , get_name() ) ;
   }
} ;

class SeaBream : public virtual Bird , virtual Mammal {
public:
   SeaBream( const char s[] ) : Animal( s ) {}
   void move() {
      Mammal::move() ;
   }
   void birth() {
      Bird::birth() ;
   }
} ;

ただし、多重継承は親クラスの情報と、メソッドを継承する。この場合、通常だと name[] を二つ持つことになるので、問題が発生する。そこで、親クラスの継承に virtual を指定することで、ダイヤモンド型継承の 2つの属性をうまく処理してくれるようになる。

しかし、多重継承は処理の曖昧さや効率の悪さもあることから、採用されていないオブジェクト指向言語も多い。特に Java は、多重継承を使えない。その代わりに interface という機能が使えるようになっている。

リスト構造の導入

データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造の導入の説明を行う。

配列の利点と欠点

今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。しかし、配列には苦手な処理がある。

例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。処理に要する時間としては となる。

// この関数は見つかったら、見つかった場所、見つからない場合は -1 を返す。
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 ; // 見つからない
}

int a[] = { 12 , 34 , 41 , 53 , 62 , 79 , 80 } ;
int main() {
   int ans = find( a , 0 , 7 , 62 ) ; // 配列 a[] から 62 を探す
   printf( "%d¥n" , ans ) ;           // 4が表示される
   return 0 ;
}

しかし、この配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。

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つ後ろにずらす処理(A)
      for( int j = *psize ; j > i ; j-- ) //  O(N)の処理
         array[ j ] = array[ j - 1 ] ;
      array[ i ] = key ; 
   } else {
      array[ *psize ] = key ;
   }
   (*psize)++ ;
}
   /// よくある間違い ///
   /// 上記処理の(A)の部分を以下のように記載した ///
   /// 問題点はなにか答えよ ///
   //   for( int j = i ; j < size ; j++ )
   //      array[ j + 1 ] = array[ j ] ;
   //   array[ i ] = key ;

int main() {
   int a[ 100 ] ;
   int size = 0 ;
   int x ;
   // 入力された値を登録していく繰り返し処理
   while( scanf( "%d" , &x ) == 1 ) {
      // x を追加する。
      entry( a , &size , x ) ;
   }
   return 0 ;
}

これで判るように、昇順に並んだ配列にデータを追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。

この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。

このことから、昇順に並べられた配列は、データの追加処理の発生頻度が少ない場合は2分探索法で効率が良いが、データの追加や削除が頻繁に発生する時はあまり効率が良くない。

順序が重要なデータ列で途中へのデータ挿入削除を高速化

例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
以下の説明のような方法であれば、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、スムーズに回覧板を回すことができる。

  101   102   103   104   105   106   アパートの番号
[ 105 | 106 |  -1 | 102 | 104 | 103 ] 回覧板を回す次の人の部屋番号

101号室の次は、105号室、
105号室の次は、104号室、
  :
106号室の次は、103号室、
103号室の次は、おしまい(-1)

このように「次のデータの場所」という概念を使うと、データの順序を持って扱うことができる。これをプログラムにしてみよう。

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 } ,
} ;

int main() {
   for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
      printf( "%d¥n" , array[ idx ].data ) ; 
   }
   return 0 ;
}

この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。(O(N)の処理が発生しない)

しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。そこで、必要に応じてメモリを確保するテクニックを導入する。

複素数クラスでre-imとr-thのコンストラクタ

複素数クラスの課題で、直交座標系のコンストラクタと曲座標系のコンストラクタを作りたいとの質問。でも、以下のようなコンストラクタでは、どちらも Complex( double , double ) であり、区別できない。

class Complex {
private:
    double re , im ;
public:
    Complex( double x , double y ) // コンストラクタ
      : re( x ) , im( y ) {}
    Complex( double r , double th )
      // Complex(double,double)では直交座標系のコンストラクタと区別できない。
      : re( r * cos( th ) ) , im( r * sin( th ) ) {}
    // Complex( double r , double th ) { // これもダメ...
    //     return Complex( r * cos(th) , r * sin(th) ) ;
    // }

    // static は、静的メンバ関数(オブジェクトに対してのメソッドではない)
    static Complex complex_rth( double r , double th ) {
        return Complex( r * cos(th) , r * sin(th) ) ;
    }
} ;

int main() {
    Complex a( 1.0 , 1.0 ) ;
    Complex b = Complex::complex_rth( 1 , 45.0/180.0*3.14 ) ;
    a.print() ; 
    b.print() ;
    return 0 ;
}

色々な書き方はあると思うけど、static Complex Complex::complex_rth( double r , double th ) ; を宣言するのが自然かな…と思ったけど、初期化が Complex a = Complex::complex_rth( 1 , 2 ) ; みたいに書くことになってちょっとダサい。”Complex::” のクラス限定子が邪魔っぽいけど、関数の名前空間を不必要に使わないという意味ではいいのかもしれないが。 C++ の complex クラスを見たら、以下のように使えるようになっていた。なるほど。

class Complex {
private:
    double re , im ;
public:
    Complex( double x , double y ) : re( x ) , im( y ) {}
    void print() const { printf( "%lf+j%lf\n" , re , im ) ; }
} ;

// 曲座標系のコンストラクタ? (正確に言えばコンストラクタではない)
inline Complex polar( double r , double th ) {
    return Complex( r * cos( th ) , r * sin( th ) ) ;
} ;

int main() {
    Complex a( 1 , 2 ) ;
    Complex b = polar( 3 , 30.0 / 180.0 * 3.141592 ) ;
    Complex c( polar( 3 , 30.0 / 180.0 * 3.141592 ) ) ;
      // こっちの書き方の方がコンストラクタを使ってるっぽく見える。
      // デフォルトコピーコンストラクタが使われている。
    a.print() ;
    b.print() ;
    c.print() ;
    return 0 ;
}

様々なデータの覚え方のレポート課題

前回の malloc() + free() の資料で、様々なデータ構造の覚え方の例やメモリイメージを説明し、前期中間のレポート課題を示す。

malloc+freeの振り返り

// 文字列(可変長)の保存
char  str[] = "ABCDE" ;
char* pc ;
pc = (char*)malloc( strlen( str ) + 1 ) ;
if ( pc != NULL ) { // ↑正確に書くと sizeof( char ) * (strlen(str)+1)
   strcpy( pc , str ) ;
   ////////////////////
   // pcを使った処理
   ////////////////////
   free( pc ) ;
}
//
// 可変長の配列の保存
int  data[] = { 11 , 22 , 33 } ;
int* pi ;
pi = (int*)malloc( sizeof( int ) * 3 ) ;
if ( pi != NULL ) {
   for( int i = 0 ; i < 3 ; i++ )
      pi[ i ] = data[ i ] ;
   ////////////////////
   // piを使った処理
   ////////////////////
   free( pi ) ;
}
//
// 1件の構造体の保存
struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person* pPsn ;
pPsn = (struct Person*)malloc( sizeof( struct Person ) ) ;
if ( pPsn != NULL ) {
   strcpy( pPsn->name , "t-saitoh" ) ;
   pPsn->age = 55 ;
   ////////////////////
   // pPsnを使った処理
   ////////////////////
   free( pPsn ) ;
}

安全な1行1件のデータ入力

C言語では、scanf などの関数は、バッファオーバーフローなどの危険性があるため、以下のような処理を使うことが多い。fgets は、指定されたファイルから1行分のデータを読み込む。sscanf は、文字列のなかから、scanf() と同じようなフォーマット指定でデータを読み込む。

fgets は、これ以上の入力データが無い場合には、NULL を返す。
(Windowsであれば、キー入力でCtrl+Z を入力、macOSやLinuxであれば、Ctrl+Dを入力で終了)

sscanf() は、読み込めたデータ件数を返す。

int main() {
   char buff[ 1024 ] ;
   for( int i = 0 ; i < 3 ; i++ ) {
      if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
         char name[ 1024 ] ;
         int  age ;
         if ( sscanf( buff , "%s%d" , name , &age ) == 2 ) {
            // 名前と年齢の2つのデータが正しく読み込めたとき
            ...
         }
      }
   }
   return 0 ;
}

様々なデータの覚え方

配列サイズ固定・名前が固定長

例えば、このデータ構造であれば、table1[] の場合、長い名前にある程度対応できるように nameの配列を100byteにしたりすると、データ件数が少ない場合には、メモリの無駄も多い。

そこで、実際に入力された存在するデータだけをポインタで覚える方法 table2[] という保存方法も考えられる。

// 固定長データのプログラム
#define SIZE 50

// 名前(固定長)と年齢の構造体
struct NameAge {
   char name[ 32 ] ;
   int  age ;
} ;
struct NameAge table1[ SIZE ] ;
int    size1 = 0 ;

void entry1( char s[] , int a ) {
   strcpy( table1[ size1 ].name , s ) ;
   table1[ size1 ].age = a ;
   size1++ ; 
}
// ポインタで覚える場合
struct NameAge* table2[ SIZE ] ;
int    size2 = 0 ;

void entry2( char s[] , int a ) {
   table2[size2] = (struct NameAge*)malloc( sizeof( struct NameAge ) ) ;
   if ( table2[size2] != NULL ) {  // なぜ != NULL のチェックを行うのか、説明せよ
      strcpy( table2[size2]->name , s ) ;
      table2[size2]->age = a ;
      size2++ ;
   }
}
// データ出力
void print_NA( struct NameAge* p ) {
   printf( "%s %d¥n" , p->name , p->age ) ;
}
int main() {
   // table1に保存
   entry1( "t-saitoh" , 55 ) ;
   entry1( "tomoko" ,   44 ) ;
   print_NA( &table1[0] ) ;
   print_NA( &table1[1] ) ;
   // table2に保存
   entry2( "t-saitoh" , 55 ) ;
   entry2( "tomoko" , 44 ) ;
   print_NA( _________________ ) ;  // table2の中身を表示せよ
   print_NA( _________________ ) ;
   return 0 ;
}

配列サイズ固定・名前が可変長

しかしながら、前回の授業で説明したように、際限なく長い名前があるのであれば、以下の様に名前は、ポインタで保存し、データを保存する時に strdup(…) を使って保存する方法もあるだろう。

// 名前が可変長のプログラム

// 名前(固定長)と年齢の構造体
struct NamePAge {
   char* name ;  // ポインタで保存
   int   age ;
} ;
struct NamePAge table3[ SIZE ] ;
int    size3 = 0 ;

void entry3( char s[] , int a ) {
   table3[ size3 ].name = strdup( s ) ;  // ★★★★
   table3[ size3 ].age = a ;
   size3++ ; 
}
// ポインタで覚える場合
struct NamePAge* table4[ SIZE ] ;
int    size4 = 0 ;

void entry4( char s[] , int a ) {
   table4[size4] = (struct NamePAge*)malloc( ____________________ ) ;
   if ( table4[size4] != NULL ) {            // ↑適切に穴埋めせよ
      table4[size4]->name = strdup( s ) ; // ★★★★
      _________________________________ ; // ←適切に穴埋めせよ
      size4++ ;
   }
}
// データ出力
void print_NPA( struct NameAge* p ) {
   printf( "%s %d¥n" , ____________ , ____________ ) ;
}                      // ↑適切に穴埋めせよ
int main() {
   // table3に保存
   entry3( "t-saitoh" , 55 ) ;
   entry3( "jyugemu jyugemu ..." ,   44 ) ;
   print_NPA( _________________ ) ;  // table3[] の中身を表示せよ。
   print_NPA( _________________ ) ; 
   // table4に保存
   entry4( "t-saitoh" , 55 ) ;
   entry4( "jyugemu jyugemu ..." , 44 ) ;
   print_NPA( table4[0] ) ;
   print_NPA( table4[1] ) ; 
   return 0 ;
}

データ件数が可変長ならば

前述のプログラムでは、データ件数全体は、SIZE という固定サイズを想定していた。しかしながら、データ件数自体も数十件かもしれないし、数万件かもしれないのなら、配列のサイズを可変長にする必要がある。

struct NamePAge* table5 ;
int    size5 = 0 ;

void entry5( char s[] , int a ) {
   strcpy( table5[ size5 ].name , s ) ;
   table5[ size5 ].age = a ;
   size5++ ; 
}

int main() {
   // table5に保存
   table5 = (struct NameAge*)malloc( sizeof( struct NameAge ) * 2 ) ;
   if ( table5 != NULL ) {
      entry5( "t-saitoh" , 55 ) ;
      entry5( "tomoko" ,   44 ) ;
   }
   return 0 ;
}

メモリの管理に十分気を付ける必要があるが、名前の長さも配列全体のサイズも可変長であれば、以下のようなイメージ図のデータを作る必要があるだろう。(JavaScriptやJavaといった言語ではデータのほとんどがこういったポインタで管理されている)

レポート課題

授業での malloc , free を使ったプログラミングを踏まえ、以下のレポートを作成せよ。

以下のデータのどれか1つについて、データを入力し、何らかの処理を行うこと。
課題は、原則として、(自分の出席番号%3)+1 についてチャレンジすること。

  1. 名前と電話番号
  2. 名前と身長・体重
  3. 名前と生年月日

このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。

名前は、長い名前の人が混ざっているかもしれない。
保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)

ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。

レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。

考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。

ネットワークとセキュリティ

ネットワークからの攻撃とFireWall

脆弱性とバッファオーバーフロー

プログラムには、何らかのバグが潜んでいる可能性があり、悪用すると悪意のプログラムの実行や、情報の漏えい、システム異常を発生させサービスができなくするなどの脆弱性があって、悪意のある利用者から攻撃をうける可能性がある。

例えば、下記のようなC言語のプログラムは、配列をはみ出るようなデータを与えることで、関数の戻り番地を破壊させ、はみ出た部分に送り込んだ悪意のプログラムを実行させることが可能となる。このような入力用のデータ領域(バッファ)をはみ出させる攻撃はバッファオーバーフローと呼ばれる。

ルータとFireWall

外部にサービスを提供するようなシステムで、何らかの脆弱性のあるプログラムが使われていると、外部からのネットワーク接続で悪意のあるプログラム(マルウェア)を実行させられてしまうかもしれない。

このため、コンピュータでは不必要なプログラム(ネットワークサービス)は、起動されないようにする必要がある。もしくは、そのサービスは外部から利用できないように、途中のルータで FireWall(防火壁) を設置する。

FireWall では、(1)攻撃の可能性のあるIPアドレスからの接続を拒否、(2)外部に公開していないネットワークサービスのポート番号の接続を拒否といった方法をとる(拒否リスト方式)。もっと厳しい対策であれば、(3)特定のIPアドレスの機器からのみ接続を許可、(4)許可されているネットワークサービスのポート番号だけからだけ許可する方式をとる(許可リスト方式)

外部に公開する必要のないサービスがFireWallなどで正しく保護されていないと、攻撃をうける可能性がある。

ネットワーク接続のための装置

ルータやFireWallなどの仕組みをもう少し理解するために、組織内でネットワークを接続するための機器とその機能について改めて確認する。

ルータとは

元々の有線LANでは、1本のケーブルを時分割多重で共有しながら通信を行う。このため、瞬間的にはとある機器がネットワークを使用している時は、他の機器はデータ通信ができなくなる。この1本の線を大量の機器で使おうとすると、機器が使えるタイミングは減ってしまう。そこで、1本の線に直接接続する機器を分割したサブネットに分けて、必要な時だけ隣接するサブネットにパケットを中継するルータ or ブリッジが重要となる。

ルータは、隣接するサブネットのネットワーク番号(IPアドレスとサブネットマスク)を確認し、パケットを流す先を決定する。このネットワーク番号(IPアドレスとサブネットマスクの論理積)と中継を依頼するゲートウェイ(転送先)の一覧をルーティングテーブルと呼ぶ。

組織内のルータであれば、ネットワークの構造に合わせてあらかじめルーティングテーブルを定義しておく(静的ルーティング)。組織と組織を接続するようなルータは、自分に送ってほしいネットワーク番号の情報を相互に交換している(動的ルーティング)

ブリッジとHUB

ネットワークを接続するための機器には、ブリッジHUBが使われていた。

スイッチングHUB

機器を接続するための古いHUB(ダムHUB)では、通信中は他の機器の通信ができず効率が悪い。最近のHUBでは、通信する相手に応じて、内部のネットワークケーブルをスイッチのように接続・分離することができるスイッチングHUBを用いる。通信相手の識別には、一般的にMACアドレスが用いられる。(レイヤ2でのスイッチングHUB)

家庭用のスイッチングHUBは、特に細かい設定などは不要で管理機能が無いものは、アン マネージド スイッチングHUBと呼ばれる。

L2スイッチとL3スイッチ

サブネットに分割し、それぞれに異なるネットワーク番号を割り振り、中継するルータで FireWall を機能させることで、セキュリティを高めることが行われる。しかし、性能の高いスイッチングHUBは高価でもあり、1つのHUBに異なるネットワークを接続する必要がでてくることもある。この場合、IPアドレスを異なるネットワークの番号を偽装されると、データが盗み見られるかもしれない。

こういった相互に分離すべきネットワークであっても、柔軟なネットワーク構成とするためには、VLAN機能を持った L2スイッチ(レイヤ2スイッチングHUB) が使われる。タグVLAN機能付きのL2スイッチでは、特定のポートにVLANのタグ番号を割り当て、ポートに入る時にパケットに VLAN のタグ情報を付加し、そのパケットは同じ VLAN のタグをもつポートからしかデータを取り出せない。

L2スイッチ(レイヤ2スイッチ)は、機器のMACアドレスやパケットに付けられたVLANのタグ番号の情報(レイヤ2=データリンク層)でパケットの流れを制御している(下記OSI参照モデルの表を参照)。最近では、許可されていない機器がネットワークに侵入する不正侵入を防ぐために、登録されていないMACアドレスのパケットを通さないといった機能がある。

OSI参照モデルとレイヤ
第7層 アプリケーション層 アプリケーションの種類の規定
第6層 プレゼンテーション層 データフォーマットの交換
第5層 セッション層 コネクションの確立や切断などの管理
第4層 トランスポート層 パケットの分割合成や再送といった管理(TCP)
第3層 ネットワーク層 隣接するネットワーク間の通信(IPアドレス)
第2層 データリンク層 直接接続された機器間の通信(MACアドレス)
第1層 物理層 物理的な接続方法(コネクタや電圧など)

スイッチングHUBの中には、レイヤ3(IPアドレス)の情報でパケットの流れを制御するものもある。こういったスイッチは、L3スイッチ(レイヤ3スイッチ)と呼ばれるが、機能的にはルータと同じである。

一般的には、LANとWANを接続するための機器はルータ、LAN内部のネットワークを分離するためのものはL3スイッチと呼ぶ。

インターネットと接続するルータの機能

ネットワーク通信のIPアドレスとポート番号

クライアントの機器と通信相手との通信では、通信相手のIPアドレスとポート番号を指定してパケットを送出するが、処理結果を送信元に送り返すために、送信元のIPアドレスとポート番号が付加されている。送信元ではポート番号は、通信でよく使われる0~1023までのポート番号(ウェルノウンポート)以外で、1024~65535のポート番号(エフェメラルポート)の中から使われていないものをランダムに選んで使う。

送信相手に届いたパケットの返信データには、送信元と送信相手のIPアドレスとポート番号を入れ替えたものを割り当てることで、送信元にパケットが戻ってくる。

  • DIP = 送信先IPアドレス、DP = 送信先ポート番号
  • SIP = 送信元IPアドレス、SP = 送信元ポート番号

NAT(Network Address Translation)

現在広く使われているIPv4アドレス(32bit)では、40億台の機器間の通信しかできない。このため、組織内だけで使われるIPアドレス(プライベートIPアドレス)を使い、インターネットではグローバルIPアドレスを使う。

プライベートIPアドレス
クラスA/8 10.0.0.0~10.255.255.255 大規模組織向け
クラスB/12 172.16.0.0~172.31.255.255 中規模組織向け
クラスC/16 192.168.0.0~192.168.255.255 家庭用ルータ向け

組織内のLANからインターネット(WAN)に接続する際には、プライベートアドレスをグローバルアドレスに変換するNAT(Network Address Translation)の機能が使われる。

NATの問題点

しかし、インターネットの内側で異なる機器で同じポート番号が割り振られると、戻ってきたパケットをどちらの機器に送ればいいのか区別できなくなる。

NAPT(Netowrk Address and Port Translation)

そこで、最近のNATでは、IPアドレスの変換だけでなくポート番号の付け替えも行われる。この機能は正式には NAPT(Network Address and Port Translation) と呼ぶが、単に NAT と呼ぶことも多い。Linuxでは、NAPTの実装をIPマスカレードと呼ぶ。

FireWall と DMZ

組織内で外部に公開しているサーバがある場合は、以下の図のような構成にするかもしれない。しかし、このようなネットワーク構成では、FireWallの内側の公開サーバが攻撃されて、踏み台となった場合、組織内のPCが簡単に攻撃をうけてしまう。

そこで、外部からの接続を行う DMZ(De-Militarized Zone 非武装地帯) を設け、外部公開用の公開サーバは DMZ 内に設置する。外部とつながる FireWall では、外部からのパケットは DMZ に流れるように構成する。DMZ 内のサーバが踏み台になった場合を想定し、組織内のルータでは DMZ のサーバと組織内PCは通信できないように FireWall を2重に設置する。

実数の取り扱いと誤差

実数型(float / double)

実数型は、単精度実数(float型)と、倍精度実数(double型)があり、それぞれ32bit,64bitでデータを扱う。

指数表現は、大きい値や小さい値を表現する場合に使われ、物理などで1.2345×10-4といった、仮数×基数指数で表現する方法。数学や物理では基数に10を用いるが、コンピュータの世界では基数を2とすることが多い。

単精度型(float)では、符号1bit,指数部8bit,仮数部23bitで値を覚え、数値としては、以下の値を意味する。(精度が低いので普通のコンピュータではあまり使われることはない)

符号✕ 1.仮数部 ✕ 2(指数数部-127)

符号部は、正の値なら0, 負の値なら1 を用いる。

仮数部が23bitなので、有効桁(正しい桁の幅)は約7桁となる。

例えば、float型で扱える最大数は、以下のようになる。

0,1111,1111,111,1111,1111,1111,1111,1111 = 1.1111…×2128 2129 1038

倍精度型(double)では、符号1bit,指数部11bit,仮数部52bitで値を覚え、数値としては、以下の意味を持つ。

符号✕ 1.仮数部 ✕ 2(指数部-1023)

これらの実数で計算を行うときには、0.00000001011×210といった値の時に、仮数部に0が並んだ状態を覚えると、計算の精度が低くなるので、1.01100000000×22のように指数部の値を調整して小数点の位置を補正しながら行われる。

double型の場合、52bit=10進数16桁相当の有効桁、最大数で、1.1111…×2102410308

倍精度型を使えば、正しく計算できるようになるかもしれないが、実数型はただの加算でも仮数部の小数点の位置を合わせたりする処理が必要で、浮動小数点専用の計算機能を持っていないような、ワンチップコンピュータでは整数型にくらべると10倍以上遅い場合もある。

実数の注意点

C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか?解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか?

単純な合計と平均

整数を入力し、最後に合計と平均を出力するプログラムを以下に示す。
しかし、C言語でこのプログラムを動かすと、10,10,20,-1 と入力すると、合計(sum)40,件数(cnt)3で、平均は13と表示され、13.33333 とはならない。

小数点以下も正しく表示するには、どうすればいいだろうか?
ただし、変数の型宣言を “double data,sum,cnt ;” に変更しないものとする。

// 入力値の合計と平均を求める。
#include <stdio.h>

int main() {
   int data ;
   int sum = 0 ;
   int cnt = 0 ;
   for(;;) {
      printf( "数字を入力せよ。-1で終了¥n" ) ;
      scanf( "%d" , &data ) ;
      if ( data < 0 )
         break ;
      cnt = cnt + 1 ;
      sum = sum + data ;
   }
   printf( "合計 %d¥n" , sum ) ;
   printf( "平均 %d¥n" , sum / cnt ) ;
}

C言語では、int型のsum / int型のcnt の計算は、int 型で計算を行う(小数点以下は切り捨てられる)。このため、割り算だけ実数で行いたい場合は、以下のように書かないといけない。

   printf( "平均 %lf¥n" , (double)sum / (double)cnt ) ;
   // (double)式 は、sum を一時的に実数型にするための型キャスト

まずは動く例

以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。

// sin の値を出力
#include <stdio.h>
#include <math.h>

int main() {
    double th , y ;
    for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) {
        y = sin( th / 180.0 * 3.1415926535 ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}

動かないプログラム

では、以下のプログラムはどうだろうか?

// case-1 ---- プログラムが止まらない
#define PI 3.1415926535
int main() {
    double th , y ;
    // 0〜πまで100分割でsinを求める
    for( th = 0.0 ; th != PI ; th += PI / 100.0 ) {
        y = sin( th ) ;
        printf( "%lf %lf¥n" , th , y ) ;
    }
    return 0 ;
}
// case-2 ---- y の値が全てゼロ
int main() {
    int    th ;
    double y ;
    for( th = 0 ; th <= 360 ; th += 5 ) {
        y = sin( th / 180 * 3.1415926535 ) ;
        printf( "%d %lf¥n" , th , y ) ;
    }
    return 0 ;
}

どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。

では何が悪かったのか…
回答編


数値と誤差

コンピュータで計算すると、計算結果はすべて正しいと勘違いをしている人も多い。ここで、改めて誤差について考える。特に、計器で測定した値であれば、測定値自体に誤差が含まれている。

こういった誤差が含まれる数字を扱う場合注意が必要である。例えば実験値を手書きで記録する場合、12.3 と 12.300 では意味が異なる。測定値であやふやな桁を丸めたのであれば、前者は 12.2500〜12.3499… の間の値であり有効数字3桁である。後者は、12.2995〜12.300499… の間の値であり、有効数字5桁である。このため、誤差が含まれる数字の加算・減算・乗算・除算では注意が必要である。

加減乗除算の場合

加減算であれば小数点の位置を揃え、誤差が含まれる桁は有効桁に含めてはいけない。

上記の計算では、0.4567の0.0567の部分は意味がないデータとなる。(情報落ち)

乗除算であれば、有効桁の少ない値と有効桁の多い値の計算では、有効桁の少ない方の誤差の影響が計算結果に出てくるため、通常は、有効桁5桁と2桁の計算であれば、乗除算結果は少ない2桁で書くべきである。

桁落ち

有効桁が大きい結果でも、減算が含まれる場合は注意が必要である。

例えば、以下のような計算では、有効桁7桁どうしでも、計算結果の有効桁は3桁となる。

このような現象は、桁落ちと呼ばれる。

演習問題(4回目)

こちらのフォルダに示す、Excel の表で、有効桁を考えてもらうための演習問題(ランダムに値が作られます)を有効数字を考えながら計算し、答えをレポートにまとめてください。例を以下に示す。

抽象クラス(純粋仮想基底クラス)

前回説明した仮想関数では、基底クラスから派生させたクラスを作り、そのデータが混在してもクラスに応じた関数(仮想関数)を呼び出すことができる。

この仮想関数の機能を逆手にとったプログラムの記述方法として、抽象クラス(純粋仮想基底クラス)がある。その使い方を説明する。

JavaのGUIにおける派生の使い方

先週の講義では、派生を使ったプログラミングは、GUI で使われていることを紹介したが、例として Java のプログラミングスタイルを少し紹介する。

例えば、Java で アプレット(ブラウザの中で動かすJavaプログラム)を作る場合の、最小のサンプルプログラムは、以下のようになる。

import java.applet.Applet; // C言語でいうところの、Applet 関連の処理を include
import java.awt.Graphics;

public class App1 extends Applet {  // Applet クラスから、App1 クラスを派生
    public void paint(Graphics g) { // 画面にApp1を表示する必要がある時に呼び出される。
        g.drawString("Hello World." , 100 , 100);
    }
}

この例では、ブラウザのGUIを管理する Applet クラスから、App1 というクラスを派生(extendsキーワード)し、App1 固有の処理として、paint() メソッドを定義している。GUI のプログラミングでは、本来ならマウスが押された場合の処理などを記述する必要があるが、このプログラムでは paint() 以外何も書かれていない。これはマウス処理などは、基底クラスのAppletのマウス処理が継承されるので、省略してもうまく動くようになっている。

純粋仮想基底クラス

純粋仮想基底クラスとは、見かけ上はデータを何も持たないクラスであり、本来なら意味がないデータ構造となってしまう。しかし、派生クラスで要素となるデータと仮想関数で機能を与えることで、基底クラスという共通部分から便利な活用ができる。(実際には、型を区別するための型情報を持っている)

例えば、C言語であれば一つの配列に、整数、文字列、実数といった異なる型のデータを記憶させることは本来ならできない。しかし、以下のような処理を記載すれば、可能となる。

C言語では、1つの記憶域を共有するために共用体(union)を使うが、C++では仮想関数が使えるようになり、型の管理をプログラマーが行う必要のある「面倒で危険な」共用体を使う必要はなくなった。

// 純粋仮想基底クラス
class Object {
public:
   virtual void print() const = 0 ;
   // 中身の無い純粋基底クラスで、
   // 仮想関数を記述しない時の書き方。
} ;

// 整数データの派生クラス
class IntObject : public Object {
private:
   int data ;
public:
   IntObject( int x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%d\n" , data ) ;
   }
} ;

// 文字列の派生クラス
class StringObject : public Object {
private:
   char data[ 100 ] ;
public:
   StringObject( const char* s ) {
      strcpy( data , s ) ;
   }
   virtual void print() const {
      printf( "%s\n" , data ) ;
   }
} ;

// 実数の派生クラス
class DoubleObject : public Object {
private:
   double data ;
public:
   DoubleObject( double x ) {
      data = x ;
   }
   virtual void print() const {
      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++ ) { // 123
      data[i]->print() ;            // abc
   }                                // 1.23 と表示
   return 0 ;
} ;

このプログラムでは、純粋仮想基底クラスObjectから、整数IntObject, 文字列StringObject, 実数DoubleObject を派生させ、そのデータを new により生成し、Objectの配列に保存している。

仮想関数を使うと、Object型の中に自動的に型情報が保存されるようになる。一般的な実装では、各派生クラス用の仮想関数のポインタテーブル(vtable)へのポインタが使われる。

Javaなどのオブジェクト指向言語では、全てのクラス階層のスーパークラスとして、Object を持つように作られている。

様々な型に適用できるプログラム

次に、純粋仮想基底クラスの特徴を応用したプログラムの作り方を説明する。

例えば、以下のような最大選択法で配列を並び替えるプログラムがあったとする。

int a[5] = { 11, 55, 22, 44, 33 } ;

void my_sort( int array[] , int size ) {
   for( int i = 0 ; i < size - 1 ; i++ ) {
      int max = i ;
      for( int j = i + 1 ; j < size ; j++ ) {
         if ( array[j] > array[max] )
            max = j ;
      }
      int tmp = array[i] ;
      array[i] = array[max] ;
      array[max] = tmp ;
   }
}
int main() {
   my_sort( a , 5 ) ;
}

しかし、この整数を並び替えるプログラムがあっても、文字列の並び替えや、実数の並び替えがしたい場合には、改めて文字列用並び替えの関数を作らなければいけない。しかも、ほとんどが同じような処理で、改めて指定された型のためのプログラムを作るのは面倒である。

C言語のデータの並び替えを行う、qsort() では、関数ポインタを用いることで、様々なデータの並び替えができる。しかし、1件あたりのデータサイズや、データ実体へのポインタを正しく理解する必要がある。

#include <stdio.h>
#include <stdlib.h>
int a[ 4 ] = { 11, 33, 22, 44 } ;
double b[ 3 ] = { 1.23 , 5.55 , 0.11 } ;
// 並び替えを行いたいデータ専用の比較関数を作る。
// a>bなら+1, a=bなら0, a<bなら-1を返す関数
int cmp_int( int* pa , int* pb ) { // int型用コールバック関数
   return *pa - *pb ;
}
int cmp_double( double* pa , double* pb ) { // double型用コールバック関数
   if ( *pa == *pb )
      return 0 ;
   else if ( *pa > *pb )
      return 1 ;
   else
      return -1 ;
}
int main() {                                   // C言語の怖さ
   qsort( a , 4 , sizeof( int ) ,              //   このあたりの引数を書き間違えると
          (int(*)(void*,void*)) cmp_int ) ;    //   とんでもない目にあう。
   qsort( b , 3 , sizeof( double ) ,
          (int(*)(void*,void*)) cmp_double ) ;
} 

このように、自分が作っておいた関数のポインタを、関数に渡して呼び出してもらう方法は、コールバックと呼ぶ。
JavaScript などの言語では、こういったコールバックを使ったコーディングがよく使われる。

// コールバック関数 f を呼び出す関数
function exec_callback( var f ) {
   f() ;
}
// コールバックされる関数 foo()
function foo() {
   console.log( "foo()" ) ;
}
// foo() を実行する。
exec_callback( foo ) ;
// 無名関数を実行する。
exec_callback( function() {
                  console.log( "anonymous" ) ;
               } ) ;

任意のデータを並び替え

class Object {
public:
   virtual void print() const = 0 ;
   virtual int  cmp( Object* ) = 0 ;
} ;

// 整数データの派生クラス
class IntObject : public Object {
private:
   int data ;
public:
   IntObject( int x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%d\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      int pdata = ((IntObject*)p)->data ;  // 本当はこのキャストが危険
      return data - pdata ;                //  ↓安全な実装したいなら↓
   }                                       // IntObject* pi = dynamic_cast<IntObject*>(p) ;
} ;                                        // return pi != NULL ? data - pi->data : 0 ;

// 文字列の派生クラス
class StringObject : public Object {
private:
   char data[ 100 ] ;
public:
   StringObject( const char* s ) {
      strcpy( data , s ) ;
   }
   virtual void print() const {
      printf( "%s\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      char* pdata = ((StringObject*)p)->data ;
      return strcmp( data , pdata ) ; // 文字列比較関数
   }
} ;

// 実数の派生クラス
class DoubleObject : public Object {
private:
   double data ;
public:
   DoubleObject( double x ) {
      data = x ;
   }
   virtual void print() const {
      printf( "%lf\n" , data ) ;
   }
   virtual int cmp( Object* p ) {
      double pdata = ((DoubleObject*)p)->data ;
      if ( data == pdata )
         return 0 ;
      else if ( data > pdata )
         return 1 ;
      else
         return -1 ;
   }
} ;

// Objectからの派生クラスでcmp()メソッドを
//   持ってさえいれば、どんな型でもソートができる。
void my_sort( Object* array[] , int size ) {
   for( int i = 0 ; i < size - 1 ; i++ ) {
      int max = i ;
      for( int j = i + 1 ; j < size ; j++ ) {
         if ( array[j]->cmp( array[max] ) > 0 )
            max = j ;
      }
      Object* tmp = array[i] ;
      array[i] = array[max] ;
      array[max] = tmp ;
   }
}
// 動作確認
int main() {
   Object* idata[3] = {
      new IntObject( 11 ) ,
      new IntObject( 33 ) ,
      new IntObject( 22 ) ,
   } ;
   Object* sdata[3] = {
      new StringObject( "abc" ) ,
      new StringObject( "defghi" ) ,
      new StringObject( "c" ) ,
   } ;
   my_sort( idata , 3 ) ; // 整数のソート
   for( int i = 0 ; i < 3 ; i++ )
      idata[i]->print() ;
   my_sort( sdata , 3 ) ; // 文字列のソート
   for( int i = 0 ; i < 3 ; i++ )
      sdata[i]->print() ;
   return 0 ;
} ;

このような方式でプログラムを作っておけば、新しいデータ構造がでてきてもソートのプログラムを作らなくても、比較専用の関数 cmp() を書くだけで良い。

ただし、この並び替えの例では、Object* を IntObject* に強制的に型変換している。

また、このプログラムでは、データを保管するために new でポインタを保管し、データの比較をするために仮想関数の呼び出しを行うことから、メモリの使用効率も処理効率でもあまりよくない。

こういう場合、最近の C++ ではテンプレート機能が使われる。

template <typename T>
void my_sort( T a[] , int size ) {
  for( int i = 0 ; i < size - 1 ; i++ ) {
    int max = i ;
    for( int j = i + 1 ; j < size ; j++ ) { if ( a[j] > a[max] )
        max = j ;
    }
    T  tmp = a[i] ;
    a[i] = a[max] ;
    a[max] = tmp ;
  }
}

int main() {
  int idata[ 5 ] = { 3, 4, 5 , 1 , 2 } ;
  double fdata[ 4 ] = { 1.23 , 0.1 , 3.4 , 5.6 } ;

  // typename T = int で int::mysort() が作られる
  my_sort<int>( idata , 5 ) ;
  for( int i = 0 ; i < 5 ; i++ )
    printf( "%d " , idata[i] ) ;
  printf( "\n" ) ;

  // typename T = double で double::mysort() が作られる
  my_sort<double>( fdata , 4 ) ;
  for( int i = 0 ; i < 4 ; i++ )
    printf( "%lf " , fdata[i] ) ;
  printf( "\n" ) ;
  return 0 ;
}

C++のテンプレート機能は、my_sort( int[] , int ) で呼び出されると、typename T = int で、整数型用の my_sort() の処理が自動的に作られる。同じく、my_sort( double[] , int ) で呼び出されると、typename = double で 実数型用の my_sort() が作られる。

テンプレート機能では、各型用のコードが自動的に複数生成されるという意味では、出来上がったコードがコンパクトという訳ではない。

神山まるごと高専の大蔵氏の講演

神山まるごと高専(仮称)の校長となる大蔵氏は、本校電子情報工学科の出身ですが、来年の開校を前に来校し、準備状況などの話を聞くことができました。
{CAPTION}
話の中では、社会人で会う人の中で「この人は高専かな?」と感じる機会というのはよくあって、そういう高専生の「高専生らしさ」のある学生を育てたいといったお話が、私にとって印象的でした。

malloc()とfree()

前回の授業で説明した、alloca() は、スタック領域にデーターを覚えるので、allocaを実行した関数の終了ともに配列領域が消えてしまう。しかし、関数が終わってもそのデータを使いたいといった場合には、malloc()+free()を使う必要がある。

malloc()とfree()

malloc() は、動的(ヒープ領域)にメモリを確保する命令で、データを保存したい時に malloc() を実行し、不要になった時に free() を実行する。

malloc() では、alloca() と同じように、格納したいデータの byte 数を指定する。また、malloc() は、確保したメモリ領域の先頭を返すが、ヒープメモリが残っていない場合 NULL ポインタを返す。処理が終わってデータ領域をもう使わなくなったら、free() で解放する必要がある。

基本的には、確保したメモリ領域を使い終わった後 free() を実行しないと、再利用できないメモリ領域が残ってしまう。こういう処理を繰り返すと、次第にメモリを食いつぶし、仮想メモリ機能によりハードディスクの読み書きで性能が低下したり、最終的にOSが正しく動けなくなる可能性もある。こういった free() 忘れはメモリーリークと呼ばれ、malloc(),free()に慣れない初心者プログラマーによく見られる。

ただし、ヒープメモリ全体は、プロセスの起動と共に確保され(不足すればOSから追加でメモリを分けてもらうこともできる)、プログラムの終了と同時にOSに返却される。このため、malloc()と処理のあとすぐにプロセスが終了するようなプログラムであれば、free() を忘れても問題はない。授業では、メモリーリークによる重大な問題を理解してもらうため、原則 free() は明記する。

文字列を保存する場合

#include <stdlib.h>
char* names[ 10 ] ;
char  buff[ 1000 ] ;

// 名前を10件読み込む
void inputs() {
   for( int i = 0 ; i < 10 ; i++ ) {
      if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
         names[ i ] = (char*)malloc( strlen(buff)+1 ) ;
         if ( names[ i ] != NULL )
            strcpy( names[ i ] , buff ) ;
      }
   }
}
// 名前を出力する
void prints() {
   for( int i = 0 ; i < 10 ; i++ )
      printf( "%s" , names[ i ] ) ;
}
void main() {
   // 文字列の入力&出力
   inputs() ;
   prints() ;
   // 使い終わったら、free() で解放
   for( int i = 0 ; i < 10 ; i++ )
      free( names[ i ] ) ;
}

文字列を保存する場合には、上記の names[i] への代入のような malloc() と strcpy() を組み合わせて使うことが多い。しかし、この一連の処理の関数として、strdup() がある。基本的には、以下のような機能である。

char* strdup( char* s ) {
   char* p ;
   if ( (p = (char*)malloc( strlen(s)+1 )) != NULL )
      strcpy( p , s ) ;
   return p ;
}

また、入力した文字列をポインタで保存する場合、以下のようなプログラムを書いてしまいがちであるが、図に示すような状態になることから、別領域にコピーする必要がある。

char  buff[ 1000 ] ;
char* name[10] ;
for( int i = 0 ; i < 10 ; i++ ) {
   if ( fgets( buff , sizeof(buff) , stdin ) != NULL )
      name = buff ;
      // ここは、name = strdup( buff ) ; と書くべき。
}

配列に保存する場合

基本的な型の任意サイズの配列を作りたい場合には、malloc() で一括してデータの領域を作成し、その先頭アドレスを用いて配列として扱う。

#include <stdlib.h>
void main() {
   int size ;
   int* array ;
   // 処理するデータ件数を入力
   scanf( "%d" , &size ) ;

   // 整数配列を作る
   if ( (array = (int*)malloc( sizeof(int) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         array[i] = i*i ; // あんまり意味がないけど
      for( i = 0 ; i < size ; i++ )
         printf( "%d¥n" , array[i] ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }
}

構造体の配列

同じように、任意サイズの構造体(ここではstruct Complex)の配列を作りたいのであれば、mallocの引数のサイズに「sizeof( struct Complex ) * データ件数」を指定すればいい。

後半の array2[] では、ポインタの配列を使った例を示す。この例では、1つの構造体毎に1つのmallocでメモリを確保している。

#include <stdlib.h>
struct Complex {
   double re , im ;
} ;

// 指定した場所にComplexを読み込む。
int input_Complex( struct Complex* p ) {
   return scanf( "%lf %lf" , &(p->re) , &(p->re) ) == 2 ;
}

// 指定したComplexを出力
void print_Complex( struct Complex* p ) {
   printf( "%lf+j%lf¥n" , p->re , p->im ) ;
}
void main() {
   int size ;
   struct Complex* array ;
   struct Complex** array2 ;

   // 処理する件数を入力
   scanf( "%d" , &size ) ;
   // 配列を確保して、データの入力&出力
   if ( (array = (struct Complex*)malloc(
                    sizeof(struct Complex) * size )) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ )
         if ( !input_Complex( &array[i] ) )
            break ;
      for( i = 0 ; i < size ; i++ )
         print_Complex( &array[i] ) ;
         // or printf( "%lf + j%lf\n" ,
         //            array[ i ].re , array[ i ].im ) ;

      // mallocしたら必ずfree
      free( array ) ;
   }

   // ポインタの配列で保存
   if ( (array2 = (struct Complex**)malloc(
                     sizeof(struct Complex*) * size)) != NULL ) {
      int i ;
      for( i = 0 ; i < size ; i++ ) {
         // 各データごとにmalloc()
         array2[ i ] = (struct Complex*)malloc( sizeof( struct Complex ) ) ;
         if ( array2[ i ] != NULL ) {
            array2[ i ]->re = (double)i ;
            array2[ i ]->im = (double)i ;
         }
      }
      // 保存した構造体をすべて表示
      for( i = 0 ; i < size ; i++ )
         print_Complex( array[ i ] ) ;
      // 各データごとに free
      for( i = 0 ; i < size ; i++ )
         free( array[ i ] ) ;
      // ポインタの配列を free
      free( array2 ) ;
   }
}

(おまけ)C++の場合

C言語における malloc() + free () でのプログラミングは、mallocの結果を型キャストしたりするので、間違ったコーディングの可能性がある。このため、C++ では、new 演算子, delete 演算子というものが導入されている。

// 同じ処理をC++で書いたら
// 文字列の保存
char  str[] = "ABCDE" ;
char* pc = new char[ strlen( str ) + 1 ] ;
strcpy( pc , str ) ;
// pcを使った処理
delete[] pc ;  // new型[]を使ったらdelete[]

// int配列の保存
int  data[] = { 11 , 22 , 33 } ;
int* pi ;
pi = new int[ 3 ] ;
for( int i = 0 ; i < 3 ; i++ )
   pi[ i ] = data[ i ] ;
// piを使った処理
delete[] pi ;

// 構造体の保存
struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
Person* pPsn ;
pPsn = new Person ;
strcpy( pPsn->name , "t-saitoh" ) ;
pPsn->age = 55 ;
// pPsnを使った処理
delete pPsn ; // new型ならdelete

注意すべき点は、malloc+freeとの違いは、mallocがメモリ確保に失敗した時の処理の書き方。返り値のNULLをチェックする方法は、呼び出し側ですべてでNULLの場合を想定した書き方が必要になり、処理が煩雑となる。C++の new 演算子は、メモリ確保に失敗すると、例外 bad_alloc を投げてくるので、try-catch 文で処理を書く。(上記例はtry-catchは省略)