ホーム » 「LIFO」タグがついた投稿
タグアーカイブ: LIFO
スタックと待ち行列
前回の授業では、リストの先頭にデータを挿入する処理と、末尾に追加する処理について説明したが、この応用について説明する。
計算処理中に一時的なデータの保存として、スタック(stack)と待ち行列・キュー(queue)がよく利用される。それを配列を使って記述したり、任意の大きさにできるリストを用いて記述することを示す。
スタック
配列を用いたスタック
一時的な値の記憶によく利用されるスタック(stack)は、データの覚え方の特徴からLIFO( Last In First out )とも呼ばれる。配列を使って記述すると以下のようになるであろう。
#define STACK_SIZE 32 int stack[ STACK_SIZE ] ; int sp = 0 ; void push( int x ) { // データをスタックの一番上に積む stack[ sp++ ] = x ; } int pop() { // スタックの一番うえのデータを取り出す return stack[ --sp ] ; } void main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d\n" , pop() ) ; // 3 printf( "%d\n" , pop() ) ; // 2 printf( "%d\n" , pop() ) ; // 1 }
++,–の前置型と後置型の違い
// 後置インクリメント演算子 int i = 100 ; printf( "%d" , i++ ) ; // これは、 printf( "%d" , i ) ; i++ ; // と同じ。100が表示された後、101になる。 // 前置インクリメント演算子 int i = 100 ; printf( "%d" , ++i ) ; // これは、 i++ ; printf( "%d" , i ) ; // と同じ。101になった後、101を表示。
リスト構造を用いたスタック
しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、配列サイズの上限を気にすることなく使うことができるだろう。では、リスト構造を使ってスタックの処理を記述してみる。
struct List* stack = NULL ; void push( int x ) { // リスト先頭に挿入 stack = cons( x , stack ) ; } int pop() { // リスト先頭を取り出す int ans = stack->data ; struct List* d = stack ; stack = stack->next ; // データ 0 件で pop() した場合のエラー対策は省略 free( d ) ; return ans ; }
キュー(QUEUE)
2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー:queue)がよく利用される。 データの覚え方の特徴からFIFO(First In First Out)とも呼ばれる。
配列を用いたQUEUE / リングバッファ
配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。
#define QUEUE_SIZE 32 int queue[ QUEUE_SIZE ] ; int wp = 0 ; // write pointer(書き込み用) int rp = 0 ; // read pointer(読み出し用) void put( int x ) { // 書き込んで後ろ(次)に移動 queue[ wp++ ] = x ; if ( wp >= QUEUE_SIZE ) // 末尾なら先頭に戻る wp = 0 ; } int get() { // 読み出して後ろ(次)に移動 int ans = queue[ rp++ ] ; if ( rp >= QUEUE_SIZE ) // 末尾なら先頭に戻る rp = 0 ; return ans ; } void main() { put( 1 ) ; put( 2 ) ; put( 3 ) ; printf( "%d\n" , get() ) ; // 1 printf( "%d\n" , get() ) ; // 2 printf( "%d\n" , get() ) ; // 3 }
このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。このため、上記コードはまだエラー対策としては不十分である。どのようにすべきか?
リスト構造を用いたQUEUE
前述のリングバッファもget()しないまま、配列上限を越えてput()を続けることはできない。
この配列サイズの上限問題を解決したいのであれば、リスト構造を使って解決することもできる。この場合のプログラムは、以下のようになるだろう。
struct List* queue = NULL ; struct List** tail = &queue ; void put( int x ) { // リスト末尾に追加 *tail = cons( x , NULL ) ; tail = &( (*tail)->next ) ; } int get() { // リスト先頭から取り出す int ans = queue->data ; struct List* d = queue ; queue = queue->next ; free( d ) ; return ans ; }
ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を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言語では、配列宣言を行う時は、配列サイズに変数を使うことはできない。
最近のC(C99)では、実は下記のようなものは、裏で後述のalloca()を使って動いたりする。(^_^;
void foo( int size ) { int array[ size ] ; // エラー for( int i = 0 ; i < size ; i++ ) array[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
メモリ利用の効率
配列サイズには、定数式しか使えないので、1クラスの名前のデータを覚えるなら、以下のような宣言が一般的であろう。
#define MEMBER_SIZE 50 #define NAME_LENGTH 20 char name[ MEMBER_SIZE ][ NAME_LENGTH ] ;
しかしながら、クラスに寿限無とか銀魂の「ビチグソ丸」のような名前の人がいたら、20文字では足りない。(C言語の普通の配列宣言では、”t-saitoh”くんは配列サイズ9byte、”寿限無”くんは配列220byte といった使い方はできない) また、クラスの人数も、巨大大学の学生全員を覚えたいとい話であれば、 10000人分を用意する必要がある。 ただし、10000人の”寿限無”ありを考慮して、5Mbyte の配列を準備したのに、与えられたデータ量が100件で終わってしまうなら、その際のメモリの利用効率は極めて低い。
このため、最も簡単な方法は、以下のように巨大な文字配列に先頭から名前を入れていき、 文字ポインタ配列に、各名前の先頭の場所を入れる方式であれば、 途中に寿限無がいたとしても、問題はない。
char array[2000] = "ayuka¥0mitsuki¥0t-saitoh¥0tomoko¥0....." ; char *name[ 50 ] = { array+0 , array+6 , array+14 , array+23 , ... } ;
この方式であれば、2000byte + 4byte(32bitポインタ)×50 のメモリがあれば、 無駄なメモリ空間も必要最低限とすることができる。
参考:
寿限無(文字数:全角103文字)
さる御方、ビチグソ丸(文字数:全角210文字)
引用Wikipedia
大きな配列を少しづつ貸し出す処理
// 巨大な配列 char str[ 10000 ] ; // 使用領域の末尾(初期値は巨大配列の先頭) char* sp = str ; // 文字列を保存する関数 char* entry( char* s ) { char* ret = sp ; strcpy( sp , s ) ; sp += strlen( s ) + 1 ; return ret ; } int main() { char* names[ 10 ] ; names[ 0 ] = entry( "saitoh" ) ; names[ 1 ] = entry( "jugemu-jugemu-gokono-surikire..." ) ; return 0 ; } // str[] s a i t o h ¥0 t o m o k o ¥0 // ↑ ↑ // names[0] names[1]
このプログラムでは、貸し出す度に、sp のポインタを後ろに移動していく。
スタック
この貸し出す度に、末尾の場所をずらす方式にスタックがある。
int stack[ 100 ] ; int* sp = stack ; void push( int x ) { *sp = x ; // 1行で書くなら sp++ ; // *sp++ = x ; } int pop() { sp-- ; return *sp ; // return *(--sp) ; } int main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; printf( "%d¥n" , pop() ) ; return 0 ; }
スタックは、最後に保存したデータを最初に取り出せる(Last In First Out)から、LIFO とも呼ばれる。
このデータ管理方法は、最後に呼び出した関数が最初に終了することから、関数の戻り番地の保存や、最後に確保した局所変数が最初に不要となることから、局所変数の管理に利用されている。
alloca() 関数
局所変数と同じスタック上に、一時的にデータを保存する配列を作り、関数が終わると不要になる場合には、alloca() 関数が便利である。alloca の引数には、必要なメモリの byte 数を指定する。100個の整数データを保存するのであれば、int が 32bit の 4byte であれば 400byte を指定する。ただし、int 型は16bitコンピュータなら2byteかもしれないし、64bitコンピュータなら、8byte かもしれないので、sizeof() 演算子を使い、100 * sizeof( int ) と書くべきである。
#include <alloca.h> void foo( int size ) { int* p ; // p = (int*)alloca( sizeof( int ) * size ) ; for( int i = 0 ; i < size ; i++ ) p[ i ] = i*i ; } void main() { foo( 3 ) ; foo( 4 ) ; }
alloca() は、指定された byte 数のデータ領域の先頭ポインタを返すが、その領域を 文字を保存するために使うか、int を保存するために使うかは alloca() では解らない。alloca() の返り値は、使う用途に応じて型キャストが必要である。文字を保存するなら、(char*)alloca(…) 、 intを保存するなら (int*)alloca(…) のように使う。
ただし、関数内で alloca で確保したメモリは、その関数が終了すると、その領域は使えなくなる。このため、最後に alloca で確保したメモリが、最初に不要となる…ような使い方でしか使えない。
スタックと待ち行列
計算処理中に一時的なデータの保存として、stackとqueueがよく利用されるが、それを配列を使って記述したり、任意の大きさにできるリストを用いて記述する。
# 授業は、前回の演習時間が不十分だったので、前半講義、後半演習時間。
スタック
一時的な値の記憶によく利用されるスタックは、一般的にLIFO( Last In First out )と呼ばれる。配列を使って記述すると以下のようになるであろう。
#define STACK_SIZE 32 int stack[ STACK_SIZE ] ; int sp = 0 ; void push( int x ) { stack[ sp++ ] = x ; } int pop() { return stack[ --sp ] ; } void main() { push( 1 ) ; push( 2 ) ; push( 3 ) ; printf( "%d\n" , pop() ) ; // 3 printf( "%d\n" , pop() ) ; // 2 printf( "%d\n" , pop() ) ; // 1 }
しかし、この中にSTACK_SIZE以上のデータは貯えられない。同じ処理をリストを使って記述すれば、ヒープメモリを使い切るまで使うことができるだろう。
struct List* stack = NULL ; void push( int x ) { stack = cons( x , stack ) ; } int pop() { int ans = stack->data ; struct List* d = stack ; stack = stack->next ; free( d ) ; return ans ; }
キュー(QUEUE)
2つの処理の間でデータを受け渡す際に、その間に入って一時的にデータを蓄えるためには、待ち行列(キュー)がよく利用される。 FIFO(First In First Out)
配列にデータを入れる場所(wp)と取り出す場所のポインタ(rp)を使って蓄えれば良いが、配列サイズを超えることができないので、データを取り出したあとの場所を循環して用いるリングバッファは以下のようなコードで示される。
#define QUEUE_SIZE 32 int queue[ QUEUE_SIZE ] ; int wp = 0 ; int rp = 0 ; void put( int x ) { queue[ wp++ ] = x ; if ( wp >= QUEUE_SIZE ) wp = 0 ; } int get() { int ans = queue[ rp++ ] ; if ( rp >= QUEUE_SIZE ) rp = 0 ; return ans ; } void main() { put( 1 ) ; put( 2 ) ; put( 3 ) ; printf( "%d\n" , get() ) ; // 1 printf( "%d\n" , get() ) ; // 2 printf( "%d\n" , get() ) ; // 3 }
このようなデータ構造も、get() の実行が滞るようであれば、wp が rp に循環して追いついてしまう。
そこで、このプログラムもリストを使って記述すると以下のようになる。
struct List* queue = NULL ; struct List** tail = &queue ; void put( int x ) { *tail = cons( x , NULL ) ; tail = &( (*tail)->next ) ; } int get() { int ans = queue->data ; struct List* d = queue ; queue = queue->next ; free( d ) ; return ans ; }
ただし、上記のプログラムは、データ格納後にget()で全データを取り出してしまうと、tail ポインタが正しい位置になっていないため、おかしな状態になってしまう。
また、このプログラムでは、rp,wp の2つのポインタで管理することになるが、 2重管理を防ぐために、リストの先頭と末尾を1つのセルで管理する循環リストが使われることが多い。
理解確認
- 配列を用いたスタック・待ち行列は、どのような処理か?図などを用いて説明せよ。
- リスト構造を用いたスタック・待ち行列について、図などを用いて説明せよ。
- スタックや待ち行列を、配列でなくリスト構造を用いることで、どういう利点があるか?欠点があるか説明せよ。