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は省略)
悪趣味なプログラム
#include <stdio.h>
int a[ 3 ] = { 11 , 22 , 33 } ;
int main() {
for( int i = 0 ; i < 3 ; i++ ) {
printf( "%d¥n" , a[ i ] ) ; // 普通の書き方
printf( "%d¥n" , i[ a ] ) ; // 悪趣味な書き方
}
for( int i = 0 ; i < 7 ; i++ ) {
printf( "%c" , "abcdefg"[ i ] ) ;
}
printf( "¥n" ) ;
}
ポインタ処理
ここからは、次のメモリの消費を考慮したプログラムの説明を行うが、ポインタの処理に慣れない人が多いので、ポインタを使ったプログラミングについて説明を行う。
値渡しとポインタ渡し
大きなプログラムを作成する場合、変数名の使い方には注意が必要となる。大域変数は、どこでも利用できるが、間違った使い方をすると値が予想外の変化があったりするため危険である。一方で、局所変数を使うと、関数呼び出しでデータの受け渡しに注意が必要となる。
値渡し(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)と言う。実引数の値は、仮引数の変数に copy し代入される。
でも、プログラムによっては、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つの値しか受け取ることができないので、上記のようにポインタを使って、呼び出し側は：結果を入れてもらう場所を伝え、関数側は：指定されたアドレスに結果を書き込む。
変数の寿命とスコープ
変数の管理では、変数の寿命とスコープの理解が重要。
静的変数：変数は、プログラムの起動時に初期化、プログラムの終了時に廃棄。
動的変数：変数は、関数に入るときに初期化、関数を抜けるときに廃棄。
もしくは、ブロックに入るときに初期化、ブロックを抜けるときに廃棄。
大域変数：大域変数は、プログラム全体で参照できる。
局所変数：関数の中 or そのブロックの中でのみ参照できる。
ブロックの中で変数が宣言されると、そのブロックの外の変数とは別の入れ物となる。そのブロックの中では、新たに宣言された変数が使われる。
int i = 111 ; // 静的大域変数
void foo() {
int i = 222 ; // 動的局所変数
i++ ;
printf( "%d\n" , i ) ;
}
void bar() {
static int i = 333 ; // 静的局所変数(プログラム起動時に初期化)
i++ ;
printf( "%d\n" , i ) ;
}
void hoge( int x ) { // x: 動的局所変数(値渡し)
x++ ;
printf( "%d\n" , x ) ;
}
void fuga( int* p ) { // p: 動的局所変数(ポインタ渡し)
(*p)++ ;
printf( "%d\n" , (*p) ) ;
}
int main() {
int i = 444 , j = 555 ;
foo() ; // 223 (副作用ナシ)
bar() ; // 334
hoge( i ) ; // 445 (副作用ナシ)
fuga( &j ) ; // 556
printf( "%d\n" , i ) ;
foo() ; // 223 (副作用ナシ)
bar() ; // 335
hoge( i ) ; // 445 (副作用ナシ)
fuga( &j ) ; // 557
printf( "%d\n" , i ) ; // 444
for( int i = 0 ; i < 2 ; i++ ) { // (a) // A:0
printf( "A:%d\n" , i ) ; // B:0
for( int i = 0 ; i < 2 ; i++ ) { // (b) // B:1
printf( "B:%d\n" , i ) ; // A:1
} // B:0
} // B:1
printf( "%d\n" , i ) ; // 333 ← 要注意C言語のバージョンによっては
// 2 になる場合あり。(a)の変数iの値
return 0 ;
}
ポインタの加算と配列アドレス
ポインタに整数値を加えることは、アクセスする場所が、指定された分だけ後ろにずれることを意味する。
// ポインタ加算の例
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 だけを記述すると、配列の先頭を意味することに注意。
ポインタインクリメントと式
C言語では、ポインタを動かしながら処理を行う場合に以下のようなプログラムもよくでてくる。
// string copy 配列のイメージで記載
void strcpy( char d[] , char s[] ) {
int i ;
for( i = 0 ; s[ i ] != '¥0' ; i++ )
d[ i ] = s[ i ] ;
d[ i ] = '¥0' ;
}
int main() {
char a[] = "abcde" ;
char b[ 10 ] ;
strcpy( b , a ) ;
printf( "%s¥n" , b ) ;
return 0 ;
}
しかし、この strcpy は、ポインタを使って書くと以下のように書ける。
// string copy ポインタのイメージで記載
void strcpy( char* p , char* q ) {
while( *q != '¥0' ) {
*p = *q ;
p++ ;
q++ ;
}
*p = '¥0' ;
}
// ポインタ加算と代入を一度に書く
void strcpy( char* p , char* q ) {
while( *q != '¥0' )
*p++ = *q++ ; // *(p++) = *(q++)
}
// ポインタ加算と代入と'¥0'判定を一度に書く
void strcpy( char* p , char* q ) {
while( (*p++ = *q++) != '¥0' ) // while( *p++ = *q++ ) ; でも良い
;
}
構造体とポインタ
構造体を関数に渡して処理を行う例を示す。
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年度中間試験問題より)
再帰呼び出しと再帰方程式
前回の授業では、簡単な再帰呼び出しのプログラムについて再帰方程式などの説明を行った。今日の授業では、ハノイの塔の処理時間や、マージソートのプログラムの処理時間について検討を行う。
ハノイの塔
ハノイの塔は、３本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。
一般解の予想
ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。
… ①
この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。
再帰方程式
上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、
… ②
… ③
ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、
枚では、
… ③より
… ①を代入
となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。
理解度確認
- 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
- 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
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つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。
- 参考: マージソート(併合整列法)
このことから、再帰方程式は、以下のようになる。
この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。
：
よって、処理時間のオーダはとなる。
選択法とクイックソートの処理時間の比較
データ数 N = 20 件でソート処理の時間を計測したら、選択法で 10msec 、クイックソートで 20msec であった。
- データ件数 N = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
- データ件数何件以上なら、クイックソートの方が高速になるか答えよ。
設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓などが必要。[解説]
再帰呼び出しの処理時間の見積もり
前回の授業の復習と練習問題
前回の授業では、for ループによる繰り返し処理のプログラムについて、処理時間を T(N) の一般式で表現することを説明し、それを用いたオーダー記法について説明を行った。理解を確認するための練習問題を以下に示す。
練習問題
- ある処理のデータ数Nに対する処理時間が、
であった場合、オーダー記法で書くとどうなるか？
の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？また、このような処理時間となるアルゴリズムの例を答えよ。
の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか？
(ヒント: ロピタルの定理)
- 1は、N→∞において、N2 ≪ 2Nなので、O(2N) 。厳密に回答するなら、練習問題3と同様の証明を行うべき。
- 2は、O(1)。誤答の例：O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
- 3の解説
再帰呼び出しの基本
次に、再帰呼び出しを含むような処理の処理時間見積もりについて解説をおこなう。そのまえに、再帰呼出しと簡単な処理の例を説明する。
再帰関数は、自分自身の処理の中に「問題を小さくした」自分自身の呼び出しを含む関数。プログラムには問題が最小となった時の処理があることで、再帰の繰り返しが止まる。
// 階乗 (末尾再帰)
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(N) を求める処理は、以下の様に再帰が進む。
また、フィボナッチ数列 fib(N) を求める処理は以下の様に再帰が進む。
再帰呼び出しの処理時間
次に、この再帰処理の処理時間を説明する。 最初のfact(),pyra()については、 x=1の時は、関数呼び出し,x<=1,return といった一定の処理時間を要し、T(1)=Ta で表せる。 x>1の時は、関数呼び出し,x<=1,*,x-1,returnの処理(Tb)に加え、x-1の値で再帰を実行する処理時間T(N-1)がかかる。 このことから、 T(N)=Tb=T(N-1)で表せる。
} 再帰方程式
このような、式の定義自体を再帰を使って表した式は再帰方程式と呼ばれる。これを以下のような代入の繰り返しによって解けば、一般式 が得られる。
T(1)=Ta
T(2)=Tb+T(1)=Tb+Ta
T(3)=Tb+T(2)=2×Tb+Ta
:
T(N)=Tb+T(N-1)=Tb + (N-2)×Tb+Ta
一般的に、再帰呼び出しプログラムは(考え方に慣れれば)分かりやすくプログラムが書けるが、プログラムを実行する時には、局所変数や関数の戻り先を覚える必要があり、深い再帰ではメモリ使用量が多くなる。
ただし、fact() や pyra() のような関数は、プログラムの末端で再帰が行われている。(fib()は、再帰の一方が末尾ではない)
このような再帰は、末尾再帰(tail recursion) と呼ばれ、関数呼び出しの return を、再帰処理の先頭への goto 文に書き換えるといった最適化が可能である。言い換えるならば、末尾再帰の処理は繰り返し処理に書き換えが可能である。このため、末尾再帰の処理をループにすれば再帰のメモリ使用量の問題を克服できる。
再帰を含む一般的なプログラム例
ここまでのfact()やpyra()のような処理の再帰方程式は、再帰の度に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 は、合計範囲の 左端(左端のデータのある場所)・右端(右端のデータのある場所+1)を表している。そして、再帰のたびに２つに分割して解いている。
このような、処理を(この例では半分に)分割し、分割したそれぞれを再帰で計算し、その処理結果を組み合わせて最終的な結果を求めるような処理方法を、分割統治法と呼ぶ。
このプログラムでは、対象となるデータ件数(R-L)をNとおいた場合、実行される命令からsum()の処理時間Ts(N)は次の再帰方程式で表せる。
← Tβ + (L〜M)の処理時間 + (M〜R)の処理時間
これを代入の繰り返しで解いていくと、
ということで、このプログラムの処理時間は、 で表せる。
繰り返し処理と処理時間の見積もり
単純サーチの処理時間
ここで、プログラムの実行時間を細かく分析してみる。
// ((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 ;
例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その１つ１つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,
,
,
とする。
この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。
ここで例題
この単純サーチのプログラムを動かしてみたら、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μ秒 となる。
2分探索法と処理時間
次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。
// ((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 ;
}
このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、
件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。
…両辺のlogをとる
2分探索は、繰り返し処理であるから、処理時間は、
ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式で係数が出てくるが、これはTβに含めて考えればいい。
単純なソート(選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。
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)は…
… i=0の時
… i=1の時
:
… i=N-1の時
…(参考 数列の和の公式)
となる。
オーダー記法
ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、
の部分の方が重要である。
| 単純サーチ | |
| ２分探索法 | |
| 最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。
| 単純サーチ | オーダーNのアルゴリズム | |
| 2分探索法 | オーダー log N のアルゴリズム | |
| 最大選択法 | オーダー N2 のアルゴリズム |
練習問題
- ある処理のデータ数Nに対する処理時間が、
- コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか？
(ヒント: 底変換の公式)
(ヒント: ロピタルの定理)
- 2と4の解説
- 1は、N→∞において、N2 ≪ 2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の説明を行う。
- 3は、O(1)。誤答の例：O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
再帰呼び出しの予習
次の講義の基礎を確認という意味で、再帰呼出しと簡単な処理の例を説明する。
最初に定番の階乗(fact)
次に、フィボナッチ数列の場合
次の講義への導入問題
ここで示す導入問題をすべて答えるには、若干の予習が必要です。まずはどういう考え方をすれば解けるかな…を考えてみてください。
- fact(N)の処理時間を、Tfact(N) = … のような式で表現し、処理時間をオーダ記法で答えよ。
- 以下のプログラムの実行結果を答えよ。また、関数sum()の処理時間を対象となるデータ件数N=R–Lを用いて Tsum(N) = …のような式で表現せよ。
int a[] = { 1 , 5 , 8 , 9 , 2 , 3 , 4 , 7 } ;
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( a , 0 , 8 ) ) ;
return 0 ;
}
情報構造論ガイダンス2022
基本的なガイダンス
情報構造論のシラバスを、ここに示す。プログラムを作成する上で、どのような考え方で作れば処理速度が速いのかを議論する。基本的に、4回のテストのたびに、レポート課題を実施する。各テスト毎の評価は、テスト素点と、「テスト素点×60%+レポート評価×40%」の良い方とする。テストに自信のない人は、レポート課題をきちんと提出すること。
プログラムを評価する3つのポイント
まずは以下を読む前に、質問。
- あなたが”良い”プログラムを作るために何を考えて作りますか？ ※1
- ここまでの段階で3つの要点を考えメモしてください。
具体的な言葉で要点を考えると、いろいろなものがでてくるだろうが、端的なポイントにまとめると、次の3つに分類できるはずである。
- プログラムの速度
- プログラムのわかり易さ
- メモリの使用量
プログラムを作る場合、この３要素がトレードオフの関係にある。プログラムの速度を優先すると、プログラムが分かり難くなったり、メモリを大量浪費するものだったりする。
メモリの使用量の影響
メモリを大量に使用すると、どういった影響がでるのか？ OSの機能を知らないと、メモリ(主記憶)を使い果たしたら、プログラムが動かないと思うかもしれないけど、最近のOSは仮想メモリ機能があるため、主記憶がメモリが足りなければ待機状態のプロセスのメモリを補助記憶に保存することで、プログラムを動かすことはできる。(仮想記憶)
しかし、プロセスが切り替わる度に、補助記憶への読み書きが発生するため、処理性能は低下する。(スワッピング)
int 型のメモリ使用量
int 型は、プログラムで扱う一般的な整数を扱うのに十分なデータ型。
32bit の0/1情報の組み合わせで、232通りの情報が表現でき、負の数も扱いたいことから2の補数表現を用いることで、-231～0～231-1 の範囲を扱うことができる。231 = 2×210×210×210 ≒ 2×10003
32bit = 4byte
ソフトウェアとアルゴリズムとプログラム
用語として、ソフトウェア、アルゴリズム、プログラムという表現があるが、この違いは何か？
- アルゴリズム – 計算手順の考え方。
- プログラム – アルゴリズムを特定のプログラム言語によって記述したもの。
- ソフトウェア – プログラムと、その処理に必要なデータ。
(日本語を変換するプログラムは、日本語の辞書データが無いと動かない/役に立たない) - パラダイム – プログラムをどう表現すると分かりやすいか？
トレードオフ関係をプログラムで確認
例えば、配列の中から、目的データを探すプログラムの場合、最も簡単なプログラムは以下の方法であろう。
// ((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分探索法 O(log N)
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が決まり、その会社の人員やら経験やらでプログラム開発に使える時間がきまる。プログラムをデザインするとは、限られた条件の中で、適切な速度のコンピュータ、適切な量のメモリでコンピュータを用意し、限られた納期の中でシステムを完成させることである。
皆さんも、ゲームを買った時、処理速度が遅くてキャラクターがカクカク動いたら幻滅するでしょ？ゲームがバグですぐに変な動きしたらキレるでしょ！発売日の予定どおりに買えなかったらさみしいでしょ!!プログラムがでかすぎてローディングに時間がかかったら、寝ちゃうでしょ!!!
2021年度授業アンケート
情報制御基礎(3年学際科目)
情報構造論(4EI)
データベース(5EI)
オブジェクト指向プログラミング(専攻科生産システム2年)
昨年度の92.6ポイントより、88.9ポイントと若干低下しているが、概ね良い評価であり、今後も授業の内容を時節に応じて変化させながら実施していきたい。
情報構造論2021全講義録
- 情報構造論2021ガイダンス
- 繰り返し処理と処理時間の見積もり
- 再帰呼び出しと再帰方程式
- 再帰処理時間の見積もりとポインタ操作
- ポインタとメモリの使用効率
- malloc()とfree()
- 様々なデータの覚え方のレポート課題
- 様々な2次元配列
- リスト構造と処理
- リスト処理
- リストへの追加処理
- スタックと待ち行列
- 集合とリスト処理
- 双方向リスト
- 2分探索木
- 深さ優先探索と幅優先探索
- 2分探索木の処理とデータ追加処理
- AVLと2分ヒープ
- 意思決定木と構文解析
- 演算子と2分木による式の表現
- B木とデータベース
- ハッシュ法(導入)
- ハッシュ衝突の対策
- プログラムの処理時間の測り方
- 文字列のハッシュ関数
- 共有のあるデータの取扱い
- ガベージコレクタ
- 動的メモリ管理 malloc() と free()
- 関数ポインタ
- 情報構造論とオブジェクト指向
情報構造論とオブジェクト指向
データ構造を扱うプログラムの書き方を説明してきたが、その考え方をプログラムにするためには手間もかかる。こういった手間を少しでも減らすために、プログラム言語が支援してくれる。その代表格がオブジェクト指向プログラミング(Object Oriented Programming:略称OOP)であり、以下にその基本を説明する。
データ指向のプログラム記述
名前と年齢のデータを扱うプログラムをC言語で書く時、私なら以下のようなプログラムを作成する。
このプログラムの書き方では、saitohというデータにset_NameAge() , print_NameAge() を呼び出していて、データに対して処理を加えるという雰囲気がでている。(C言語なのでデータに処理を施す関数には、必ずどのデータに対する処理なのかを与えるポインタがある。) このようにプログラムを書くと、saitoh というデータに対して命令するイメージとなり、擬人化したデータに向かってset,printしろ…って命令しているように見える。
// 名前と年齢の構造体
struct NameAge {
char name[ 20 ] ;
int age ;
} ;
// NameAgeを初期化する関数
void set_NameAge( struct NameAge* p , char s[] , int a ) {
strcpy( p->name , s ) ;
p->age = a ;
}
// NameAgeを表示する関数
void print_NameAge( struct NameAge* p ) {
printf( "%s %d¥n" , p->name , p->age ) ;
}
void main() {
struct NameAge saitoh ;
set_NameAge( &saitoh, "t-saitoh" , 53 ) ;
print_NameAge( &saitoh ) ;
// NameAge の中身を知らなくても、
// set_NameAge(),print_NameAge() の中身を見なくても、
// saitoh を set して print する....という雰囲気は伝わるよね!!
}
このプログラムでは、例えば、データに誕生日も覚えたいという改良を加えるとしても、main の前のデータ構造と関数の部分は色々と書き換えることになるだろうけど、main の内部はあまり変わらないだろう。こういう書き方をすればプログラムを作成するときには、データ構造とそれを扱う関数を記述する人と、データ構造を使う人(main内部を書く人)と、分業ができるようになる。
隠蔽化
このような記述では、データ構造の中身を知らなくても、main で、setしてprintして…という処理の雰囲気は分かる。さらに、set_NameAge()とか、print_NameAge() の処理の中身を知らなくても、設定するとか表示するとか…は予想できる。
これは、NameAge というデータをブラックボックス化(隠蔽化)して捉えていると見れる。データ構造の中身を知らなくてもプログラムを理解できることは、データ構造の隠蔽化という。また、関数の中身を知らなくても理解できることは、手続きの隠蔽化という。
オブジェクト指向プログラミング
前述のように、プログラムを書く時には、データ構造とそのデータを扱う関数を一緒に開発する方が分かり易い。そこで、プログラム言語の文法自体を、データ構造とその関数(メソッドと呼ぶ)をまとめてクラスとして扱うプログラムスタイルが、オブジェクト指向プログラミングの基本である。
class NameAge {
private:
// データ構造の宣言
char name[ 20 ] ;
int age ;
public:
// メソッドの定義
void set( char s[] , int a ) { // 初期化関数
strcpy( name , s ) ; // どのデータに対する処理かは省略できるので、
age = a ; // データへのポインタ引数は不要。
}
void print() { // 表示関数
printf( "%s %d¥n" , name , age ) ;
}
} ;
void main() {
NameAge saitoh ;
saitoh.set( "t-saitoh" , 53 ) ; // set,printはpublicなので自由に使える。
saitoh.print() ;
// saitoh.age = 54 ; エラー：クラス外でprivateの要素は触れない。
}
このプログラムでは、saitoh というデータ(具体的なデータが割り当てられたものはオブジェクトと呼ぶ)に対して、set() , print() のメソッドを呼び出している。
# C++ではクラス毎に関数名を区別してくれるので、関数名もシンプルにset,printのようにかける。
オブジェクト指向では、データに対して private を指定すると、クラス以外でその要素やメソッドを扱うことができなくなる。一方 public が指定されたものは、クラス外で使っていい。これにより、クラスを設計する人と、クラスを使う人を明確に分けることができ、クラスを使う人が、クラス内部の変数を勝手に触ることを禁止できる。
プログラムを記述する時には、データ件数を数える時に、カウンタの初期化を忘れて動かないといった、初期化忘れも問題となる。オブジェクト指向のプログラム言語では、こういうミスを減らすために、データ初期化専用の関数(コンストラクタ)を定義することで、初期化忘れを防ぐことができる。
// コンストラクタを使う例
class NameAge {
// 略
public:
NameAge( char s[] , int a ) { // データ初期化専用の関数
strcpy( name , s ) ; // コンストラクタと呼ぶ
age = a ;
}
// 略
} ;
void main() {
NameAge saitoh( "t-saitoh" , 53 ) ; // オブジェクトの宣言と初期化をまとめて記述できる。
saitoh.print() ;
}
プログラムにオブジェクト指向を取り入れると、クラスを利用する人とクラスを記述する人で分業ができ、クラスを記述する人は、クラスを利用するプログラマーに迷惑をかけずにプログラムを修正できる。
この結果、クラスを記述する人はプログラムを常により良い状態に書き換えることができるようになる。このように、よりよく改善を常に行うことはリファクタリングと呼ばれ、オブジェクト指向を取り入れる大きな原動力となる。。
最近のC++なら
最近のオブジェクト指向プログラミングは、テンプレート機能と組み合わせると、単純リスト処理が以下のように書けてしまう。struct 宣言やmalloc()なんて出てこない。(^_^;
#include <iostream>
#include <forward_list>
#include <algorithm>
int main() {
// std::forward_list<>線形リスト
std::forward_list<int> lst{ 1 , 2 , 3 } ; // 1,2,3の要素のリストで初期化
// リスト先頭に 0 を挿入
lst.push_front( 0 ) ;
// 以下のような処理を最新のC++なら...
// * もともとのC言語なら以下のように書くだろう。
// for( struct List*p = top ; p != NULL ; p = p->next )
// printf( "%d¥n" , p->data ) ;
// * 通常の反復子iteratorを使って書いてみる。
// auto は、lst の型推論。
// ちょっと前のC++なら型推論がないので、
// std::forward_list<int>::iterator itr = lst.begin() と書く。
// * C++では演算子の処理をクラス毎に書き換えることができる。
// itr++ といっても、カウントアップ処理をする訳ではない。
for( auto itr = lst.begin() ;
itr != lst.end() ;
itr++ ) {
std::cout << *itr << std::endl ;
}
// 同じ処理を algorithm を使って書く。
std::for_each( lst.begin() ,
lst.end() ,
[]( int x ) { // 配列参照のコールバック関数
std::cout << x << std::endl ;
} );
// 特に書かなくてもデストラクタがlstを捨ててくれる。
return 0 ;
}
テンプレート機能
テンプレート機能は、実際のデータを覚える部分の型を後で指定できるようにしたデータ構造を定義する機能。
template <class > struct List { T data ; struct List* next ; } ; int main() { List<int> li ; // 整数を要素とするList型の宣言 List<double> ld ; // 実数を要素とするList型の宣言 }