ホーム » 2020 » 5月

月別アーカイブ: 5月 2020

2020年5月
 12
3456789
10111213141516
17181920212223
24252627282930
31  

検索・リンク

ソートのアルゴリズムの分岐点

ソートアルゴリズムの処理時間で、選択法よりクイックソートが有利になる分岐点を求める問題で、

の結果が、N=53.1 になる…との説明が判らないとの質問。# 53.017 が正しいとの結果だったが。

あてずっぽうな計算方法

Excelで実際に計算すればいい。B列2行目に =A2/LOG(A2) を入れて、A列に2,3,…. と数字を入れて変化させて、30.74 に近い場所を探すと53となった。# 手抜きだな!

ニュートン法で解く

方程式で解けない場合は、ニュートン法 f(x)=0 の式でxの値を求める…のが定番の方法。

この場合は f(x) = x/log(x) – 1000/25/log(20) として、ニュートン法の漸化式を解けばいい。
ちょいとプログラムを書いてみた。

((( nlogn.cxx )))
#include <stdio.h>
#include <math.h>

// N/logN = 1000/25/log20 をニュートン法で解く                                                                          
//                                                                                                                      
//      f(x) = x/log(x) - 1000/25/log20                                                                                 
//      f'(x) = log(10) (log(x) - 1) / log(x)^2                                                                         
//                                                                                                                      
//      x <= x + f(x) / f'(x)                                                                                           

//      要注意 C言語のlog関数                                                                                           
//              log(x) = 自然対数を底とするlog                                                                          
//              log10(x) = 10を底とするlog                                                                              

double f( double x ) {
  return x / log10(x) - 1000.0/25.0/log10(20.0) ;
}

double df( double x ) {
  return log(10.0) * ( log(x) - 1.0 ) / pow( log(x) , 2.0 ) ;
}

int main() {
  double x = 5.0 ;

  for( int i = 0 ; i < 5 ; i++ ) {
    double f1 = f(x) ;
    double f2 = df(x) ;
    x = x - f1 / f2 ;
    printf( "%d %lf\n" , i , x ) ;
  }
  return 0 ;
}

((( 実行結果 )))
$ g++ nlogn.cxx
$ ./a.out
0 48.547041
1 52.983539
2 53.016894
3 53.016896
4 53.016896

うーむ、Webの資料では、53 に近い値だし、あてずっぽうで 53.1 となる…って書いたけど、本当は 53.017 だな。m(_ _)m

数年前までの電子情報の学生さんなら、TI の関数電卓持ってたから「授業で解いて…」というと、結果をすぐに答えてくれる優秀な人がクラスに1人くらい必ずいたけど、最近は BYOD でパソコンを使うので TI の関数電卓持ってないから、解いてくれるヤツいないのよね。

SolidWorks使い方入門

SolidWorks

3Dプリンタ AFINIA H800

ソート処理の見積もりとポインタ処理

前回の授業では、再帰処理やソートアルゴリズムの処理時間の見積もりについて説明を行った。

ソート処理の見積もり

この際の練習問題の1つめは、「再帰方程式の理解度確認の回答」にて解説を示す。

最後の練習問題はここで説明を行う。

選択法とクイックソートの処理時間の比較

例として、データ数N=20件で、選択法なら10msec、クイックソートで20msecかかったとする。

これより、選択法の処理時間を、クイックソートの処理時間を、とすると、





よって、

処理時間が逆転するときのデータ件数は、2つのグラフの交点を求めることになるので、

より、以下の式を解いた答えとなる。これは通常の方程式では解けないが電卓で求めると、N=53.1 ほどかな。(2020/05/26) 真面目に解いたら N=53.017 だった。

実際にも、クイックソートを再帰呼び出しだけでプログラムを書くと、データ件数が少ない場合は選択法などのアルゴリズムの方が処理時間が早い。このため、C言語などの組み込み関数の qsort() などは、データ件数が20とか30とか一定数を下回ったら、再帰を行わずに選択法でソートを行うのが一般的である。

ポインタ処理

ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。

値渡し(call by value)

// 値渡しのプログラム
void foo( int x ) {  // x は局所変数(仮引数は呼出時に
                     // 対応する実引数で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   int a = 123 ;
   foo( a ) ;  // 124
               // 処理後も main::a は 123 のまま。
   foo( a ) ;  // 124
}

このプログラムでは、aの値は変化せずに、124,124 が表示される。

言い方を変えるなら、呼び出し側main() では、関数の foo() の処理の影響を受けない。このように、関数には仮引数の値を渡すことを、値渡し(call by value)と言う。

でも、プログラムによっては、124,125 と変化して欲しい場合もある。
どのように記述すべきだろうか?

// 大域変数を使う場合
int x ;
void foo() {
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   x = 123 ;
   foo() ;  // 124
   foo() ;  // 125
}

しかし、このプログラムは大域変数を使うために、間違いを引き起こしやすい。

// 大域変数が原因で予想外の挙動をしめす簡単な例
int i ;
void foo() {
   for( i = 0 ; i < 2 ; i++ )
      printf( "A" ) ;
}
void main() {
   for( i = 0 ; i < 3 ; i++ )  // このプログラムでは、AA AA AA と
      foo() ;                   // 表示されない。
}

ポインタ渡し(call by pointer)

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、(引数を経由して関数の副作用を受け取るには)、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。このような値の受け渡し方法は、ポインタ渡し(call by pointer)と呼ぶ。

// ポインタ渡しのプログラム
void foo( int* p ) {  // p はポインタ
   (*p)++ ;
   printf( "%d¥n" , *p ) ;
}
void main() {
   int a = 123 ;
   foo( &a ) ;  // 124
                // 処理後 main::a は 124 に増えている。
   foo( &a ) ;  // 124
}               // さらに125と増える。

C言語では、関数から結果をもらうには、通常は関数の返り値を使う。しかし、返り値は1つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は:結果を入れてもらう場所を伝え、関数側は:指定されたアドレスに結果を書む。

ポインタの加算と配列アドレス

ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。

// ポインタ加算の例
int a[ 5 ] = { 11 , 22 , 33 , 44 , 55 } ;

void main() {
   int* p ;
                               //            p∇
   p = &a[2] ;                 // a[] : 11,22,33,44,55
                               //       -2    +0 +1
   printf( "%d¥n" , *p ) ;     // 33  p[0]
   printf( "%d¥n" , *(p+1) ) ; // 44  p[1]
   printf( "%d¥n" , *(p-2) ) ; // 11  p[-2]

   p = a ;                  //      p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p++ ;                    //       → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
   p += 2 ;                 //           → → p∇
   printf( "%d¥n" , *p ) ;  // a[] : 11,22,33,44,55
}

ここで、注意すべき点は、ポインタの加算した場所の参照と、配列の参照は同じ意味となる。

*(p + 整数式)p[ 整数式 ] は同じ意味

特に配列 a[] の a だけを記述すると、配列の先頭を意味することに注意。

構造体とポインタ

構造体を関数に渡して処理を行う例を示す。

struct Person {
   char name[ 10 ] ;
   int  age ;
} ;
struct Person table[3] = {
   { "t-saitoh" , 55 } ,
   { "tomoko" ,   44 } ,
   { "mitsuki" ,  19 } ,
} ;

void print_Person( struct Person* p ) {
   printf( "%s %d\n" ,
           (*p).name , // * と . では . の方が優先順位が高い
                       // p->name と簡単に書ける。
           p->age ) ;  // (*p).age の簡単な書き方
}

void main() {
   for( int i = 0 ; i < 3 ; i++ ) {
      print_Person( &(table[i]) ) ;
   // print_Person( table + i ) ; でも良い
   }
}

構造体へのポインタの中の要素を参照する時には、アロー演算子 -> を使う。

練習問題(2018年度中間試験問題より)

派生と継承

隠ぺい化の次のステップとして、派生・継承を説明する。オブジェクト指向プログラミングでは、一番基本となるデータ構造を宣言し、その基本構造に様々な機能を追加した派生クラスを記述することでプログラムを作成する。今回は、その派生を理解するためにC言語で発生する問題点を考える。

派生を使わずに書くと…

元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。

// 元となる構造体(Person) / 基底クラス
struct Person {
   char name[ 20 ] ; // 名前
   int  age ;        // 年齢
} ;
// 初期化関数
void set_Person( struct Person* p ,
                 char s[] , int x ) {
   strcpy( p->name , s ) ;
   p->age = x ;
}
// 表示関数
void print_Person( struct Person* p ) {
   printf( "%s %d\n" , p->name , p->age ) ;
}
int main() {
   struct Person saitoh ;
   set_Person( &saitoh , "t-saitoh" , 50 ) ;
   print_Person( &saitoh ) ;
   return 0 ;
}

パターン1(そのまんま…)

上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。

このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。

// 元のデータに追加要素(パターン1)
struct PersonStudent1 {
   // Personと同じ部分
   char name[ 20 ] ; // 名前
   int  age ;        // 年齢

   // 追加部分
   char dep[ 20 ] ;  // 所属
   int  grade ;      // 学年
} ;
void set_PersonStudent1( struct PersonStudent1* p ,
                         char s[] , int x ,
                         char d[] , int g ) {
   // set_Personと同じ処理を書いている。
   strcpy( p->name , s ) ;
   p->age = x ;

   // 追加された処理
   strcpy( p->dep , d ) ;
   p->grade = g ;
}

// 名前と年齢 / 所属と学年を表示
void print_PersonStudent1( struct PersonStudent1* p ) {
   // print_Personと同じ処理を書いている。
   printf( "%s %d\n" , p->name , p->age ) ;
   printf( "- %s %d¥n" , p->dep , p->grade ) ;
}

int main() {
   struct PersonStudent1 yama1 ;
   set_PersonStudent1( &yama1 ,
                       "yama" , 22 , "PS" , 2 ) ;
   print_PersonStudent1( &yama1 ) ;
   return 0 ;
}

パターン2(元データの処理を少し使って…)

パターン1では、機能が追加された新しいデータ構造のために、同じような処理を改めて書くことになりプログラムの記述量を減らせない。面倒なので、 元データ用の関数をうまく使うように書いてみる。

// 元のデータに追加要素(パターン2)
struct PersonStudent2 {
   // 元のデータPerson
   struct Person person ;

   // 追加部分
   char          dep[ 20 ] ;
   int           grade ;
} ;

void set_PersonStudent2( struct PersonStudent2* p ,
                         char s[] , int x ,
                         char d[] , int g ) {
   // Personの関数を部分的に使う
   set_Person( &(p->person) , s , x ) ;

   // 追加分はしかたない
   strcpy( p->dep , d ) ;
   p->grade = g ;
}

void print_PersonStudent2( struct PersonStudent2* p ) {
   // Personの関数を使う。
   print_Person( &p->person ) ;
   printf( "- %s %d¥n" , p->dep , p->grade ) ; 
}

int main() {
   struct PersonStudent2 yama2 ;
   set_PersonStudent2( &yama2 ,
                       "yama" , 22 , "PS" , 2 ) ;
   print_PersonStudent2( &yama2 ) ;
   return 0 ;
}

このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。

しかし、print_PersonStudent2() のような処理は、元データ構造が同じなのに、 いちいちプログラムを記述するのは面倒ではないか?

そこで、元データの処理を拡張し、処理の流用ができないであろうか?

基底クラスから派生クラスを作る

オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」「public/protected/private」基底クラス名を書く。

// 基底クラス
class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   Person( const char s[] , int x )
     : age( x ) {
      strcpy( name , s ) ;
   }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
// 派生クラス(Student は Person から派生)
class Student : public Person {
private:
   // 追加部分
   char dep[ 20 ] ;
   int  grade ;
public:
   Student( const char s[] , int x ,
            const char d[] , int g )
            : Person( s , x ) // 基底クラスのコンストラクタ
   {  // 追加された処理
      strcpy( dep , d ) ;
      grade = g ;
   }
} ;

int main() {
   Person saitoh( "t-saitoh" , 50 ) ;
   saitoh.print() ;
   Student yama( "yama" , 22 , "PS" , 2 ) ;
   yama.print() ;
   return 0 ;
}

ここで注目すべき点は、main()の中で、Studentクラス”yama”に対し、yama.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「yama 22」が表示される。

さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。

class Student ...略... {
   ...略...

   // Student クラス専用の print() 
   void print() {
      // 親クラス Person の print() を呼び出す
      Person::print() ;
      // Student クラス用の処理
      printf( "%s %d\n" , dep , grade ) ;
   }
} ;
void main() {
   ...略...
   Student yama( "yama" , 22 , "PS" , 2 ) ;
   yama.print() ;
}

この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「yama 22 / PS 2」が表示される。

派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。

public    だれもがアクセス可能。
protected であれば、派生クラスからアクセスが可能。
          派生クラスであれば、通常は protected で使うのが一般的。
private   派生クラスでもアクセス不可。

仮想関数への伏線

上記のような派生したプログラムを記述した場合、以下のようなプログラムでは何が起こるであろうか?

class Student ... {
   :
   void print() {
      Person::print() ;                    // 名前と年齢を表示
      printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示
   }
} ;
int main() {
   Person saitoh( "t-saitoh" , 55 ) ;
   saitoh.print() ;                // t-saitoh 55 名前と年齢を表示

   Student mitsu( "mitsuki" , 20 , "KIT" ,  3 ) ;
   Student ayuka( "ayuka" ,   18 , "EI" ,   4 ) ;
   mitsu.print() ;                 // mitsuki 20 / KIT 3  名前,年齢,所属,学年を表示
   ayuka.print() ;                 // ayuka 18   / EI  4  名前,年齢,所属,学年を表示

   Person* family[] = {
      &saitoh , &mitsu , &ayuka ,  // 配列の中に、Personへのポインタと
   } ;                             // Studentへのポインタが混在している
                                   // 派生クラスのポインタは、
                                   // 基底クラスのポインタとしても扱える
   for( int i = 0 ; i < 3 ; i++ )
      family[ i ]->print() ;       // t-saitoh 55/mitsuki 20/ayuka 18
   return 0 ;                      // が表示される。 
}                                  // # "mitsuki 20/KIT 3" とか "ayuka 18/EI 4"
                                   // # が表示されてほしい?

Remote-sshでcould not to establish…

PHPとデータベースの実験で、クラウドサーバ上のファイルを触るために、VSCode に Remote-ssh をインストールして、サーバのファイルを編集だけど、何人かの学生がログインできない様子。

“Could not establish connection to ホスト名”といったエラーが表示される。同様のエラーの情報を探していたら、以下のようにremotePlatformを指定すれば良いとの情報。

Remote-sshの設定⚙の、「拡張機能の設定」を選び、Remote-sshのRemote Platformを編集するためのsettings.jsonの編集画面となる。

この中で、”remote.SSH.remotePlatform”に、接続相手の名前とOS種別(今回はLinux)を設定する。

再帰方程式の理解度確認の解答

再帰呼び出しと再起方程式の資料の中の「理解度確認」の解答

解答

pyraをループで

// pyra() をループで書いたら。
int pyra( int x ) {
   int ans = 0 ;
   for( int i = 1 ; i <= x ; i++ )
      ans += i * i ;
   return ans ;
}

2分探索法を再帰で

// 2分探索を再帰で書いたら
int find( int array[] , int L , int R , int key ) {
   if ( R == L ) {
      return 0 ; // みつからない
   } else {
      int M = (L + R) / 2 ;
      if ( array[ M ] == key )     // みつかった
         return 1 ;           
      else if ( array[ M ] > key ) // 左側にある - 末尾再帰
         return find( array , L , M , key ) ;
      else                         // 右側にある
         return find( array , M+1 , R , key ) ;
   }
}

このプログラムでは、検索する範囲がLとRで与えられ、この範囲の幅が再帰が呼び出される毎に半分になっていく。

であれば、処理時間は対象となるデータ件数 N = R – L によって、処理時間は変化するので、T(N) で考えると、(ただし途中でデータが見つからない最悪の場合で式を示す)

データ件数0件では、if,R==L,return 0の処理を行う。このため、以下の様な再帰方程式の細小時での処理時間は、

  … ①

となる。(find(件数=1)の次は必ずfind(件数=0)が実行されるのででも良い。)

Nは整数という条件をつけないと、N=1/2, 1/4, 1/8…で止まらない…と勘違いする人もいるし、データ件数が1件になったら再帰がとまると考えた方が分かりやすいので、の方が都合がいいかな…

データが1以上の時で、対象データが L..Mの範囲にあるのなら、再帰の時に対象データ件数は半分になるから、if,R==L,else,if,array[M]==key,else-if,array[M]>keyの処理時間(Tb) と find(…,L,M,…) の処理時間を要するので、次の式となる。

  … ②

一方、(M+1)..Rの範囲にあるのなら同様に、if,R==L,else,if,array[M]==key,else-if,array[M]>key,elseの処理時間(Tc)と、find(…,M+1,R,…) の処理時間なので、

  … ③

となる。ただ、処理時間の見積もりでは厳密な分析が求められないので、(N-1)/2 だと一般式が複雑になるので、N/2 で考える。さらにTbTcの処理時間は少しの時間の違いだし、確率1/2でTbTcのどちらかを実行するので、その平均時間をTbで表すことにすれば、③は②とほぼ同じと見なすことができるので、再帰方程式は①と②で良い。

fib()の再帰方程式

再帰のフィボナッチ数 fib() の処理時間に相応しい再帰方程式は、xの値(Nとする)が2以下の時は、return を実行するだけ。3以上の時は、if,else,return,+ の処理時間と、fib(x-2)の処理時間、fib(x-1)の処理時間を要する。

よって、再帰方程式は、以下の式となる。

これを代入法で一般式を求めると、T(N)=fib(N-2)×Tb+fib(N+1)×Tかな?よって、再帰のfib()の処理時間は、フィボナッチ数に比例する。ちなみに、フィボナッチ数ピネの公式で一般項が示されているので、処理時間のオーダーは、次式となる。

コンピュータとN進数

3年の情報制御基礎の授業の一回目。この授業では、情報系以外の学生も受講することから、基礎的な共通的な話題を中心に説明を行う。

情報制御基礎のシラバス

情報制御基礎では、ここに上げたシラバスに沿って授業を行う。

基本的に、センサーから読み取ったデータを使って動くシステムを作る場合の、知識ということでアナログ量・デジタル量の話から、移動平均やデータ差分といった数値処理や、そこで求まった値を制御に用いるための基礎的な話を行う。

コンピュータと組み込み系

最近では、コンピュータといっても様々な所で使われている。(1)科学技術計算用の大型コンピュータやインターネットの処理を行うサーバ群、(2)デスクトップパソコン、(3)タブレットPCやスマートフォンのような端末、(4)電化製品の中に収まるようなワンチップコンピュータなどがある。


(1) サーバ:ブレードサーバ

(4) ワンチップコンピュータ:PIC

身近で使われている情報制御という点では、(4)のような小型のコンピュータも多く、こういったものは組み込み型コンピュータとも呼ばれる。しかし、こういったコンピュータは、小さく機能も限られているので、

  • 組み込み系では、扱える数値が8bit や 16bit といった精度しかなかったり、
  • 複雑な計算をするには、処理時間がかかったりする

ため、注意が必要である。

この情報制御基礎の授業では、組み込み系のコンピュータでも数値を正しく扱うための知識や、こういった小さいコンピュータで制御を行うことを踏まえた知識を中心に説明を行う。

2進数と10進数

コンピュータの中では、電圧が高い/低いといった状態で0と1の2通りの状態を表し、その0/1を組み合わせて、大きな数字を表す(2進数)。

練習として、2進数を10進数で表したり、10進数を2進数に直してみよう。

N進数を10進数に変換

N進数で “abcde” があったとする。(2進数で”10101″とか、10進数で”12345″とか)

この値は、以下のような式で表せる。

(例1)

(例2)

10進数をN進数に変換

N進数のは、前式を変形すると、以下のような式で表せることから、

値をNで割った余りを求めると、N進数の最下位桁eを取り出せる。

このため、10進数で与えられた35を2進数に変換するのであれば、35を2で次々と割った余りを、下の桁から書きならべれば2進数100011)2が得られる。

実数の場合

途中に小数点を含むN進数のab.cde)Nであれば、以下の値を意味する。

ここで、小数点以下だけを取り出した、0.cde)Nを考えると、

の値に、Nをかけると、次のように変形できる。

この式を見ると、小数部にNをかけると、整数部分に小数点以下1桁目が取り出せる

このため、10進数で与えられた、0.625を2進数に変換するのであれば、0.625に次々と2をかけて、その整数部を上の桁から書きならべれば、2進数0.101)2が得られる。

ただし、10進数で0.1という値で、上記の計算を行うと、延々と繰り返しが発生する。つまり、無限小数になるので注意せよ。

2の補数と負の数

コンピュータの中で引き算を行う場合には、2の補数がよく使われる。2の補数とは、2進数の0と1を入替えた結果(1の補数)に、1を加えた数である。

元の数に2の補数を加えると(2進数が8bitの数であれば)、どのような数でも1,0000,0000という値になる。この先頭の9bit目が必ずはみ出し、この値を覚えないのであれば、元の数+2の補数=0とみなすことができる。このことから、2の補数= (-元の数) であり、負の数を扱うのに都合が良い。

練習問題

(1) 自分の誕生日で、整数部を誕生日の日、小数点以下を誕生日の月とした値について、2進数に変換せよ。(例えば、2月7日の場合は、”7.02″という小数点を含む10進数とする。)

変換の際には、上の説明の中にあるような計算手順を示すこと。また、その2進数を10進数に直し、元の値と同じか確認すること。(ただし、結果の2進数が無限小数になる場合最大7桁まで求めれば良い。同じ値か確認する際には無限少数の場合は近い値になるか確認すること)

(2) 自分の誕生日の日と、自分の学籍番号の下2桁の値を加えた値について、8bitの2進数で表わせ。(2月7日生まれの出席番号13番なら7+13=21)

その後、8bitの2進数として、2の補数を求めよ。また、元の数と2の補数を加えた値についても検証すること。

VSCodeとnode.js

サーバを使ったセキュリティの実験で、VSCode の Remote-ssh を使って作業を行う方式をとっているが、実験中に何気なくpsコマンドを実行したら、入れた記憶のない node が動いている。

確認したら、$HOME/.vscode-server ディレクトリの中に、色々とファイルが置かれ、node.js などを使っている見たい。ls -R .vscode-server しても大量のファイルがある。

emacs の tramp みたいに、その都度 ssh でファイルをコピーしているのかと思ったけど、なんかややこしそうなテクニックを使っているみたいだな。

創造工学演習・予備実験・PHPとDB

インターネットを活用したプログラムを作成する場合、データを保存管理するためのデータベースと、データベースのデータを処理するためのプログラム言語が必要となってくる。今回の予備実験では、そのためにリレーショナルデータベースと、Webの動的なプログラム言語である PHP について説明する。

リレーショナル・データベース

データベースは、データを保存し、矛盾が発生しない様に管理してくれるシステムであり、インターネットで活用されている。

データを確実に保存し、矛盾なく扱うためには、本来複雑なプログラムが必要となる。この中で、データを表形式のテーブルを組み合わせて管理するシステムはリレーショナルデータベースと呼ばれる。リレーショナルデータベースでは、データの問い合わせなどの処理が簡単にできるように、SQL と呼ばれる言語を使って処理を行う。

大量のデータをインターネットの中で利用するためには、ネットワークを経由してデータの問い合わせが求められ、有名なデータベースシステムには、Oracle, MySQL などがある。今回の実験では、ネットワーク機能は持たないが簡単な手続きで使うことができる SQLite を使って説明する。

また、今回の予備実験では時間も限られることから、複数の表を組み合わせた SQL の処理については割愛する。

SQLの基本

リレーショナルデータベースでは、データの基本は表形式データであり、1つの表に相当するデータはテーブルと呼ぶ。

以下の様な名前・住所・年齢のデータがあったとすると、1人前のデータをレコードと呼び、name, addr, age といった属性はカラムと呼ぶ。

name addr age
t-saitoh 越前市 55 ←レコード
sakamoto 福井市 50
murata 福井市 35
↑カラム

データの型には、文字列型(char型,varchar型,text型)や、数値型(integer型,decimal型,real型)などがあり、create table 文にてカラムの型を定義する。

create table テーブルを作る

データベースの表を使う最初には、create table 文を実行する。C言語での struct 文をイメージすると解り易いかもしれないが、データはデータベースの中に永続的に保存されるので、システムを動かす最初に一度実行するだけで良い。

上記のような名前・住所・年齢のデータ構造であれば、次の様な create table 文を使う。

create table テーブル名 (
    カラム名1  型1 ,
    カラム名2  型2 
    ) ;
-- 例 --
create table PERSON (        -- テーブル名:PERSON
    name  varchar( 20 ) ,    -- 名前
    addr  varchar( 20 ) ,    -- 住所
    age   integer ,          -- 年齢
    primary key( name )      -- name はデータ検索のキーであり重複は許されない
    ) ;

これと同じ様な処理をC言語で書くのであれば、以下の様な構造体宣言と同じであろう。

struct PERSON {
    char name[ 20 ] ;    // 名前
    char addr[ 20 ] ;    // 住所
    int  age ;           // 年齢
} ;

drop table テーブルを消す

データベースは永続的に保存されるので、テーブル全体のデータが不要であれば、drop table 命令で、テーブル全体を消す。

drop table テーブル名 ;
-- 例 --
drop table PERSON ;

insert into レコードを追加

データベースに1レコードを保存するには、insert文を用いる。

insert into テーブル名 ( カラム名... ) values( 値... ) ;
-- 例 --
insert into PERSON ( name ,       addr ,    age )
            values ( 't-saitoh' , '越前市' , 55  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'sakamoto' , '福井市' , 50  ) ;
insert into PERSON ( name ,       addr ,    age )
            values ( 'murata' ,   '福井市' , 35  ) ;

delete レコードを消す

データベースのレコードを消すには、delete 文を用いる。条件を満たす複数のデータをまとめて消すことができる。

delete from テーブル名 where 条件 ;
-- 例 --
-- 40歳未満のデータを全て消す。 murata,福井市,35 が消える。
delete from PERSON
       where age < 40 ;

update レコードを更新

データベースのレコードを修正するには、update 文を用いる。条件を満たす複数のデータをまとめて修正することもできる。

update テーブル名 set カラム = 値 where 条件 ;
-- 例 --
-- 住所が越前市のレコードの年齢を 0 にする。
update PERSON set age = 0
       where addr == '越前市' ;

select データを探す

データベースの内容を参照するための命令が select 文。where を記載することで、特定の条件のデータだけを選択したり、特定のカラムだけを抽出することができる。

select カラム名 from テーブル名 where 条件 ;
-- 例 --
-- PERSON の全データを出力
select * from PERSON ;

-- PERSON の住所が福井市だけを選別し、名前と住所を抽出
select name,addr from PERSON
       where addr = '福井市' ;

-- PERSON の年齢の最高値を出力 (集約関数)
select max(age) from PERSON
       where addr = '福井市' ;

-- PERSON の年齢条件を満たす人数を数える (集約関数)
select count(name) from PERSON
       where age >= 50 ;

動的なプログラム言語とPHP

本来、Webサーバが作られた頃は、論文や研究用のデータを公開する物であったが、扱うデータが増えるにつれ、特定の論文や研究データの一覧を表示したり探したりという処理が求められた。こういった処理のためにWebページのアクセスを受けた時に処理を実行する CGI という機能があったが、これを発展させてできたプログラム言語が PHP である。

PHPでは、ページを表示するための HTML の中に <?php?> のといった開始タグ・終了タグの中に、ブラウザから送られてきたデータに合わせて、処理を行うPHPの命令を記述し、データを(一般的にはHTML形式で)表示することができる。基本文法は C 言語に似ているが、様々なデータを扱うために変数にはどのような型でも保存できるようになっている。

ブラウザからデータを送るためのform文

ブラウザで入力欄を作ったり選択肢を表示し、その結果を送るための HTML は、入力フォーム(form)と呼ぶ。

<form method="get" action="処理ページ" >

  <input type="text" name="変数名" />

  <input type="radio" name="変数名" value="値" />
  <input type="checkbox" name="変数名" value="値" />

  <textarea cols="横文字数" rows="行数"></textarea>

  <select name="変数名">
    <option value="値1">表示1</option>
    <option value="値2">表示2</option>
  </select>
  <input type="submit" value="実行ボタンに表示する内容" />
</form>

formでは、入力する項目に変数名の名前を付け、action=”” で示したページにデータを送る。

PHPのプログラムの基本

PHPのプログラムは、外見は一般的に HTML ファイルであり、途中で <?php のタグからは、?> までの範囲が、PHP で処理が行われる。PHP のプログラムで print が実行されると、その場所に print 内容が書かれているような HTML ファイルが生成され、ブラウザで表示される。

PHP の中で変数は、$ で始まり、型宣言は基本的に不要である。

文字データを連結する場合は、”.” 演算子を使う。ダブルクオテーション”…”で囲まれた文字列の中の $名前 の部分は、変数名として扱われ、変数名の内容に置き換えられる。

HTMLのform文の action 属性で示された php であれば、PHPの中で送られてきた値を $_GET[‘変数名’] (method=”get”の場合)、 $_POST[‘変数名’] (method=”post”の場合)、または $_REQUEST[‘変数名’] (method=”get” or “post”) で参照できる。

((( sample.php )))
<html>
   <head>
      <title>sample.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <form action="sample.php" method="POST">
         <input name="A" type="text" />     <!-- 変数 $A -->
         +
         <input name="B" type="text" />     <!-- 変数 $B -->
         =
         <?php 
            ini_set( 'error_reporting' , E_WARNING ) ;
            if ( $_REQUEST[ "A" ] != "" && $_REQUEST[ "B" ] != "" ) {
               print $_REQUEST[ "A" ] + $_REQUEST[ "B" ] ;
            } else {
               print "<INPUT TYPE=submit>" ;
            }
         ?>
      </form>
   </body>
</html>

PHPでデータベースを扱う

SQLのデータベースを、プログラム言語の中で扱う場合は、その記述も色々である。PHPでは以下の様にSQLを扱う。

((( survey-init.php )))
<html>
   <head>
      <title>survey_init.php</title>
      <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
   </head>
   <body>
      <?php
         // デバッグ用にエラー警告を表示する
         ini_set( 'error_reporting' , E_WARNING ) ;
         // データベースに接続する
         $data_dir = "../public_data" ;
         $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;
         // データベースを初期化する
         $init_sql = "drop table if exists Survey ;"
                   . "create table Survey ("
                   . "  uid  varchar( 20 ) ,"
                   . "  item varchar( 10 )"
                   . ") ;"
                   . "insert into Survey ( uid , item ) values ( 't-saitoh' , '猫'        ) ;"
                   . "insert into Survey ( uid , item ) values ( 'tomoko' ,   'ケーキ'     ) ;"
                   . "insert into Survey ( uid , item ) values ( 'mitsuki' ,  'ボードゲーム' ) ;"
                   ;
         if ( $dbh->exec( $init_sql ) < 0 ) {
            print "Error: $init_sql" ;
         }
         // データベースの表形式を読み出し、表形式で出力する。
         print "<table border='1'>\n" ;
         print "<tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;
         $select_sql = "select uid,item from Survey ;" ;
         foreach( $dbh->query( $select_sql ) as list( $uid , $item ) ) {
            print "<tr><td>$uid</td><td>$item</td></tr>\n" ;
         }
         print "<table>\n" ;

         // データベースの単一データを取り出す
         $count_sql = "select count(item) from Survey where item = 'ケーキ' ;" ;
         print $dbh->query( $count_sql )->fetchColumn() ;
      ?>
   </body>
</html>

PHPの主要なSQL関数(PDO)

$dbh = new PDO(…) ; データベースに接続するハンドラを取得。
$dbh->exec( “create…” ) ; データベースでSQLを実行。
$dbh->query( “select…” ) ; データベースに問い合わせ。「1レコードに対応した配列」が全データだけ繰り返す、2次元配列を返す。
$dbh->query( “…” )->fetchColumn() 結果が1つだけの問い合わせ。集約関数の結果を参照する場合に用いる。

練習問題(1)

  • 上記の survey-init.php の select 文の部分を編集し、色々なデータ検索を試してみよ。

入力フォームのデータをデータベースに書き込む

((( survey-vote.php )))
<?php
    // エラー警告を表示                                                                                                     
    ini_set( 'error_reporting' , E_WARNING ) ;

    // form から送られてきた変数を保存                                                                                      
    $uid  = $_REQUEST[ "uid" ] ;
    $item = $_REQUEST[ "item" ] ;

    // データベースに接続する                                                                                               
    $data_dir = "../public_data" ;
    $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ;

    // データベースに項目を追加する                                                                                         
    if ( $uid != "" && $item != "" ) {
        $insert_sql = sprintf( "insert into Survey( uid , item ) values ( %s , %s ) ;" ,
                               $dbh->quote( $uid ) , $dbh->quote( $item ) ) ;
        $dbh->exec( $insert_sql ) ;

        // reload処理で追記しないためページを強制的に再表示させる                                                           
        header( "Location: survey-vote.php" ) ;
    }
?>
<html>
  <head>
    <title>survey_vote.php</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
  </head>
  <body>
    <form method="get" action="survey-vote.php">
       名前:   <input type="text" name="uid" />
       好きな物:<input type="text" name="item" />
       <input type="submit" value="投票" />
    </form>
    <?php
      // データベースの表形式を読み出し、表形式で出力する。                                                                   
      print "<table border='1'>\n" ;
      print "  <tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ;

      $select_sql = "select uid,item from Survey ;" ;
      foreach( $dbh->query( $select_sql ) as list( $t_uid , $t_item ) ) {
          print "  <tr><td>$t_uid</td><td>$t_item</td></tr>\n" ;
      }
      print "</table>\n" ;
    ?>
  </body>
</html>

練習問題(2)

  • 上記の survey-vote.php のプログラムを編集し色々な入力方法・出力方法を試してみよ。
    • 例えば、入力の item 選択に select や ラジオボタン フォームを使う。
    • 例えば、出力結果で、item の投票結果を、棒グラフで出力する。

複素数クラスによる演習

コンストラクタ

プログラミングでは、データの初期化忘れによる間違いもよく発生する。これを防ぐために、C++ のクラスでは、コンストラクタ(構築子)がある。データ構造の初期化専用の関数。

// コンストラクタ
#include <stdio.h>
#include <string.h>

class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   void print() {
      printf( "%s %d¥n" , name , age ) ;
   }
   Person() {                             // コンストラクタ(A)
      name[0] = '¥0' ; // 空文字列
      age = 0 ;
   }
   Person( const char str[] , int ag ) {  // コンストラクタ(B)
      strcpy( name , str ) ;
      age = ag ;
   }
   ~Person() {                            // デストラクタ
      print() ; // 内容の表示
   }
} ;
int main() {
   Person saitoh( "t-saitoh" , 55 ) ;     // (A)で初期化
   Person tomoko() ;                      // (B)で初期化
   saitoh.print() ;  // "t-saitoh 55" の表示
   tomoko.print() ;  // " 0" の表示

   return 0 ;        // この時点で saitoh.~Person()
                     // tomoko.~Person() が自動的に
}                    // 呼び出される。

コンストラクタと反対に、デストラクタは、データが不要となった時に自動的に呼び出される関数。

このクラスの中には、引数無しのコンストラクタと、引数ありのコンストラクタが出てくる。C++では、同じ名前の関数でも引数の数や型に応じて呼出す関数を適切に選んでくれる。(関数のオーバーロード)

デストラクタは、データが不要となった時に自動的に呼び出してくれる関数で、一般的にはC言語でのファイルの fopen() , fclose() のようなものを使う処理で、コンストラクタで fopen() , デストラクタで fclose() を呼出すように使うことが多いだろう。同じように、コンストラクタで malloc() を呼出し、デストラクタで free() を呼出すというのが定番の使い方だろう。

複素数クラスの例

隠蔽化と基本的なオブジェクト指向の練習課題として、複素数クラスをあげる。ここでは、複素数の加算・乗算を例に説明をするので、減算・除算などの処理を記述することで、クラスの扱いに慣れてもらう。

直交座標系

#include <stdio.h>
#include <math.h>

// 直交座標系の複素数クラス
class Complex {
private:
   double re ; // 実部
   double im ; // 虚部
public:
   void print() {
      printf( "%lf + j%lf¥n" , re , im ) ;
   }
   Complex( double r , double i ) {
      re = r ;
      im = i ;
   }
   Complex() {
      // デフォルトコンストラクタ
      re = im = 0.0 ;
   }
   void add( Complex z ) {
      // 加算は、直交座標系だと極めてシンプル
      re = re + z.re ;
      im = im + z.im ;
   }
   void mul( Complex z ) {
      // 乗算は、直交座標系だと、ちょっと煩雑
      double r = re * z.re - im * z.im ;
      double i = re * z.im + im * z.re ;
      re = r ;
      im = i ;
   }
   double get_re() {
      return re ;
   }
   double get_im() {
      return im ;
   }
   double get_abs() { // 絶対値
      return sqrt( re*re + im*im ) ;
   }
   double get_arg() { // 偏角
      return atan2( im , re ) ;
   }
} ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね
int main() {
   // 複素数を作る
   Complex a( 1.0 , 2.0 ) ;
   Complex b( 2.0 , 3.0 ) ;

   // 複素数の計算
   a.print() ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;

   return 0 ;
}

極座標系

上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。

// 局座標系の複素数クラス
class Complex {
private:
   double r ;  // 絶対値 r
   double th ; // 偏角   θ
public:
   void print() {
      printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ;
   }
   Complex() {
      r = th = 0.0 ;
   }
   // 表面的には、同じ使い方ができるように
   //  直交座標系でのコンストラクタ
   Complex( double x , double y ) {
      r  = sqrt( x*x + y*y ) ;
      th = atan2( y , x ) ;    // 象限を考慮したatan()
   }
   // 極座標系だと、わかりやすい処理
   void mul( Complex z ) {
      // 極座標系での乗算は
      r = r * z.r ;    // 絶対値の積
      th = th + z.th ; // 偏角の和
   } 
   // 反対に、加算は面倒な処理になってしまう。
   void add( Complex z ) {
      ; // 自分で考えて
   }
   // 
   double get_abs() {
      return r ;
   }
   double get_arg() {
      return th ;
   }
   double get_re() {
      return r * cos( th ) ;
   }
   double get_im() {
      return r * sin( th ) ;
   }
} ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;

このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。

このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。

メソッドのプロトタイプ宣言

class 構文では、{} の中に、要素の定義や、メソッドの記述を行うと説明してきたが、メソッド内の処理が長い場合もある。

この時に、すべてを {} の中に書こうとすると、全体像が見渡せない。こういう時には、以下のように、メソッドのプロトタイプ宣言と、メソッドの実体の記述を別に記載する。

class Complex {
private:
   double re , im ;
public:
   Complex( double r , double i ) ; // メソッドのプロトタイプ宣言
   void print() ;
} ;
// メソッドの実体
Complex::Complex( double r , double i ) {
   re = r ;
   im = i ;
}
void Complex::print() {
   printf( "%lf + j %lf" , re , im ) ;
}

ゲッター/セッター (経験者向け解説)

それぞれのクラス宣言では、get_re() , get_im() , get_abs() , get_arg() というメソッドを記載した。このように記述しておくと、クラス外で re , im といったメンバを public 指定をせずに、リファクタリングしやすいクラスにすることができる。(re, im を public にしてしまうと、クラス外でオブジェクトへの代入が可能となる。)

PHPなどの private や public の機能のないオブジェクト指向言語では、get_xx() といった要素の参照しかできないメソッドを作ったうえで、クラス外でメンバ参照をしないというマナーを徹底させることで、public 機能の代用し、隠蔽化を徹底させることも多い。

この場合、参照専用の get_xx() と同じように、要素に値を設定するためのメソッド set_xx( 値… ) を作るとプログラムの意味が分かりやすくなる。こういったクラスの参照や代入のメソッドは、getter(ゲッター),setter(セッター)と呼ぶ。

ゲッターやセッターメソッドでは、要素を参照(あるいは代入)するだけといった極めて単純な関数を作ることになる。この場合、関数呼び出しの処理時間が無駄になる。この対処として、C++ には inline 関数機能がある。関数(メソッド)の前に、inline を指定すると、コンパイラは関数呼び出し用の命令を生成せず、それと同じ処理となる命令を埋め込んでくれる。(開いたサブルーチン)

class Complex {
private:
   double re , im ;
public:
   :
   inline void get_re() {
      return re ;
   }
} ;

const 指定 (経験者向け解説)

C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。

void foo( const int x ) {
   x++ ; // 定数を書き換えることはできない。
   printf( "%d\n" , x ) ;
}
int main() {
   const double pi = 3.141592 ;
   // C言語で #define PI 3.141592 と同等

   int a = 123 ;
   foo( a ) ;

   return 0 ;
}

前に説明した、getter メソッドは要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、

class ... {
   :
   inline double get_re() const {
      re = 0 ; // 文法エラー
      return re ;
   }
} ;

 

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー