ホーム » 2021 (ページ 3)
年別アーカイブ: 2021
batchとnohup
学校の CUDA サーバを自宅より使う学生より、「接続が Broken Pipeで切れるのどうすれば?」との質問があった。
原因は ssh で操作が何もない状態が続くと、セキュリティのために接続が切られるため。んで、.ssh/ssh_config でセッションの最大時間を延ばす設定あたりを説明したけど、「計算どのぐらいかかるの?」と聞くと「20時間かな…」。# さすが CUDA を使う卒研。
ssh のセッション延長の設定で20時間とかしちゃうと、ネットワークトラブルで通信が途中で切れたときに、サーバ側で「まだこの ssh 通信中だよね…」というプロセスが生き残る可能性があるので、あまり勧められる方法ではない。
こういう時には、処理を継続したままで、ログアウトするテクニックが必要。
通常は処理を起動して、ログアウトすると親プロセスにあたる sh が死ぬので、子プロセスが死んでしまう。
# このプロセスの原則があるから、Linux サーバで「訳の変わらんプロセスがあったら、『親を殺せ!!』が基本。」
プロセス確認の基本
((( 通常のプロセス全表示 ))) $ ps ax ((( 指定したコマンドのプロセス情報表示 ))) $ ps ax | grep コマンド名など ((( プロセスの起動引数を全部表示 ))) $ ps axl ((( 負荷の高い順にプロセス一覧を表示 ))) $ top ((( 指定したプロセスを停止 ))) $ kill -KILL プロセス番号
プロセスのバックグラウンド起動
((( プロセスをバックグラウンド起動 ))) $ コマンド... & # &がバックグラウンド起動の意味 ((( プロセスをバックグラウンドに変更 ))) $ コマンド... # フォアグランドでプロセスが動き出す ^Z (Ctrl-Z) # プロセスを一時停止 $ fg # 停止中のプロセスを再びフォアグラウンドで再起動 $ bg # 停止中のプロセスをバックグラウンドで再起動 $ jobs # 起動中の job を表示
上記で説明したコマンドは、login した shell の子プロセスになるため、たとえバックグラウンドで起動して「裏で動いている…プロセス」といえども、logout すると親プロセスが死ぬので、一緒に子プロセスも死んでしまう。
このため、起動するプロセスの親をシステムに代替わりしてもらって起動する nohup コマンドが使われる。
((( プロセスを No Hugup コマンドで起動 ))) $ nohup コマンド & # 出力はファイル保存される。 $ nohup コマンド > file.out & # 明示的にリダイレクトで表示保存先を指定 $ tail file.out # 保存しているファイルの末尾を表示
ただし nohup コマンドだと、プロセスが終了したかどうかわからない。こういう時は、batch コマンドが便利。ただし、batch コマンドはインストールされていない処理系が多い。(メールの設定が必要だから)
((( at パッケージのインストール ))) $ sudo apt-get install at # at(指定時間コマンド起動) # batch(バッチ処理起動) ((( batchの使い方 ))) $ batch at> コマンド at> ^D $ echo "コマンド" | batch
ただし batch は PATH が /bin/sh だけで起動するので、”python ほげ.py” とかで起動しても動かない場合あり。”/usr/bin/python ほげ.py” とかPATHを明記して起動するか、PATH=/usr/local/bin:/usr/bin:/bin なりの設定する処理を明記しないと動かない場合があるので要注意。
batch は、処理の出力結果はメールで送られてくる。結果を残すのなら、出力リダイレクトをしておく方がいい。
高専プロコン2021入賞
先日開催された、第32回秋田大会(2021). 「集え!未来創造への限りなき想い」において、電子情報工学科では、課題2作品、自由2作品、競技1チームにて応募し、6月に行われた書類審査にて、下記の3チームが本戦に参加し、2作品が入賞となりました。
- 自由部門 : 特別賞(ベスト3+企業賞:トヨタシステムズ賞)
- 「お地蔵様といっしょ -保育士のための園児見守りサポートシステム-」
- 開発,横山,加藤,北,飯島(電子情報4年),村田(指導教員)
- 課題部門 : 敢闘賞(+企業賞:さくらインターネット賞)
- 「マジメン-マジのイクメンパパになるための育児ⅤR教材アプリ-」
- 髙山,三木(電子情報4年),小松(指導教員)
- 競技部門 : 敗者復活戦にて敗退
- 小川,村中(電子情報4年),斉藤(指導教員)
2分探索木の処理とデータ追加処理
前回の授業では、当初予定に加え、この後に示すデータの追加処理の説明を行った。その代わり、簡単な2分木の演習が抜けていたので少し演習を追加。
2分木の簡単な処理
int count( struct Tree* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } int sum( struct Tree* p ) { // データ合計 if ( p == NULL ) return 0 ; else return p->data + sum( p->left ) + sum( p->right ) } int max( struct Tree* p ) { // 最大値 if ( p == NULL ) { return 0 ; // データ件数=0のとき0が最大値でいいのかなぁ? } else { while( p->right != NULL ) p = p->right ; return p->data ; } } int depth( struct Tree* p ) { // 木の深さ if ( p == NULL ) { return 0 ; } else { int d_l = depth( p->left ) ; int d_r = depth( p->right ) ; if ( d_l > d_r ) return d_l + 1 ; else return d_r + 1 ; } } int main() { struct Tree* top = ..... ; printf( "%d\n" , count( top ) ) ; // 木全体のデータ件数 printf( "%d\n" , sum( top ) ) ; // 木全体のデータ合計 printf( "%d\n" , depth( top ) ) ; // 木全体の最大段数 return 0 ; }
2分探索木にデータを追加
前回の授業では、データの木構造は、補助関数 tcons() により直接記述していた。実際のプログラムであれば、データに応じて1件づつ木に追加するプログラムが必要となる。この処理は以下のようになるだろう。
struct Tree* top = NULL ; // 2分探索木にデータを追加する処理 void entry( int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { if ( (*tail)->data == d ) // 同じデータが見つかった break ; else if ( (*tail)->data > d ) tail = &( (*tail)->left ) ; // 左の枝に進む else tail = &( (*tail)->right ) ; // 右の枝に進む } if ( (*tail) == NULL ) *tail = tcons( d , NULL , NULL ) ; } int main() { char buff[ 100 ] ; int x ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( x ) ; return 0 ; }
このプログラムでは、struct Tree** tail というポインタへのポインタ型を用いている。tail が指し示す部分をイメージするための図を以下に示す。
理解確認
- 関数entry() の14行目の if 判定を行う理由を説明せよ。
- 同じく、8行目の tail = &( (*tail)->left ) の式の各部分の型について説明せよ。
- sscanf() の返り値を 1 と比較している理由を説明せよ。
- entry() でデータを格納する処理時間のオーダを説明せよ。
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... void entry( struct Tree* top , int d ) { struct Tree** tail = &top ; while( *tail != NULL ) { : // 上記の entry() と同じとする } void main() { // 追加対象の top は局所変数 struct Tree* top = NULL ; char buff[ 100 ] ; int x ; while( fgets(buff,sizeof(buff),stdin) != NULL ) { if ( sscanf( buff , "%d" , &x ) != 1 ) break ; entry( top , x ) ; } }上記のプログラム↑は動かない。なぜ?
このヒントは、このページ末尾に示す。
演習課題
以下のようなデータを扱う2分探索木のプログラムを作成せよ。以下の箇条書き番号の中から、(出席番号 % 3+1)のデータについてプログラムを作ること。
- 名前(name)と電話番号(phone)
- 名前(name)と誕生日(year,mon,day)
- 名前(name)とメールアドレス(mail)
プログラムは以下の機能を持つこと。
- 1行1件でデータを入力し、2分木に追加できること。
- 全データを昇順(or降順)で表示できること。
- 検索条件を入力し、目的のデータを探せること。
レポートでは、(a)プログラムリスト,(b)その説明,(c)動作検証結果,(d)考察 を記載すること。考察のネタが無い人は、このページの理解確認の内容について記述しても良い。
// プログラムのおおまかな全体像の例 struct Tree { // // この部分を考えて // 以下の例は、名前と電話番号を想定 } ; struct Tree* top = NULL ; void tree_entry( char n[] , char ph[] ) { // n:名前,ph:電話番号 を追加 } void tree_print( struct Tree* p ) { // 全データを表示 } struct Tree* tree_search_by_name( char n[] ) { // n:名前でデータを探す } int main() { char name[ 20 ] , phone[ 20 ] ; char buff[ 1000 ] ; struct Tree* p ; // データを登録する処理(空行を入力するまで繰り返し) while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { if ( sscanf( buff , "%s%s" , name , phone ) != 2 ) break ; // 入力で、2つの文字列が無い場合はループを抜ける tree_entry( name , phone ) ; } // 全データの表示 tree_print( top ) ; // データをさがす while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { if ( sscanf( buff , "%s" , name ) != 1 ) break ; // 入力で、1つの文字列が無い場合はループを抜ける if ( (p = tree_search_by_name( name )) == NULL ) printf( "見つからない¥n" ) ; else printf( "%s %s¥n" , p->name , p->phone ) ; } return 0 ; }
動かないプログラムのヒント
// 前述プログラムは、データ追加先が大域変数なのがダサい。 // 局所変数で追加処理ができるように、したいけど... // ちなみに、こう書くと動く // Tree*を返すように変更 struct Tree* entry( struct Tree* top , int d ) { : // 最初の entry と同じ : return top ; } void main() { // 追加対象のポインタ struct Tree* top = NULL ; while( ... ) { : // entry() の返り値を top に代入 top = entry( top , x ) ; } }
fgets()とsscanf()による入力の解説
前述のプログラムの入力では、fgets() と sscanf() による処理を記載した。この関数の組み合わせが初見の人も多いと思うので解説。
// scanf() で苦手なこと -------------------------// // scanf() のダメな点 // (1) 何も入力しなかったら...という判定が難しい。 // (2) 間違えて、abc みたいに文字を入力したら、 // scanf()では以後の入力ができない。(入力関数に詳しければ別だけどさ) int x ; while( scanf( "%d" , &x ) == 1 ) { entry( x ) ; } // scanf() で危険なこと -------------------------// // 以下の入力プログラムに対して、10文字以上を入力すると危険。 // バッファオーバーフローが発生する。 char name[ 10 ] ; scanf( "%s" , name ) ; // 安全な入力 fgets() ---------------------------// // fgets() は、行末文字"¥n"まで配列 buff[]に読み込む。 // ただし、sizeof(buuf) 文字より長い場合は、途中まで。 char buff[ 100 ] ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { // buff を使う処理 } // 文字列からデータを抜き出す sscanf() -------------// // sscanf は、文字列の中から、データを抜き出せる。 // 入力が文字列であることを除き、scanf() と同じ。 char str[] = "123 abcde" ; int x ; char y[10] ; sscanf( str , "%d%s" , &x , y ) ; // x=123 , y="abcde" となる。 // sscanf() の返り値は、2 (2個のフィールドを抜き出せた) // ただし、Microsoft Visual Studio では、以下のように関数名を読み替えること。 // scanf( ... ) → scanf_s( ... ) // fscanf( ... ) → fscanf_s( ... ) // sscanf( ... ) → sscanf_s( ... )
理解確認
- 標準入力からの1行入力関数 gets() 関数が危険な理由を説明せよ。
深さ優先探索と幅優先探索
2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。
幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、データ件数0になる際の処理を手抜きで説明しているため、C++ の deque で記述。
深さ優先探索(deep-first search)は、スタックを使って実装可能なことを示すために、あえて再帰呼び出しを使わずに記述してみた。
#include <deque> #include <algorithm> int main() { std::deque<struct Tree*> deq ; struct Tree* p ; // 幅優先探索(FIFOを使って) deq.push_front( top ) ; while( !deq.empty() ) { // 待ち行列の最初を取り出す p = deq.front() ; deq.pop_front() ; if ( p != NULL ) { printf( "%d\n" , p->data ) ; // 待ち行列に枝葉を追加 deq.push_back( p->left ) ; deq.push_back( p->right ) ; } } // 深さ優先探索(再帰呼び出しを使わずstack/LIFOで実装) p = top ; for( ;; ) { // 分岐をpushしながら左下にまっしぐら while( p != NULL ) { deq.push_front( p ) ; p = p->left ; } if ( deq.empty() ) break ; // pushしておいた分岐点をpopして繰り返し p = deq.front() ; deq.pop_front() ; printf( "%d\n" , p->data ) ; p = p->right ; } return 0 ; }
mysqldump
単なるメモ
mysql の全データを吐き出すコマンド(要 mysql root password)
((( データベース dump ))) $ sudo mysqldump -u root -p -h localhost データベース名 テーブル名 > YYYY-MM-DD-mysql-db-tbl.sql $ sudo mysqldump -u root -p -h localhost --database データベース名 > YYYY-MM-DD-mysql-db.sql $ sudo mysqldump -u root -p -h localhost -A -n > YYYY-MM-DD-mysql.sql ((( データベース import ))) $ sudo mysql -h localhost -u root -p < YYYY-MM-DD-mysql.sql
2分探索木
配列やリスト構造のデータの中から、目的となるデータを探す場合、配列であれば2分探索法が用いられる。これにより、配列の中からデータを探す処理は、O(log N)となる。(ただし事前にデータが昇順に並んでいる必要あり)
// 2分探索法 int array[ 8 ] = { 11, 13 , 27, 38, 42, 64, 72 , 81 } ; int bin_search( int a[] , int key , int L , int R ) { // Lは、範囲の左端 // Rは、範囲の右端+1 (注意!!) while( R > L ) { int m = (L + R) / 2 ; if ( a[m] == key ) return key ; else if ( a[m] > key ) R = m ; else L = m + 1 ; } return -1 ; // 見つからなかった } void main() { printf( "%d¥n" , bin_search( array , 0 , 8 ) ) ; }
一方、リスト構造ではデータ列の真ん中のデータを取り出すには、先頭からアクセスするしかないのでO(N)の処理時間がかかり、極めて効率が悪い。リスト構造のようにデータの追加が簡単な特徴をもったまま、もっとデータを高速に探すことはできないものか?
2分探索木
ここで、データを探すための効率の良い方法として、2分探索木(2分木)がある。以下の木のデータでは、分離する部分に1つのデータと、左の枝(下図赤)と右の枝(下図青)がある。
この枝の特徴は何だろうか?この枝では、中央のデータ例えば42の左の枝には、42未満の数字の枝葉が繋がっている。同じように、右の枝には、42より大きな数字の枝葉が繋がっている。この構造であれば、64を探したいなら、42より大きい→右の枝、72より小さい→左の枝、64が見つかった…と、いう風にデータを探すことができる。
特徴としては、1回の比較毎にデータ件数は、(N-1)/2件に減っていく。よって、この方法であれば、O(log N)での検索が可能となる。これを2分探索木とよぶ。
このデータ構造をプログラムで書いてみよう。
struct Tree { struct Tree* left ; int data ; struct Tree* right ; } ; // 2分木を作る補助関数 struct Tree* tcons( struct Tree* L , int d , struct Tree* R ) { struct Tree* n = (struct Tree*)malloc( sizeof( struct Tree ) ) ; if ( n != NULL ) { /* (A) */ n->left = L ; n->data = d ; n->right = R ; } return n ; } // 2分探索木よりデータを探す int tree_search( struct List* p , int key ) { while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; // 見つからなかった } struct Tree* top = NULL ; void main() { // 木構造をtcons()を使って直接生成 (B) top = tcons( tcons( tcons( NULL , 13 , NULL ) , 27 , tcons( NULL , 38 , NULL ) ) , 42 , tcons( tcons( NULL , 64 , NULL ) , 72 , tcons( NULL , 81 , NULL ) ) ) ; printf( "%d¥n" , tree_search( top , 64 ) ) ; }
この方式の注目すべき点は、struct Tree {…} で宣言しているデータ構造は、2つのポインタと1つのデータを持つという点では、双方向リストとまるっきり同じである。データ構造の特徴の使い方が違うだけである。
理解度確認
- 上記プログラム中の、補助関数tcons() の(A)の部分 “if ( n != NULL )…” の判定が必要な理由を答えよ。
- 同じくmain() の (B) の部分 “top = tcons(…)” において、末端部に NULL を入れる理由を答えよ。
2分木に対する処理
2分探索木に対する簡単な処理を記述してみよう。
// データを探す int search( struct Tree* p , int key ) { // 見つかったらその値、見つからないと-1 while( p != NULL ) { if ( p->data == key ) return key ; else if ( p->data > key ) p = p->left ; else p = p->right ; } return -1 ; } // データを全表示 void print( struct Tree* p ) { if ( p != NULL ) { print( p->left ) ; printf( "%d¥n" , p->data ) ; print( p->right ) ; } } // データ件数を求める int count( struct Tree* p ) { if ( p == NULL ) return 0 ; else return 1 + count( p->left ) + count( p->right ) ; } // データの合計を求める int sum( struct Tree* p ) { if ( p == NULL ) return 0 ; else return p->data + count( p->left ) + count( p->right ) ; } // データの最大値 int max( struct Tree* p ) { while( p->right != NULL ) p = p->right ; return p->data ; }
これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。
(2021/10/12)
print() の再帰の処理の流れを説明するなかで、「じゃあデータを降順で表示したかったらどうすればいい?」「じゃあ、データが根っこに近い方から表示したかったらどうすればいい?」みたいな話を、高専プロコンの競技部門の組み合わせ問題に考えてほしくなって、つぶやいちゃったもんだから、話がそれて「再帰で記載するのは、枝の先の処理が終わってから、残りの枝の処理を行うので、深さ優先探索法になる。」、「根っこに近い方から表示したかったら幅優先探索法」になるよ…という話をする。ついでの雑談で、「将棋とかチェスのプログラムだと、次の手を打った後の評価で先読みするけど、あれどうやってる?」という話をして、その中でαβ法というのがあってね…静的評価で良い手の候補を選び、その手は動的評価で再帰処理を行い、本当に良い手を選ぶ…という説明を行った。来週は、2分木の sum() とか count() を考えてもらうことから始めよう。
データベースの用語など
データベースの機能
データベースを考える時、利用者の視点で分類すると、以下の3つの視点の違いがある。
- データベースの管理者(データベース全体の管理)、
- 応用プログラマ(SQLなどを使って目的のアプリケーションに合わせた処理を行う)、
- エンドユーザ(データベース処理の専門家でなく、DBシステムのGUIを使ってデータベースを操作する)
データベース管理システム(DBMS)では、データとプログラムを分離してプログラムを書けるように、データ操作言語(SQL)で記述する。
また、データは独立して扱えるようにすることで、データへの物理的なアクセス方法があっても、プログラムの変更が不要となるようにする。
データベースは、利用者から頻繁に不定期にアクセスされる。このため、データの一貫性が重要となる。これらを満たすためには、(a) データの正当性の確認、(b) 同時実行制御(排他制御)、(c) 障害回復の機能が重要となる。
これ以外にも、データベースからデータを高速に扱えるためには、検索キーに応じてインデックスファイルを管理してくれる機能や、データベースをネットワーク越しに使える機能などが求められる。
データベースに対する視点
実体のデータをそれぞれの利用者からデータベースを記述したものはスキーマと呼ばれる。そのスキーマも3つに分けられ、これを3層スキーマアーキテクチャと呼ぶ。
- 外部スキーマ – エンドユーザからどんなデータに見えるのか
- 概念スキーマ – 応用プログラマからは、どのような表の組み合わせで見えるのか、表の中身はどのようなものなのか。
- 内部スキーマ – データベース管理者からみて、表の中身は、どのようなファイル名でどのような形式でどう保存されているのか
データモデル
データを表現するモデルには、いくつかのモデルがある。
- 階層型データモデル – 木構造で枝葉に行くにつれて細かい内容
- ユーザ情報を扱うLDAP(Light Weight Directory Access Protocol)は、階層モデルの例
- ディレクトリサービス: コンピュータのリソースの属性や情報のデータベース
- ネットワーク型モデル – データの一部が他のデータ構造と関係している。
- 関係モデル – すべてを表形式で表す。
データベースの基礎
データベースは、1970年頃に、E.F.コッド博士によりデータベースのための数学的な理論が確立された。
- 集合 A, B – 様々なデータ
- 直積 A✕B = { (x,y) | x∈A , y∈B } 集合A,Bのすべての組み合わせ
- 関係 R(A,B) すべての組み合わせのうち、関係があるもの。直積A,Bの部分集合
例えば、A={ s,t,u } , B={ p,q } (定義域) なら、
A✕B = { (s,p) , (s,q) , (t,p) , (t,q) , (u,p) , (u,q) }
このうち、Aが名前(sさん,tさん,uさん)、Bが性別(p=男性,q=女性)を表すなら、
R(A,B) = { (s,p) , (t,q) , (u,p) } (例)
(例):(sさん,男性) , (tさん,女性) , (uさん,男性)
理解確認
- データベースにおける3層スキーマアーキテクチャについて説明せよ
- 集合A,Bが与えられた時、関係R(A,B) はどのようなものか、数学定義や実例をあげて説明せよ。
双方向リスト
最初に、前期期末試験で「メモリの番地の理解が怪しい」人が多かったので、その確認のための Forms による小テストを行う。
実施してみらた、各問題とも50%程度の正解率。ひとまず解説をしたうえで、同じような問題を今後も何度かやってみたいと思う。
リスト構造の利点と欠点
リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。
例えば、整数型のデータを最大 MAX 件保存したいけど、実際は それ以下の、平均 N 件扱うとする。この時のメモリの使用量 M は、以下のようになるであろう。
配列の場合 | リスト構造の場合 |
(ただしヒープ管理用メモリ使用量は無視) |
シーケンシャルアクセス・ランダムアクセス
もう1つの欠点がシーケンシャルアクセスとなる。テープ上に記録された情報を読む場合、後ろのデータを読むには途中データを読み飛ばす必要があり、データ件数に比例したアクセス時間を要する。このような N番目 データ参照に、O(N)の時間を要するものは、シーケンシャルアクセスと呼ばれる。
一方、配列はどの場所であれ、一定時間でデータの参照が可能であり、これは ランダムアクセスと呼ばれる。N番目のアクセス時間がO(1)を要する。
このため、プログラム・エディタの文字データの管理などに単純リストを用いた場合、1つ前の行に移動するには、先頭から編集行までの移動で O(N) の時間がかかり、大量の行数の編集では、使いものにならない。ここで、シーケンシャルアクセスでも1つ前にもどるだけでも処理時間を改善してみよう。
単純リストから双方向リストへ
ここまで説明してきた単純リストは、次のデータへのポインタを持つ。ここで、1つ後ろのデータ(N番目からN+1番目)をアクセスするのは簡単だけど、1つ前のデータ(N-1番目)を参照しようと思ったら、先頭から(N-1)番目を辿るしかない。でも、これは O(N) の処理であり時間がかかる処理。
ではどうすればよいのか?
この場合、一つ前のデータの場所を覚えているポインタがあれば良い。
// 双方向リストの宣言 struct BD_List { struct BD_List* prev ; // 1つ前のデータへのポインタ int data ; struct BD_List* next ; // 次のデータへのポインタ } ;
このデータ構造は、双方向リスト(bi-directional list)と呼ばれる。では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。
// リスト生成補助関数 struct BD_List* bd_cons( struct BD_List* p , int d , struct BD_List* n ) { struct BD_List* ans ; ans = (struct BD_List*)malloc( sizeof( struct BD_List ) ) ; if ( ans != NULL ) { ans->prev = p ; ans->data = d ; ans->next = n ; } return ans ; } void main() { struct BD_List* top ; struct BD_List* p ; // 順方向のポインタでリストを生成 top = bd_cons( NULL , 1 , bd_cons( NULL , 2 , bd_cons( NULL , 3 , NULL ) ) ) ; // 逆方向のポインタを埋める top->next->prev = top ; top->next->next->prev = top->next ; // リストを辿る処理 for( p = top ; p->next != NULL ; p = p->next ) printf( "%d\n" , p->data ) ; for( ; p->prev != NULL ; p = p->prev ) printf( "%d\n" , p->data ) ; }
双方向リストの関数作成
以上の説明で、双方向の基礎的なプログラムの意味が分かった所で、練習問題。
先のプログラムでは、1,2,3 を要素とするリストを、ナマで記述していた。実際には、どんなデータがくるか分からないし、指定したポインタ p の後ろに、データを1件挿入する処理 bd_insert( p , 値 ) , また、p の後ろのデータを消す処理 bd_delete( p ) を書いてみよう。
// 双方向リストの指定場所 p の後ろに、値 d を要素とするデータを挿入せよ。 void bd_insert( struct BD_List* p , int d ) { struct BD_List*n = bd_cons( p , d , p->next ) ; if ( n != NULL ) { p->next->prev = n ; p->next = n ; } } // 双方向リストの指定場所 p の後ろのデータを消す処理は? void bd_delete( struct BD_List* p ) { struct BD_List* d = p->next ; d->next->prev = p ; p->next = d->next ; free( d ) ; } // この手のリスト処理のプログラムでは、命令の順序が重要となる。 // コツとしては、修正したい箇所の遠くの部分を操作する処理から // 書いていくと間違いが少ない。
番兵と双方向循環リスト
前述の bd_insert() だが、データの先頭にデータを挿入したい場合は、どう呼び出せば良いだろうか?
bd_insert() で、末尾にデータを挿入する処理は、正しく動くだろうか?
同じく、bd_delete() だが、データの先頭のデータを消したい場合は、どう呼び出せば良いだろうか?
また、データを消す場合、最後の1件のデータが消えて、データが0件になる場合、bd_delete() は正しく動くだろうか?
こういった問題が発生した場合、データが先頭・末尾で思ったように動かない時、0件になる場合に動かない時、特別処理でプログラムを書くことは、プログラムを読みづらくしてしまう。そこで、一般的には 循環リストの時にも紹介したが、番兵(Sentinel) を置くことが多い。
しかし、先頭用の番兵、末尾用の番兵を2つ用意するぐらいなら、循環リストにした方が便利となる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。
deque(両端キュー)
この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。
理解確認
- 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
- 双方向リストの利点と欠点はなにか?
- 番兵を用いる利点を説明せよ。
- deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
- 双方向リストが使われる処理の例としてどのようなものがあるか?