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

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

// ポインタ加算の例
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 ) ; でも良い
   }
}

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

前回の授業のハノイの塔は、単純な再帰方程式で処理時間のオーダーが巨大となる一例として示した。そこで、プログラムの中でよく利用されるデータの並び替え(ソート)で処理時間の分析を行ってみる。

• ポインタについての説明は、前回の講義録資料に追記

様々なソートアルゴリズム

データの有名な並び替えアルゴリズムとその処理時間のオーダーを示す。

• バブルソート O(N²)
• 選択法 O(N²/2)
• クイックソート O( N log N )
• マージソート O( N log N )

マージソートの分析

マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

• 
• 

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが、 となる。

：

よって、

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

データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。

1. データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

この後の授業で、ポインタを使ったプログラムが増えるので、ポインタの理解の確認

ポインタと引数

値渡し

// 値渡しのプログラム
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 が表示される。
でも、プログラムによっては、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() ;                   // 表示されない。
}

静的局所変数

大域変数を使わない方法としては、静的局所変数( static )を使う方法もある。

// 静的局所変数を使う場合
void foo() {
   static int x = 123 ; // x は foo の内部でのみ使用可
                        // x はプログラム起動時に作られ 123 で初期化される。
   x++ ;
   printf( "%d¥n" , x ) ;
}
void main() {
   foo() ;  // 124
   foo() ;  // 125
   // ここで x = 321 といった代入はできない
}

静的局所変数は、変数の寿命が大域変数と同じように、プログラム起動から終了までの間だが、参照できるスコープは所属するブロック内に限られる。

ポインタ渡し

C言語で引数を通して、呼び出し側の値を変化して欲しい場合は、変更して欲しい変数のアドレスを渡し、関数側では、ポインタ変数を使って受け取った変数のアドレスの示す場所の値を操作する。

// ポインタ渡しのプログラム
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++では、ポインタ渡しを使わないようにするために、参照渡しを利用する。

参照渡し

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

ポインタ渡しを使う処理

// ポインタ渡しのプログラム
void swap( int* pa , int* pb ) {
   int t = *pa ;
   *pa = *pb ;
   *pb = t ;
}
void main() {
   int a = 123 ;
   int b = 111 ;
   swap( &a , &b ) ;
   printf( "%d %d¥n" , a , b ) ;
}

再帰関数と再帰方程式

再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。

// 階乗 (末尾再帰)
int fact( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x * fact( x-1 ) ;
}
// ピラミッド体積 (末尾再帰)
int pyra( int x ) {
   if ( x <= 1 )
      return 1 ;
   else
      return x*x + pyra( x-1 ) ;
}
// フィボナッチ数列 (非末尾再帰)
int fib( int x ) {
   if ( x <= 2 )
      return 1 ;
   else
      return fib( x-1 ) + fib( x-2 ) ;
}

これらの関数の結果について考えるとともに、この計算の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、 で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理に加え、x-1の値で再帰の処理時間がかかる。 このことから、 で表せる。

}

再帰方程式

このような再帰を使って表した式は再帰方程式と呼ばれる。これを代入によって解けば、一般式  が得られる。

fact() や pyra() のような関数は、プログラムの末端に再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に最適化が可能である。つまり繰り返し処理に書き換えが可能である。このため、ループにすれば局所変数を消費しない。

再帰を含む一般的なプログラム例

ここまでの再帰方程式は、再帰の度にNの値が1減るものばかりであった。もう少し一般的なプログラムで再帰方程式を使って処理時間を考えてみよう。
以下のプログラムを実行したらどんな値になるであろうか？それを踏まえ、処理時間はどのように表現できるであろうか？

int array[ 8 ] = {
  3 , 6 , 9 , 1 , 8 , 2 , 4 , 5 ,
} ;

int sum( int a[] , int L , int R ) { // 非末尾再帰
    if ( R - L == 1 ) {
        return a[ L ] ;
    } else {
        int M = (L + R) / 2 ;
        return sum( a , L , M ) + sum( a , M , R ) ;
    }
}
int main() {
    printf( "%d¥n" , sum( array , 0 , 8 ) ) ;
    return 0 ;
}

このプログラムでは、配列の合計を計算しているが、引数の L,R は、合計範囲の 左端・右端を表している。そして、再帰のたびに２つに分割して解いている。

このような、処理を分割し、分割した処理を再帰で計算し、その分割した処理結果を組み合わせて結果を求めるような処理方法を、分割統治法と呼ぶ。

このことから、以下の再帰方程式が得られる。

これを、代入法により解いていくと、

ということで、このプログラムの処理時間は、 で表される。

最後に、再帰方程式の事例として、ハノイの塔の処理時間について説明し、 数学的帰納法での証明を示す。

ハノイの塔

ハノイの塔は、３本の塔にN枚のディスクを積み、ディスクの上により大きいディスクを積まずに、移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、  … ① ということが予想ができる。
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚と、その上の(N-1)枚のディスクに分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
　… ③

ということが言える。(ハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

　… ③
 … ①

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

• 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
• 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)
• 再帰のフィボナッチ関数 fib() の処理時間にふさわしい再帰方程式を示せ

int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

2分探索法の処理時間の見積もり

コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか？

解答

2分探索法なので、処理時間はO(logN) であり、T(N) = T_α+T_β✕N で表される。

T(100) =10μsec = T_β✕ log 100

となる。ここで、logの底は、底変換の公式を使うと、底の違いはT_β に含めて考えればいいので、今回は10を底にして考える。

10μsec = T_β ✕ log₁₀100=T_β✕2

T_β=5μsec

よって、

T(10000) = 5μsec✕log₁₀10000=20μsec

処理時間の式をオーダ表記

の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？

解答

ここで問題となるのは、 との値が、Nが巨大な値の時にどっちが大きいかが問題となる。

そこで、それぞれの値を分子分母にして N→∞で、∞に拡散するか、0に収束するかを判定すればいい。

ここで、ロピタルの定理より、分子分母をそれぞれ微分すると、

よって、分子の方が巨大な値になるので、この処理時間は、で表せる。

先週に、単純繰り返し処理の時間分析をやったので、次のステップに。

2分探索法の処理時間

データを探す処理において、単純検索より速い方法ということで、2分探索法の処理速度見積もりを行う。

// 2分探索法　O(log N)
int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;  // データ数 N
int L = 0 ;     // L=下限のデータの場所
int R = size ;  // R=上限のデータ+1の場所
while( L != R ) {
   int M = (L + R) / 2 ;  // 計算は整数型で行われることに注意
   if ( a[M] == key )     // 見つかった
      break ;
   else if ( a[M] < key ) // |L         |M.         |R
      L = M + 1 ;         // |----------|-+---------|
   else                   // |L---------|M|
      R = M ;             //              |M+1------|R
}

上記のようなプログラムの場合、処理に要する時T(N)は、

処理は、対象となるデータ件数が繰り返し毎に半分となり、対象データ件数が1件になれば処理が終わる。このことから、

となることから、 の関係が成り立つ。よって、は、以下のように表せる。

単純なソート(最大選択法)の処理時間

次に、並べ替え処理の処理時間について考える。

int a[ 1000 ] = { 対象となるデータ } ;
int size = N ;

for( int i = 0 ; i < size - 1 ; i++ ) {
    int tmp ;
    // i..size-1 の範囲で一番大きいデータの場所を探す
    int m = i ;
    for( int j = i + 1 ; j < size ; j++ ) {
        if ( a[j] > a[m] )
            m = j ;
    }
    // 一番大きいデータを先頭に移動
    tmp = a[i] ;
    a[i] = a[m] ;
    a[m] = tmp ;
}

このプログラムの処理時間T(N)は… (参考 数列の和の公式)

となる。

オーダー記法

ここまでのアルゴリズムをまとめると、処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。

単純サーチ
２分探索法
最大選択法

そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。

単純サーチ		オーダーNのアルゴリズム
2分探索法		オーダー log N のアルゴリズム
最大選択法		オーダー N2 のアルゴリズム

練習問題

1. コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
   データ10000件なら何[sec]かかるか？
   (ヒント: 底変換の公式)
2. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？また、このようなアルゴリズムの例を答えよ。
3. の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
   (ヒント: ロピタルの定理)

• 解答

再帰呼び出しの予習

若干、時間が余ったので、再帰呼出しと簡単な処理の例を説明する。

最初に定番の階乗(fact)

次に、フィボナッチ数列の場合

情報構造論のガイダンス

プログラムを評価する3つのポイント

この授業で恒例の、プログラムを作る場合に何に気をつけてプログラムを作成するかを聞いてみた。今年は、以下に示す3要素をうまく答えてくれたかな。

• プログラムの速度
• プログラムのわかり易さ
• メモリの使用量

プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。

メモリの使用量の影響

メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)

しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)

ソフトウェアとアルゴリズムとプログラム

用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？

• アルゴリズム – 計算手順の考え方。
• プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
• ソフトウェア – プログラムと、その処理に必要なデータ。(日本語を変換するプログラムは、日本語の辞書データが無いと動かない)

トレードオフ関係をプログラムで確認

例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。

// ((case-1))
// 単純サーチ O(N)
#define SIZE 1024
int a[ SIZE ] ; // 配列
int size ;      // 実際のデータ数(Nとする)
int key ;       // 探すデータ
for( int i = 0 ; i < size ; i++ )
   if ( a[i] == key )
      break ;

しかし、もっと早く探したいのであれば、2分探索法を用いるだろう。でも、このプログラムは、case-1 のプログラムよりは分かり難い。(速度⇔わかり易さ)

// ((case-2))
// 2分探索法
int L=0 , R=size ; // プログラムは複雑になった 
while( L != R ) {
   int M = (L + R) / 2 ;
   if ( a[M] == key )
      break ;
   else if ( a[M] < key )
      L = M + 1 ;
   else
      R = M ;
}

でももっと速いプログラムとしたければ、大量のメモリを使えば一発でデータを探せる。(速度⇔メモリ使用量)

// ((case-3))
// 添字がデータ O(1)
// 探すデータが電話番号 272925 のような 6 桁ならば
int a[ 1000000 ] ;
a[ 272925 ] = 272925 ;
// 処理速度はクソ速いけど、メモリは大量消費

良いプログラムを作るとは

プログラムを作る時には、メモリが大量に使えるのなら、速いものを使えばいい。だけど実際には、そのシステムには限られた予算があるだろう。

実際には、限られる予算から、メモリやCPUが決まり、その会社の人員やら経験やらで、プログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。

動作時間の予測

ここで、プログラムの実行時間を細かく分析してみる。例えば、前節のcase-1の単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、その実行回数の繰り返した分の処理時間を要する。この時間を とする。

この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。

ここで例題

この単純サーチのプログラムを動かしてみたら、データ件数N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか？

感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、T_β,T_α は何秒だったのだろうか？ 上記のT(N)=T_α+N ✕ T_β に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。

ここで一番のポイントは、大量のデータ処理を行うのが普通だから、N が小さな値の場合はあまり考えない。N が巨大な値であれば、T_αは、1000T_βに比べれば微々たる値という点である。よって

で考えれば良い。これであれば、T(1000)=5μ秒=T_β×1000 よって、T_β=5n秒となる。この結果、T(10000)=T_β×10000=50μ秒 となる。