ホーム » 2022 » 10月

月別アーカイブ: 10月 2022

2022年10月
 1
2345678
9101112131415
16171819202122
23242526272829
3031  

検索・リンク

集約関数と副問い合わせ

特殊な条件演算子

WHERE 節の中で使える特殊な条件演算子を紹介する。

... AND ...
   WHERE S.業者番号 <= 100 AND S.業者番号 >= 200 ;
... OR ...
   WHERE S.業者番号 >= 100 OR S.業者番号 <= 200 ;
NOT ...
   WHERE NOT S.業者番号 >= 100 ;
... IN ...
   WHERE S.業者番号 IN ( 'S1' , 'S4' ) ;
... BETWEEN A AND B 
   WHERE S.優良度 BETWEEN 50 AND 100 ;
... LIKE ...
   WHERE S.業者名 LIKE 'A_C社' ;   _ は任意の1文字 ABC社 ADC社
   WHERE S.業者名 LIKE 'A%社' ;    % は任意の0~N文字 A社, AA社 ABC社
... IS NULL
   WHERE S.業者名 IS NULL
   WHERE S.業者名 IS NOT NULL

集約関数

集約関数は、SQL の SELECT の射影部分で使える関数で、出力対象となった項目に対して、COUNT(),SUM(),AVG()といった計算を行うもの。

COUNT() - 項目の数
SUM() -   項目の合計
AVG() -   項目の平均
MAX() -   項目の最大値
MIN() -   項目の最低値

SELECT COUNT(S.業者番号) FROM S WHERE S.優良度 > 20 ;

集合計算

複数の SQL の結果に対し、集合和, 集合積, 集合差などの処理を行う。

... UNION ...  集合和
... EXPECT ... 集合差
... INTERSECT ... 集合積

SELECT S.業者名 FROM S WHERE S.所在 = '福井'
UNION
SELECT S.業者名 FROM S WHERE S.所在 = '東京'

SQLの副問い合せ

前節の結合処理は時として効率が悪い。このような場合は、副問い合わせを用いる場合も多い。

SELECT S.業者名, S.所在
  FROM S
  WHERE S.業者番号 IN
     ( SELECT SG.業者番号
         FROM SG
         WHERE SG.商品番号 = 'G2'
           AND SG.在庫量 >= 200 ) ;

まず、『◯ IN { … }』 の比較演算子は、◯が{…}の中に含まれていれば真となる。また、SQLの中の (…) の中が副問い合わせである。

この SQL では、副問い合わせの内部には、テーブル S に関係する要素が含まれない。この場合、副問い合わせ(商品番号がG2で在庫量が200以上)は先に実行される。

{(S1,G2,200),(S2,G2,400),(S3,G2,200),(S4,G2,200)}が該当し、その業者番号の{S1,S2,S3,S4}が副問い合わせの結果となる。最終的に SELECT … FROM S WHERE S.業者番号 IN {‘S1′,’S2′,’S3′,’S4’} を実行する。

相関副問い合わせ

SELECT G.商品名, G.色, G.価格
  FROM G
  WHERE 'S4' IN 
     ( SELECT SG.業者番号
         FROM SG
         WHERE SG.商品番号 = G.商品番号 ) ;

この副問い合わせでは、内部に G.商品番号 が含まれており、単純に()内を先に実行することはできない。こういった副問い合わせは、相関副問い合わせと呼ばれる。

処理は、Gのそれぞれの要素毎に、副問い合わせを実行し、その結果を使って WHERE節の判定を行う。WHERE節の選択で残った結果について、射影で商品名,色,価格が抽出される。

// 概念の説明用に、C言語風とSQL風を混在して記載する
for( int i = 0 ; i < sizeofarray( G ) ; i++ ) {
   SELECT SG.業者番号 FROM SG
    WHERE SG.商品番号 = G[i].商品番号 を実行
   if ( WHERE 'S4' IN 副query の結果が真なら ) {
      printf( ... ) ;
   }
}
// 全てのG 副queryの結果     WHERE 射影
// G1 ->  {S1,S2}
// G2 ->  {S1,S2,S3,S4} -> ◯ -> (ノート,青,170)
// G3 ->  {S1}
// G4 ->  {S1,S4}       -> ◯ -> (消しゴム,白,50)
// G5 ->  {S1,S4}       -> ◯ -> (筆箱,青,300)
// G6 ->  {S1}

演習課題

SQLの実験環境を使って、自分で考えたSQLの命令を2つ実行すること。実行した命令とその意味を説明し、出力された結果と一致することを確認すること。

さらにこの実行と同じ結果が出力される様なC言語のプログラムを作成し、おなじく結果を確認すること。

考察として、SQLで書いたプログラムとCで書いたプログラムの違いや便利な点や、Cでのプログラムの速度を早めるにはどう書くと良いかを比較検討すること。

2分探索木の処理とデータ追加処理

前回の授業で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)のデータについてプログラムを作ること。

  1. 名前(name)と電話番号(phone)
  2. 名前(name)と誕生日(year,mon,day)
  3. 名前(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( ... )

理解確認

授業アンケート前期科目

情報メディア工学

今年度、初めて開講した情報メディア工学だが、斉藤担当の前半についてアンケートの結果がでた。情報セキュリティの話を演習中心に講義を行い、レポートやFormsによる小テストにて評価を行ったが、課題などの提出が怪しい学生以外は好成績であった。学生からの評価も81.6ポイントとまずまずの評価であった。

情報制御基礎(学際)

学際科目の情報制御基礎については、複数の学科の学生の参加で、講義内容も色々と制限もあるが、基礎的な課題でのレポート点と期末テストで評価を行う中、期末テストでは評価が低い学生でも、きちんとレポート課題を提出している学生については合格点を出すことができた。

授業アンケートの評価でも 85.9 ポイントと高い評価が得られた。講義資料や過去試験問題などのWeb公開などについては、今後も続けていきたい。

SQLの基本

先週の、関係データベースの導入説明を終えて、実際のSQLの説明。

SQLの命令

SQL で使われる命令は、以下のものに分類される。((参考資料))

  • データ定義言語 – CREATE, DROP, ALTER 等
  • データ操作言語 – INSERT, UPDATE, DELETE, SELECT 等
  • データ制御言語 – GRANT, REVOKE 等 (その他トランザクション制御命令など)

create user

データベースを扱う際の create user 文は、DDL(Data Definition Language)で行う。

CREATE USER ユーザ名
    IDENTIFIED BY "パスワード"

grant

テーブルに対する権限を与える命令。

GRANT システム権限 TO ユーザ名
   データベースシステム全体に関わる権限をユーザに与える。
   (例) GRANT execute ON admin.my_package TO saitoh
GRANT オブジェクト権限 ON オブジェクト名 TO ユーザ名
   作られたテーブルなどのオブジェクトに関する権限を与える。
   (例) GRANT select,update,delete,insert ON admin.my_table TO saitoh
REVOKE オブジェクト権限 ON オブジェクト名 TO ユーザ名
   オブジェクトへの権限を剥奪する。

ただし、後に示す実験環境では、データベースのシステムにSQLiteを用いている。SQLite はネットワーク対応型のデータベースではないため、データベースをアクセスするユーザや権限の概念が存在しない。

create table

実際にテーブルを宣言する命令。構造体の宣言みたいなものと捉えると分かりやすい。

CREATE TABLE テーブル名
   ( 要素名1  型 , 要素名2 型 ... ) ;
   PRIMARY KEY 制約
   1つの属性でのキーの場合、型の後ろに"PRIMARY KEY"をつける、
   複数属性でキーとなる場合は、要素列の最後に PRIMARY KEY(要素名,...) をつける。
   これによりKEYに指定した物は、重複した値を格納できない。

型には、以下の様なものがある。(Oracle)
   CHAR( size)  : 固定長文字列 / NCHAR国際文字
   VARCHAR2( size ) : 可変長文字列 / NVARCHAR2...
   NUMBER(桁) :指定 桁数を扱える数
   BINARY_FLOAT / BINARY_DOUBLE : 浮動小数点(float / double)
   DATE : 日付(年月日時分秒)
   SQLiteでの型
   INTEGER : int型
   REAL : float/double型
   TEXT : 可変長文字列型
   BLOB : 大きいバイナリデータ

DROP TABLE テーブル名
   テーブルを削除する命令

insert,update,delete

指定したテーブルに新しいデータを登録,更新,削除する命令

INSERT INTO テーブル名 ( 要素名,... ) VALUES ( 値,... ) ;
   要素に対応する値をそれぞれ代入する。
UPDATE テーブル名 SET 要素名=値 WHERE 条件
   指定した条件の列の値を更新する。
DELETE FROM テーブル名 WHERE 条件
   指定した条件の列を削除する。

select

データ問い合わせは、select文を用いる、 select文は、(1)必要なカラムを指定する射影、(2)指定条件にあうレコードを指定する選択、 (3)複数のテーブルの直積を処理する結合から構成される。

SELECT 射影 FROM 結合 WHERE 選択
   (例) SELECT S.業者番号 FROM S WHERE S.優良度 > 30 ;

理解確認

  • キー・プライマリキー・外部キーについて説明せよ。
  • 上記説明中の、科目テーブルにふさわしい create table 文を示せ。
  • select文における、射影,結合,選択について説明せよ。

SQLの演習環境の使い方

SQL の演習は、Paiza.IO もしくは 下記の 学内向け SQL 演習環境で動作確認をしてください。

下記URLにアクセスすると、認証画面が表示されるので、情報処理センターのユーザIDとパスワードで、Login する。

以下のような画面が表示されるので、最初に”データベースリセット”を押すこと。

以降、登録済みの処理を実行する場合は、左上のプルダウンメニューから、処理を選んで”バッチ処理実行”を行う。
画面下に、実行された結果が表示される。

教科書内の基本演習のデータを利用したい場合は、”0_Create_DB” , “1_Insert_Data”を実行する。

自分で処理を実行したい場合には、中段のSQLコマンドの欄に、命令を記載する。”create table”や”insert”といった結果を伴わない命令の場合は、”EXEC”を実行。”select” などの実行結果がある場合は、”QUERY”を実行すること。


SQLの基礎

ここまで述べたようにデータベースでは記録されているデータの読み書きは、SQL で行われ、射影・結合・選択を表す処理で構成されることを示した。SQL の機能を理解するために、同じ処理を C 言語で書いたらどうなるのかを示す。

((( 元のSQL )))
SELECT S.業者番号         -- 必要とされるデータを抽出する射影 --
  FROM S                 -- 複数のテーブルを組合せる結合 --
  WHERE S.優良度 >= 20 ;  -- 対象となるデータを選び出す選択 --

((( SQLをC言語で書いたら )))
// 配列の個数を求める #define 文
#define sizeofarray(ARY) (sizeof(ARY) / sizeof(ARY[0]))
// C言語なら... S のデータを構造体宣言で書いてみる。
struct Table_S {
   char 業者番号[ 6 ] ; // 当然、C言語では要素名を
   char 業者名[ 22 ] ;  // 漢字で宣言はできない。
   int  優良度 ;
   char 所在[ 16 ] ;
} S[] = {
   { "S1" , "ABC社" , 20 , "福井" } ,
   :
} ;

// SELECT...をC言語で書いた場合の命令のイメージ
// 結合
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // 選択
   if ( S[i].優良度 >= 20 )
      // 射影
      printf( "%d¥n" , S[i].業者番号 ) ;
}

Sは、テーブル名であり、文脈上対象テーブルが明らかな場合、フィールド名の前の テーブルは省略可能である。

SELECT 業者番号 FROM S WHERE 優良度 >= 20 ;

WHERE 節で記述できる条件式では、= , <>(not equal) , < , > , <= , >= の比較演算子が使える。
# これ以外の演算機能は、次週にて紹介予定。

直積と結合処理

ここで、SQLの最も便利な機能は、直積による結合処理。複数の表を組み合わせる処理。単純な表形式の関係データベースで、複雑なデータを表現できる基本機能となっている。

SELECT SG.商品番号 , S.所在
  FROM S , SG
  WHERE SG.業者番号 = S.業者番号

上記の様に FROM 節に複数のテーブルを書くと、それぞれのテーブルの直積(要素の全ての組み合わせ)を生成する処理が行われる。この機能が結合となる。しかし、これだけでは意味がないので、通常は外部キーが一致するレコードでのみ処理を行うように、WHERE SG.業者番号 = S.業者番号 のような選択を記載する。最後に、結果として欲しいデータを抽出する射影を記載する。

SELECTの結合処理と処理内容

selectでの選択,結合,射影の処理(select 射影 from 結合 where 選択)を理解するために、同じ処理をC言語で書いたらどうなるかを示す。

// C言語なら
struct Table_S {
   char 業者番号[ 6 ] ;
   char 業者名[ 22 ] ;
   int  優良度 ;
   char 所在[ 16 ] ;
} S[] = {
   { "S1" , "ABC社" , 20 , "福井" } ,
   :
} ;
struct Table_SG {
   char 業者番号[ 6 ] ;
   char 商品番号[ 6 ] ;
   int  在庫量 ;
} = SG[] {
   { "S1" , "G1" , 300 } ,
   :
} ;

// FROM S
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // FROM SG
   for( int j = 0 ; j < sizeofarray( SG ) ; j++ ) {
      // WHERE S.業者番号 = SG.業者番号
      if ( strcmp( S[i].業者番号 , SG[j].業者番号 ) == 0 ) {
         // SELECT SG.商品番号 , S.所在
         printf( "%s %s¥n" , SG[j].商品番号 , S[i].所在 ) ;
      }
   }
}

(1) i,jの2重forループが、FROM節の結合に相当し、(2) ループ内のif文がWHERE節の選択に相当し、(3) printfの表示内容が射影に相当している。

射影の処理では、データの一部分を抽出することから、1件の抽出レコードが同じになることもある。この際の重複したデータを1つにまとめる場合には、DISTINCT を指定する。

SELECT DISTINCT SG.商品番号, S.所在
   FROM S, SG
   WHERE SG.業者番号 = S.業者番号 ;

上記のプログラムでは、データの検索は単純 for ループで記載しているが、内部で HASH などが使われていると、昇順に処理が行われない場合も多い。出力されるデータの順序を指定したい場合には、ORDER BY … ASC (or DESC) を用いる

SELECT SG.商品番号, S.所在
   FROM S, SG
   WHERE SG.業者番号 = S.業者番号
   ORDER BY S.所在 ASC ;        -- ASC:昇順 , DESC:降順 --

表型のデータと串刺し

FROM に記載する直積のための結合では、2つ以上のテーブルを指定しても良い。

SELECT S.業者名, G.商品名, SG.在庫量
   FROM S, G, SG
   WHERE  S.業者番号 = SG.業者番号  -- 外部キー業者番号の対応付け --
     AND  SG.商品番号 = G.商品番号  -- 外部キー商品番号の対応付け --

// 上記の処理をC言語で書いたら

struct Table_G {
   char 商品番号[ 6 ] ;
   char 商品名[ 22 ] ;
   char 色[ 4 ] ;
   int  価格 ;
   char 所在[ 12 ] ;
} = G[] = {
   { "G1" , "赤鉛筆" , "青" , 120 , "福井" } ,
   :
} ;

// [結合] S,G,SGのすべての組み合わせ
// FROM S -- 結合
for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
   // FROM G -- 結合
   for( int j = 0 ; j < sizeofarray( G ) ; j++ ) {
      // FROM SG -- 結合
      for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) {

         // [選択] 条件でレコードを選び出す
         //   WHERE S.業者番号 = SG.業者番号
         //     AND SG.商品番号 = G.商品番号
         if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0
           && strcmp( SG[k].商品番号 , G[j].商品番号 ) == 0 ) {
            // [射影] 使用するフィールドを出力
            printf( "%s %s %d\n" ,
                    S[i].業者名 , G[j].商品名 , SG[k].在庫量 ) ;
         }
      }
   }
}

ここで結合と選択で実行している内容は、外部キーである業者番号を S から探す、商品番号を G から探している。この、外部キー対応しているものを探すという視点で、上記 C 言語のプログラムを書き換えると、以下のように表せる。

// FROM SG
for( int k = 0 ; k < sizeofarray( SG ) ; k++ ) {
   // 外部キー SG.業者番号に対応するものを S から探す
   for( int i = 0 ; i < sizeofarray( S ) ; i++ ) {
      if ( strcmp( S[i].業者番号 , SG[k].業者番号 ) == 0 ) {
         // 外部キー SG.商品番号に対応するものを G から探す
         for( int j = 0 ; j < sizeofarray( G ) ; j++ ) {
            if ( strcmp(SG[k].商品番号,G[j].商品番号) == 0 ) {
               printf( "%s %s %d\n" ,
                       S[i].業者名,G[j].商品名,SG[k].在庫量 ) ;
            }
         }
      }
   }
}

このような、複数の表の実体と関係を対応付けた検索を、データベースの専門の人は「データを串刺しにする」という言い方をすることも多い。

また、SQL では、このようなイメージの繰り返し処理を、数行で分かりやすく記述できている。このプログラム例では、キーに対応するものを単純 for ループで説明しているが、SQL ではプライマリキーなら、B木やハッシュなどを用いた効率の良い検索が自動的に行われる。このため、SQLを扱う応用プログラマは、SQLの結合の処理方法は通常はあまり考えなくて良い。

4EI インターンシップ報告会

今日10/24に、夏休みに実施された 4年学生のインターンシップの報告会が 行われました。
4年電子情報の学生さんは、高専プロコンに参加して忙しかった人も 多かったようですが、貴重な体験ができ、来年の就職活動の 参考になったと思います。
個人的には、質疑応答時間も短いことから、Teams に質問を 全4EI学生にしてみました。質問の返答を見ていると、問題意識を もってインターンに臨んでいたのか判りますね。

ネットワーク層とIPアドレス

前回説明したMACアドレスによるデータリンク層では、1つのサブネットの中で指定した相手にデータを送ることはできる。しかし、データリンク層だけでは、他のサブネットにいる相手にデータを送ることができない。(相手の名前を知っていても、住所を知らなければ郵便は送れない。)

ネットワーク層とIPアドレス(IPv4)

サブネットに分割し、隣接するサブネット、さらには上流のインターネットと通信をするためには、IPアドレスを用いた通信が行われる。

ネットワークに接続する機器には、それぞれユニークな32bitの番号(IPv4アドレス)を割り振る。

コンピュータへのIPアドレスの設定には、(a)IPアドレス,(b)サブネットマスク,(c)ゲートウェイの情報が必要となる。

  • IPアドレス: 192.156.145.100 といった、0~255の8bitの値をピリオド区切りで4つ並べて表記するのが一般的。
  • サブネットマスク: 255.255.255.0 といった値で、IPアドレスを2進数で書き並べた32bitと、サブネットマスクの32bitで、2進数の論理積をとった値は、ネットワーク番号と呼ばれ、機器が存在する場所を表す。
    また、IPアドレスとサブネットマスクの否定と論理積をとった値は、ホスト番号と呼ばれる。
    サブネットマスクは、先行する1のbit数で書き表すことも多い。255.255.255.0は、”/24″のように書く。
  • ゲートウェイ: 自分自身のネットワーク番号と通信相手のネットワーク番号が異なる場合は、異なるサブネットにいるので、パケットを中継してもらう機器(ルータ,ゲートウェイ)にパケットを送る。

  • IPアドレスとクラス: IPアドレスは、先頭8bit をネットワーク番号とするクラスA,16bitのクラスB,24bitのクラスCに分類されている。以前は、IPアドレスを割り当てる企業規模に応じて、大規模な大学だからクラスA、中規模ならクラスB(福井大学は133.7.0.0/16 ←このような書き方はCIDR記法という)、小規模ならクラスCを割り当てていた。(福井高専はCクラスを5本192.156.145~149.0/24 : 福井高専のIPアドレスでは3つのCIDR記法で表現できる。 192.156.145.0/24, 192.156.146.0/23, 192.156.148.0/23)
    しかし、最近では IPv4 アドレスの不足から、大きな組織に割り振られた クラスA を再分配している。

ARP(IPアドレスとMACアドレスの橋渡し)

同じサブネットの中では、データリンク層でMACアドレスを用いて通信相手を指定するが、ネットワーク層ではIPアドレスを用いて通信相手を指定する。この違いを埋めるためのプロトコルがARPである。

サブネット内に相手先IPアドレスの指定されたパケット(10.10.22.102)が届くと、通信機器はサブネット内の全ての機器相手に ARPリクエストを送信する。(10.10.22.102はいますか?)

この時、10.10.22.102 のコンピュータは、自分宛てのパケットがあることを知るので、送信元のコンピュータに、自分のMACアドレスを付けたARPリプライを送り返す。(10.10.22.102は、私 “FE:DC:BA:98:76:54” です!)。送信元は、ARP通信をへらすために、その情報を記憶して、2度目以降は覚えたMACアドレスですぐに通信を始める。

ルータとRIP

ルータは、隣接するサブネットの間に入る機器で、各サブネットにゲートウェイとなるインタフェースを持つ。ルータでは受け取ったパケットをどこに流すか…という経路情報が重要となる。

  • 静的ルーティング – 末端のルータの設定で、管理者が経路を設定
  • 動的ルーティング – 上流ルータでRIPにより設定

経路設定には2種類あり、(a)末端のルータではこのネットワーク番号はどのルータに送るという情報をルータに直接設定する静的ルーティングがとられる。(b)上流のルータでは、末端のルータの設定が変更されることがあるので、ルータ同士がルーティング情報を送りあう動的ルーティングがとられる。動的ルーティングでは、RIPというプロトコルにより、各サブネットのつながっている経路情報が送られてくる。この経路情報を見て、パケットのIPアドレスを見て、パケットの送り先を判断する。

((Windows の場合))

C:> ipconfig /all
インタフェース名:
 IPv4アドレス............192.168.xx.xx
 サブネットマスク.........255.255.255.0
 デフォルトゲートウェイ....192.168.xx.1
C:> arp -a
インタフェース:
 192.168.xx.xx     74-03-xx-xx-xx-xx 動的
 192.168.xx.yy     B0-05-xx-xx-xx-xx 動的
C:> netstat -r
ネットワーク宛先 ネットマスク ゲートウェイ インタフェース メトリック
      0.0.0.0        0.0.0.0   192.168.xx.1  192.168.xx.xx 45
 192.168.xx.0  255.255.255.0   ....

((Unix の場合))

$ ifconfig -a
en1: ....
     inet 192.168.xx.xx netmask 0xffffff00 ...
$ arp -an
.... (192.168.xx.xx) at 74:03:xx:xx:xx:xx ...
.... (192.168.xx.yy) at b0:05:xx:xx:xx:xx ...
$ netstat -rn
Destination  Gateway ...
default      192.168.xx.1  ...
192.168.xx   ...

プライベートアドレス

IPv4 では、32bit でコンピュータを識別することから、最大でも 232台≒40億台しか識別できない。実際、IPアドレスの管理団体では、2017年度には IPv4 アドレスは使い切った状態となっている。この対応として、その組織やその家庭内だけで使われる IPアドレス である、プライベートアドレスが用いられる。

  • 10.0.0.0~10.255.255.255 / 8 – 大きな機関向け
  • 172.16.0.0~172.31.255.255 / 12
  • 192.168.0.0~192.168.255.255 /16 – 個人向け

プライベートアドレスを利用する組織では、インターネットに接続するルータでは NAT(もしくはNAPT) という機能を内蔵し、プライベートアドレスとグローバルアドレスの変換を行う。

IPv6アドレス

IPv4の32bit の IP アドレスでは、40億台のコンピュータを区別することしかできない。そこで、最近では 128bit の IPv6 アドレスが用いられる。IPv6 では、2004:6800:4004:0826:0000:0000:0000:2003 (www.google.co.jp) といった16進数4桁(16bit)を8個を”:”区切りで書き連ねる書き方をする。ただし16進4桁の先行する0や、全部”0000″ は省略して、”2404:6800:4004:826::2003″ と書く。IPv6 は最近では普及がかなり進んでいるが、途中のルータなどがすべて IPv6 に対応する必要があり IPv4 しか使えない組織も多い。

DNS と nslookup

IPアドレスみたいな数字の羅列は覚えることが難しい。このためコンピュータの名前からIPアドレスを調べるサービスがあり、Domain Name Service(DNS) と呼ばれる。詳しい仕組みは ドメイン名の説明の際に行うが、IP アドレスの調べ方を説明する。

ドメイン名から、IP アドレスを調べるには、nslookup (もしくは dig) を使用する。

$ nslookup www.fukui-nct.ac.jp
:
Non-authoritative answer:
Name:   www.fukui-nct.ac.jp
Address: 104.215.53.205

$ nslookup -query=A www.fukui-nct.ac.jp   # IPv4 アドレスの取得
(同上)

$ nslookup -query=AAAA www.google.co.jp   # IPv6 アドレスの取得
:
Non-authoritative answer:
Name:   www.google.co.jp
Address: 2404:6800:4004:826::2003

理解確認

  • Cクラスのサブネットに設置できるコンピュータの台数は何台?
  • “172.”で始まるプライベートアドレスでは最大何台?
  • 192.168.11.2/24 のコンピュータから、192.168.1.50にデータを送る場合、どのような処理が行われるか、IPアドレス、サブネットマスク、ゲートウェイ、ネットワーク番号を使って説明せよ。
  • 同じサブネット内で相手のIPアドレスが与えられた時、どのようにパケットが送られるか、MACアドレスとARPを交えて説明せよ。

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 ;
}

これらの関数では、木構造の全てに対する処理を実行する場合には、再帰呼び出しが必要となる。

2分ヒープ(binary heap)

2分探索木では、1つのノードにつき2つのポインタを持ち、データ1件あたりのメモリの使用量が多い。通常の「配列の先頭から昇順にデータを並べる2分探索法」では、途中にデータを挿入する場合、データを後ろにずらす必要があるため、O(N)の処理時間を要する。

これらの問題の解決法の1つとして、2分ヒープがある。左右に均一に成長している2分探索木で、上から番号を以下の様に振ると、i番目のデータの左の枝2×i+1 番目、右の枝2×i+2 番目であることが判る。

このような順序で配列にデータを保存する方法が2分ヒープである。この方式ならアルゴリズムの説明は省略するが、O(log(N))で挿入が可能となる。

int a[ 7 ] = { 53 , 11 , 86 , 10 , 22 , 65 , 92 } ;

// 2分ヒープを表示
void print_heap( int array[] , int idx , int size ) {
   if ( idx < size ) {
      // 左の枝を表示
      print_heap( array , 2*idx + 1 , size ) ;
      // 真ん中の枝を表示
      printf( "%d " , array[ idx ] ) ;
      // 右の枝を表示
      print_heap( array , 2*idx + 2 , size ) ;
   }
}

// 2分ヒープから key を検索
int find_heap( int array[] , int idx , int size , int key ) {
   while( idx < size ) {
      if ( array[ idx ] == key )
         return idx ; // 見つかったら配列の番号を返す
      else if ( array[ idx ] _____ key )  // 何が入るか考えよう
         idx = ________________ ;
      else
         idx = ________________ ;
   }
   return -1 ; // 見つからなかったら、-1 を返す
}
int main() {
   print_heap( a , 0 , 7 ) ;
   if ( find_heap( a , 0 , 7 , 65 ) >= 0 )
      printf( "Find!!¥n" ) ;
   return 0 ;
} 

Ethernet と CSMA/CD方式

CSMA/CD方式

Ethernet では、1本の線を共有するバス型であり、複数の機器が同時に信号を出力すると、電圧の高低がおかしい状態となる(衝突,コリジョン)ため、同時に信号を出さない工夫が必要となる。ただし、他の人が信号線を使っていないことを確認してから、信号を出せばいいけど、確認から信号を出すまでの遅延により、衝突を避けるのは難しい。

また、1本の線を共有する機器の数が増えてくると、衝突の発生の可能性が高まってくる。

これらの問題を解決するためのルールが CSMA/CD(Carrier Sense Multiple Access with Collision Detection)方式である。

  • 機器は、信号を出す場合、信号線が空いている状態を待ち、出力を行う。
  • もし、複数の機器が同時に信号を出した場合、電圧異常を検知したら衝突なので再送を試みる。
  • 再送を行う場合には、乱数時間待つ。(機器が多い場合は、これでも衝突が起こるかもしれない)
  • 乱数時間待っても信号線が空かない場合は、乱数時間の単位時間を倍にする。

どちらにしろ、バス共有する機器の台数が増えてくると、衝突の可能性は高まり、100台を越えるような状態は通信効率も悪くなる。

ただし、最近はスイッチングHUBで通信制御を行うことが一般的になり、CSMA/CD方式が使われることは減っている。

スイッチングHUB

*BASE-T のような、HUB による接続では、複数の機器が異なる機器どうしで通信をする場合、その通信路を時分割多重するのではなく、通信相手に応じて内部回路を直接つながるように接続するスイッチングHUB(以下SW-HUB)が普及している。

バス型通信では、1本の線を共有するため、同じネットワーク内の別機器間の通信は、傍受することができる(タッピング)。しかし、SW-HUB の場合、機器同士が直接つながるので、傍受するのが困難であり、セキュリティ的にも望ましい。

データリンク層とMACアドレス

前述のように、1つのバス型接続のネットワーク内部には、同時に設置できる機器の数には限界がある。このため、小さなネットワークに分割したもの(サブネット)を、ブリッジやルータで接続し、隣接するサブネットにサブネット内の通信情報が出ないように分割することを行う。

Ethernetに接続する機器は、機器ごとにユニークな番号(MACアドレス)を持っている。このMACアドレスは、8bit✕6個の48bitの値で、メーカー毎に割振られた範囲の値を、機器ごとに異なる値がついている。

通信は、一般的に1500byte程のパケットを単位として送受信が行われる。サブネット内の通信では、自分宛のパケットかどうかをMACアドレスを見て受け取る。これらのレイヤーは、データリンク層と呼ばれる。

旧式のHUB(Dumb HUB)は、電気的に信号を増幅するだけなので、物理層(レイヤー1)だけで通信を行う。
スイッチングHUBは、MACアドレスを見て通信相手を判断(データリンク層/レイヤー2)する。最近では、SW-HUBのコネクタ毎に、パケットにタグを付加することで、1本のネットワーク経路に仮想的な複数のネットワークを構築するタグV-LANといった方式を使う場合もある。このような機能を持つSW-HUBは特にレイヤ2スイッチとも呼ばれる。

L2スイッチとL3スイッチ

サブネットに分割し、それぞれに異なるネットワーク番号を割り振り、中継するルータで FireWall を機能させることで、セキュリティを高めることが行われる。しかし、性能の高いスイッチングHUBは高価でもあり、1つのHUBに異なるネットワークを接続する必要がでてくることもある。この場合、IPアドレスを異なるネットワークの番号を偽装されると、データが盗み見られるかもしれない。

こういった相互に分離すべきネットワークであっても、柔軟なネットワーク構成とするためには、VLAN機能を持った L2スイッチ(レイヤ2スイッチングHUB) が使われる。タグVLAN機能付きのL2スイッチでは、特定のポートにVLANのタグ番号を割り当て、ポートに入る時にパケットに VLAN のタグ情報を付加し、そのパケットは同じ VLAN のタグをもつポートからしかデータを取り出せない。

L2スイッチ(レイヤ2スイッチ)は、機器のMACアドレスやパケットに付けられたVLANのタグ番号の情報(レイヤ2=データリンク層)でパケットの流れを制御している(下記OSI参照モデルの表を参照)。最近では、許可されていない機器がネットワークに侵入する不正侵入を防ぐために、登録されていないMACアドレスのパケットを通さないといった機能がある。

OSI参照モデルとレイヤ
第7層 アプリケーション層 アプリケーションの種類の規定
第6層 プレゼンテーション層 データフォーマットの交換
第5層 セッション層 コネクションの確立や切断などの管理
第4層 トランスポート層 パケットの分割合成や再送といった管理(TCP)
第3層 ネットワーク層 隣接するネットワーク間の通信(IPアドレス)
第2層 データリンク層 直接接続された機器間の通信(MACアドレス)
第1層 物理層 物理的な接続方法(コネクタや電圧など)

スイッチングHUBの中には、レイヤ3(IPアドレス)の情報でパケットの流れを制御するものもある。こういったスイッチは、L3スイッチ(レイヤ3スイッチ)と呼ばれるが、機能的にはルータと同じである。

一般的には、LANとWANを接続するための機器はルータ、LAN内部のネットワークを分離するためのものはL3スイッチと呼ぶ。

無線LANと暗号化

無線LAN(通称 WiFi)は、IEEE 802.11 にて規格が定められている。無線LANは、使う通信周波数で、2.4GHz帯を使うものと、最近増えてきた5GHz帯のものに分けられる。

  • IEEE802.11a 5GHz帯を使う、最大54Mbps
  • IEEE802.11b 2.4GHz帯を使う、最大11Mbps
  • IEEE802.11g 2.4GHz帯を使う、最大54Mbps
  • IEEE802.11n 2.4GHz/5GHzを使う、最大600Mbps
  • IEEE802.11ac 5GHz帯を使う、最大6.9GBps
  • IEEE802.11ad 60GHz 最大6.8Gbps
  • IEEE802.11ax 2.4GHz/5GHz 最大 9.6Gbps

2.4GHz帯は、電子レンジで使う電波の周波数と重なるため、電波干渉を受けやすい。5GHz帯は、障害物の影響を受けやすい。
2.4GHzは様々な家電製品・電子機器で利用されているため、他の機器との干渉を受けやすく速度低下を起しやすいが、遠くまで電波が届きやすい。 5GHzは、この周波数帯を利用している機器が少ない為、干渉を受けにくく安定して通信できるが、あまり遠くには電波が届かず、通信が極端に不安定になる場合がある。

無線LANに接続する場合には、接続先(アクセスポイント)に付けられた名前(SSID)と、SSIDに割り振られたパスワードが必要となる。ただし無線は、電波で信号を飛ばすため、近くに行くだけで通信を傍受できる。このため、データの暗号化が必須となる。この暗号化は、そのアルゴリズムにより解読の困難さが変わる。

  • WEP 64bit / 128bit – すでに古い暗号化で専用ソフトを使うとすぐに解読される可能性が高い。使うべきではない。
  • WPA/WPA2 – 現時点の主流。
    • 暗号化方式 TKIP や 暗号化アルゴリズム AES

無線LANでは、車でセキュリティの甘いアクセスポイント(暗号化無しやWEPを使うAP)を探し、その無線LANを使ってクラッキングなどをおこなう場合も多い。(ウォードライビング)

勝手に無線LANを使われないようにするために一般的には、(1)アクセスポイントに接続できる機器をMACアドレス(機器に割り当てられた48bitの固有値)で制限したり、(2)SSIDのステルス化(APが出す電波にSSIDを入れない方式)を行う場合も多い。ただし、これらの制限をかけても専用の機器を使えば通信は傍受可能。

双方向リスト

リスト構造の利点と欠点

リストを使った集合演算のように、データを連ねたリストは、単純リストとか線形リストと呼ばれる。特徴はデータ数に応じてメモリを確保する点や、途中へのデータの挿入削除が得意な点があげられる。一方で、配列は想定最大データ件数で宣言してしまうと、実際のデータ数が少ない場合、メモリの無駄も発生する。しかし、想定件数と実データ件数がそれなりに一致していれば、無駄も必要最小限となる。リスト構造では、次のデータへのポインタを必要とすることから、常にポインタ分のメモリは、データにのみ注目すれば無駄となる。

例えば、整数型のデータを最大 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)と呼ばれる。

双方向リストは以前は、プログラムのエディタなどを実装する場合によく使われていた。エディタであれば、1つ前の行や次の行を参照することが多いため。しかし、最近では単純な双方向リストでエディタを実装することはない。

では、簡単なプログラムを書いてみよう。双方向リストのデータを簡単に生成するための補助関数から書いてみる。

// リスト生成補助関数
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つ用意するぐらいなら、先頭と末尾のデータを1つにまとめた方がムダがない。この場合上図のように末尾データが先頭データにつながる循環リストとなる。このような双方向リストでの循環した構造は、双方向循環リスト(bi-directional ring list)と呼ばれる。

deque(両端キュー)

この双方向循環リストを使うと、(1)先頭にデータを挿入(unshift)、(2)先頭のデータを取り出す(shift)、(3)末尾にデータを追加(push)、(4)末尾のデータを取り出す(pop)、といった処理が簡単に記述できる。この4つの処理を使うと、単純リスト構造で説明した、待ち行列(queue)やスタック(stack) が実現できる。この特徴を持つデータ構造は、先頭・末尾の両端を持つ待ち行列ということで、deque (double ended queue) とも呼ばれる。

理解確認

  • 双方向リストとはどのようなデータ構造か図を示しながら説明せよ。
  • 双方向リストの利点と欠点はなにか?
  • 番兵を用いる利点を説明せよ。
  • deque の機能と、それを実現するためのデータをリストを用いて実装するには、どうするか?
  • 双方向リストが使われる処理の例としてどのようなものがあるか?

高専プロコンin群馬で福井高専3チーム受賞

10/15(金),16(日)と群馬にて開催されていた、第33回高専プロコン群馬大会にて、福井高専から参加していた3チームが受賞しました。

  • 課題部門・特別賞 PaOn −ぴえんを越えるParkOnline−
    • 4EI:泉、伊藤、並河、松田、山岸、清水
    • NICT賞「起業家甲子園出場挑戦権」
  • 課題部門・敢闘賞 お神輿わっしょい −⾃宅で神輿担ぎを疑似体験−
    • 4EI:出倉、越元、小見山、ヤン
    • アバナード企業賞
  • 自由部門・敢闘賞 もうそうサイクリング −観客を巻き込むVRフィットネスゲーム−
    • 4EI:戸田、中村、吹谷、武藤
    • チームラボ企業賞
  • 競技部門 –お茶汲み同好会– 一回戦敗退

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー