リストへの追加処理
最初のリスト生成の説明では、補助関数 cons を用いて、直接リストを生成していた。
しかし、実際にはデータを入力しながらの処理となるであろう。今回は、前回のリスト操作のプログラムの確認などと合わせ、リストへのデータの追加処理について説明する。
ループによるリスト操作・再帰によるリスト操作
ループによるリスト操作のプログラム例を以下に示す。
// リストの全要素を出力
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// リストの件数を返す
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
// リストの合計を返す
int sum( struct List* p ) {
int s = 0 ;
for( ; p != NULL ; p = p->next )
s += p->data ;
return s ;
}
// リストの最大値を返す
int max( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
int m = p->data ;
for( p = p->next ; p != NULL ; p = p->next )
if ( p->data > m )
m = p->data ;
return m ;
}
}
// リストの中から指定したkeyが含まれるか探す
int find( struct List* p , int key ) {
// 要素を見つけたら 1 、見つからなかったら 0 を返す
for( ; p != NULL ; p = p->next )
if ( p->data == key )
return 1 ;
return 0 ;
}
同じプログラムを再帰呼び出しで書いた場合。
// リストの全要素を再帰処理で出力
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ;
}
}
// リストの件数を再帰処理でカウント
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ;
}
// リストの合計を再帰処理で求める
int sum( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return p->data + sum( p->next ) ;
}
// リストの最大値を再帰処理で求める
int max( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
int tm = p->data ;
int rm = max( p->next ) ;
return tm > rm ? tm : rm ; // if ( tm > rm )
} // return tm ;
} // else
// return rm ;
// リストの中から指定した値 key を再帰処理で探す
int find( struct List* p , int key ) {
if ( p == NULL )
return 0 ; // 見つからなかった
else if ( p->data == key )
return 1 ; // 見つかった
else
return find( p->next , key ) ;
}
最も単純なリスト先頭への挿入
リスト構造を使うと、必要に応じてメモリを確保しながらデータをつなげることができるので、配列のように最初に最大データ件数を想定した入れ物を最初に作って保存するような処理をしなくて済む。
struct List {
int data ;
struct List* next ;
} ;
// 保存するリストの先頭
struct List* top = NULL ;
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
// ~~~~~~~~~(A) ~~~~~~~(B)
printf( "%d " , p->data ) ;
// ~~~~~(C) ~~~~~~~(D)
printf( "¥n" ) ;
}//~~~~~~~~~~~~~~(E)
int main() {
int x ;
while( scanf( "%d" , &x ) == 1 ) {
// ~~~~~~~~~~~~~~~~~~(F)
top = cons( x , top ) ;
} // ~~~~~~~~~~~~~~~(G)
print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(H)
return 0 ; // (生成したリストの廃棄処理は省略)
}
// (1) 入力で、11 , 22 を与えるとどうなる？ - 下図参照
// (2) 練習問題(A)～(H)の型は？
// (3) 入力で、11,22 の後に 33 を与えるとどうなる？
ここで示したコードは、新しい要素を先頭に挿入していく処理となる。このため、作られたリストは、与えられた要素順とは逆順となる。この方法は、リストを管理するポインタが1つで分かりやすい。
授業では、C言語のプログラムを示しているが、C++を使うと LIST 処理もシンプルに記述できるようになっている。参考資料として、C++で同様の処理を示す。テンプレートを使ったコンテナクラスを使うと、struct List {…} といった記述は不要で、std::forward_list<int> という型を使うだけで書けてしまう。
// C++ コンテナクラスで書くと...(auto を使うには C++11 以上) #include <iostream> #include <forward_list> #include <algorithm> int main() { std::forward_list<int> top ; int x ; while( std::cin >> x ) top.push_front( x ) ; for( auto i = top.cbegin() ; i != top.cend() ; ++i ) std::cout << *i << std::endl ; return 0 ; }
要素を末尾に追加して追加順序で保存
前に示した方法は、逆順になるので、追加要素が常に末尾に追加される方法を示す。
struct List* top = NULL ;
struct List** tail = &top ;
int main() {
int x ;
while( scanf( "%d" , &x ) == 1 ) {
// ~~~~~~~~~~~~~~~~~~~~~~~(A)
*tail = cons( x , NULL ) ;
tail = &((*tail)->next) ;
}//~~~~~~~~~~~~~~~~~~~~~~~(B) 下記の解説参照
print( top ) ; // 前回示したリスト全要素表示
// ~~~~~~~~~~~~(C)
return 0 ; // (生成したリストの廃棄処理は省略)
}
// (1) 入力で 11,22 を与えるとどうなる？ - 下図参照
// (2) 練習問題(A),(C)の型は？
// (3) 11,22の後に、さらに 33 を与えるとどうなる？
この方法は、次回にデータを追加する場所(末尾の目印のNULLが入っているデータの場所)を覚える方式である。ただし、リストへのポインタのポインタを使う方法なので、少しプログラムがわかりづらいかもしれない。
理解の確認のために、末尾のポインタを動かす部分の式を、型で解説すると以下のようになる。
途中でデータ挿入・データ削除
リスト構造の特徴は、途中にデータを入れたり、途中のデータを抜くのが簡単にできる所。そのプログラムは以下のようになるだろう。
// 指定した途中の場所に要素を挿入
void insert( struct List*p , int data ) {
// p は要素を入れる前のポインタ
// data は追加する要素
// あえて、補助関数consを使わずに書いてみる
struct List* n ;
n = (struct List*)malloc( sizeof( struct List ) ) ;
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(A)
if ( n != NULL ) {
n->data = data ;
// ~~~~(B)
n->next = p->next ;
// ~~~~~~~(C)
p->next = n ;
}
// consを使って書けば、簡単
// p->next = cons( data , p->next ) ;
}
int main() {
struct List* top = cons( 11 , cons( 22 , cons( 44 , NULL ) ) ) ;
// ↑
insert( top->next , 33 ) ; // ここに33を挿入したい
return 0 ; // (生成したリストの廃棄処理は省略)
}
// 指定した場所のデータを消す
void remove_after( struct List* p ) {
struct List* del = p->next ;
p->next = del->next ;
free( del ) ;
}
int main() {
struct List* top = cons( 11 , cons( 22 , cons( 33 , cons( 44 , NULL ) ) ) ) ;
remove_after( top->next ) ; // ↑
// これを消したい
return 0 ; // リストの廃棄処理は省略)
}
理解度確認
上記プログラムinsert() の中の、下線部(A),(B),(C)の型は何か答えよ。
レポート課題
以下に示すようなデータを扱うリスト構造を作り、そのリストを扱うプログラムを作成せよ。
( 出席番号 % 3 ) の番号の課題に取り組むこと。
- 緯度(latitude)経度(longitude)とその場所の都市名(city)
- 名前(name)と誕生日(month,day)(1つの変数に2月7日を0207のように保存するのは禁止)
- 複素数(re,im)
このようなプログラムを作るのであれば、以下の例を参考に。
struct NameAgeList {
char name[ 20 ] ; // 名前
int age ; // 年齢
struct NameAgeList* next ; // 次のデータへのポインタ
} ;
struct NameAgeList* na_cons( char* nm, int ag,
struct NameAgeList*p )
{ struct NameAgeList* ans ;
ans = (struct NameAgeList*)malloc(
sizeof( struct NameAgeList ) ) ;
if ( ans != NULL ) {
strcpy( ans->name , nm ) ;
ans->age = ag ;
ans->next = p ;
}
return ans ;
}
int main() {
struct NameAgeList* top = NULL ;
struct NameAgeList* p ;
char buff[ 1024 ] ;
// 1行読み込みの繰り返し
while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
char nm[ 100 ] ;
int ag ;
// 1行の中から名前と年齢があったら na_cons で挿入保存
if ( sscanf( buff , "%s%d" , nm , &ag ) == 2 ) {
top = na_cons( nm , ag , top ) ;
}
}
// 読み込んだデータを全部出力
for( p = top ; p != NULL ; p = p->next )
printf( "%s %d¥n" , p->name , p->age ) ;
return 0 ; // リストの廃棄処理は省略)
}
リスト処理
リスト構造
リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。
まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、１つ１つのデータをポインタでつなげる処理を示す。
#include <stdio.h>
#include <stdlib.h>
// List構造の宣言
struct List {
int data ; // データ保存部
struct List* next ; // 次のデータへのポインタ
} ;
int main() {
struct List* top ; // データの先頭
struct List* p ;
// (1)
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 111 ;
// (2)
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 222 ;
// (3)
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 333 ;
top->next->next->next = NULL ; // 末尾データの目印
for( p = top ; p != NULL ; p = p->next ) {
printf( "%d¥n" , p->data ) ;
}
return 0 ;
}
このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。
NULLって何？
前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。
同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。NULLポインタの先を参照してはいけない。このリスト処理では、末尾を表す目印として使っている。
#define NULL 0
補助関数
上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。
struct List* cons( int x , struct List* n ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
int main() {
struct List* top ;
top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
:
return 0 ; // Listの開放free()は省略
}
補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP)※ というプログラム言語でのリスト(セル)を生成する関数が cons 。
typedefを使った書き方
List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。
// typedef の使い方 // typedef 型宣言 型名 ; typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい uint32 x = 12345 ; typedef struct LIST { // 構造体のタグ名と新しくつける型名と重複できない int data ; // のでこの時点のタグ名は "LIST" としておく struct LIST* next ; } List ; List* cons( int x , List* n ) { // C++なら struct List { ... } ; と書く List* ans ; // だけでこういう表記が可能 ans = (List*)malloc( sizeof( List ) ) ; : ((略)) } int main() { List* top ; top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ; : ((略)) }最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。
// 最近のC++なら... struct List { public: int data ; List* next ; public: List( int x , List* n ) : data( x ) , next( n ) {} } ; int main() { List* top = new List( 111 , new List( 222 , new List( 333 , NULL ) ) ) ; : // Listの開放deleteは省略 }LISP※と関数型プログラミング言語
LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらいに遡る。最初は、人工知能※※(AI)のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。
関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しの関数で書けばいい…。
LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。
古いAI※※と最近のAIの違い
最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。
LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというとLISPの時代のAI「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すことを目指していた。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。
しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習やディープラーニングという技法により今まで難しかった右脳の機能を実現することで、最近のAIでは左脳と右脳の機能を兼ね備えたものとなっている。
将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。
簡単なリスト処理の例
先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。
// 全要素を表示する関数
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
int main() {
struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , count( top ) ) ;
return 0 ;
}
リスト処理を自分で考えて作成
以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
// (111+444+333)/3=296.0
自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
// find( top , 444 ) = 1 (先頭0番目)
// 見つからなかったら -1
自分で考えよう
}
再帰呼び出しでリスト処理
リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか？
// 全データを表示
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ; // 末尾再帰
}
}
// データ数を返す関数
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
// find( top , 444 ) = 1
// 見つかったら1 , 見つからなかったら 0
自分で考えよう
}
理解度確認
上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。
リスト構造の導入
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造の導入の説明を行う。
配列の利点と欠点
今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。しかし、配列には苦手な処理がある。
例えば、配列の中から目的のデータを高速に探す方式として、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 ) {
// 要素を１つ後ろにずらす処理(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)の処理が発生しない)
しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。そこで、必要に応じてメモリを確保するテクニックを導入する。
様々なデータの覚え方のレポート課題
前回の 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 ) {
// 名前と年齢の２つのデータが正しく読み込めたとき
...
}
}
}
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 についてチャレンジすること。
- 名前と電話番号
- 名前と身長・体重
- 名前と生年月日
このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。
名前は、長い名前の人が混ざっているかもしれない。
保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)
ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。
レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。
考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。
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 ;
}