ホーム » スタッフ » 斉藤徹

斉藤徹」カテゴリーアーカイブ

2025年5月
 123
45678910
11121314151617
18192021222324
25262728293031

検索・リンク

unixにおけるファイルとユーザ管理

Unix演習サーバへの接続

Unix(Linux)は、インターネットでのサーバとして広く活用されている。Linuxを試すには、Windows ならば WSL や Cygwin であったり、Mac でも使える仮想OSの VMware, VirrtualBox を使うこともできる。今回の演習では、全員が同じ環境で使うために、クラウド環境にサーバを準備し利用する。

ネットワークの向こう側にあるサーバを利用する場合、以下のような方法が使われる。

  • telnet (port 23)
    • キー入力を相手に送って、送られてくるデータを画面に表示する。
    • 通信データが暗号化されないので盗聴される心配があり、一般的には使用しない。
  • rsh (remote shell – port 514)
    • ネットワークを越えてコマンドを実行したりファイル転送ができる。
    • telnet 同様に暗号化されていないので、次に示す ssh を使うのが一般的。
  • ssh (secure shell – port 22)
    • rsh の処理を暗号化しながら実行。
    • ネットワークを越えた処理を行う際の基本だが、ssh を経由した攻撃が多いことから、通常のポート番号22以外を使ったり、アクセス制限を厳しく設定する必要がある。
  • remote Desktop
    • ネットワークの先のPCの画面をネットワーク越しに触れるようにしたもの。

教室のWiFi環境(fnct-student)では、HTTP(80) , HTTPS(443) の通信しか使えないことから、ssh(22) が通常利用できない。電子情報のWiFiアクセスポイント(nitfc-ei-student等)であれば、ssh などが使用できる。

今回授業の演習では、さくらインターネットのサーバ上のクラウドサーバを利用する。

ただし、さくらインターネットのクラウドサーバでは、ssh(port=22)が使用できるが、ssh 接続の際にログインパスワードの間違いなどが多発すると、ssh 経由の攻撃の可能性があると判断され、ssh(port=22)接続が一定時間使えなくなる対策がとられている。今回は、ゲストアカウントでパスワード入力ミスが多発することが想定されるので、port=22のsshは使用しない。

リモート接続を行う

Windows 10 or Windows 11 ならば、cmd.exe , macOS ならば、ターミナルソフトを起動し、以下の操作を行う。

$ ssh -p 443 ゲストID@演習サーバ
  • 443ポートは通常は https 用だが、今回はサーバで ssh プロトコルを 443 ポートで受け付けるように設定してある。かなり特殊な使い方なので要注意。
  • 演習サーバの接続方法(学内のみ) – サーバへの攻撃を極力へらすために非公開。
  • パスワード入力時は、打つたびに●●●といった文字は表示されません。
  • パスワード入力時にタイプミスした時は、Ctrl-U で最初から入力のやり直しができます。

ファイル操作の基本

まずは基本操作をしてみよう。ls コマンド(list) は、ディレクトリ内にあるファイルの一覧を表示する。cat コマンド(catalog)は、指定されたファイルの内容を表示する。

s53599xx@nitfcei:~$ ls
helloworld.c  Maildir  public_data  public_html

s53599xx@nitfcei:~$ ls -l
total 8
-rw-r--r-- 1 s53599xx students   76 Dec 21 14:30 helloworld.c
drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir
(略)

s53599xx@nitfcei:~$ cat helloworld.c
#include <stdio.h>

int main() {
    printf( "Hello World\n" ) ;
    return 0 ;
}
s53599xx@nitfcei:~$

ファイルをコピーするには cp コマンド(copy)、不要なファイルを消すには rm コマンド(remove)を使う。

s53599xx@nitfcei:~$ cp helloworld.c test.c
s53599xx@nitfcei:~$ ls -l
total 8
-rw-r--r-- 1 s53599xx students   76 Dec 21 14:30 helloworld.c
drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir
-rw-r--r-- 1 s53599xx students   76 Dec 21 14:40 test.c
(略)
s53599xx@nitfcei:~$ rm test.c
s53599xx@nitfcei:~$ ls -l
total 8
-rw-r--r-- 1 s53599xx students   76 Dec 21 14:30 helloworld.c
drwx------ 5 s53599xx students 4096 Dec 21 14:30 Maildir
s53599xx@nitfcei:~$

ファイル詳細表示の説明

ls -l で表示される詳細の内容は以下の通り。

属性 リンク数 所有者 グループ サイズ 日付 ファイル名
rw- r– r– 1 s53599xx students 76 Dec 21 14:30 helloworld.c
d rwx 5 s53599xx students 4096 Dec 21 14:30 Maildir
d -: 通常ファイル, d:ディレクトリ
rw- r,w,x 所有者が r:読み出し, w:書き込み, -: 権限なし
ファイルなら、x:実行可能
ディレクトリなら、x:ディレクトリに入れる
r – – – – – グループの rwx の属性 r– は 読み込みだけ許可
r – – – – – その他の rwx の属性  — は、読み書き禁止

基本的なファイル操作コマンド一覧

操作 Linux Windows
ディレクトリ一覧(list)
ディレクトリ詳細
ls 場所  ※
ls -l 場所
dir /w 場所  ※
dir 場所
※ 省略時はカレントディレクトリ
ファイル表示(catalog) cat 場所 type 場所
ファイルコピー(copy) cp コピー元 コピー先
cp コピー元 コピー先ディレクトリ
copy コピー元 コピー先
ファイル削除(remove) rm 場所 del 場所
ディレクトリ作成(make dir) mkdir 場所 md 場所
ディレクトリ削除(remove dir) rmdir 場所 rmdir 場所
カレントディレクトリ移動
(change directory)
cd 場所 cd 場所
ドライブの場合は
ドライブ名:
所有者を変更(change owner) chown 所有者 場所
グループを変更(change group) chgrp グループ 場所
属性を変更(change mode) chmod 属性 場所 ←属性の書き方

ワイルドカード文字

ls などのコマンドで、複数のファイルを対象とするとき、ワイルドカード文字が使える。

任意の1文字
?
(例)
$ ls          # 全部のファイル
aaa.c  ab.c    abc.c   bcd.c   defgh.c  hij.cxx
$ ls a?.c   # aで始まる2文字のC言語ファイル
ab.c
$ ls ???.c  # 3文字のC言語のファイル
aaa.c   abc.c   bcd.c
任意の文字
*
(例)
$ ls a*.c   # aで始まるC言語ファイル
aaa.c ab.c abc.c
$ ls *.cxx  # 拡張子が.cxxのファイル(C++)
hij.cxx

相対PATHと絶対PATH

ファイルの場所を指定するには、2つの方法がある。

絶対PATHは、木構造の根(ルートディレクトリ / で表す) からの経路のディレクトリ名を”/”で区切って書き連ねる。ルートディレクトリからの場所であることを示すために、先頭を / で始める。住所を /福井県/越前市/宮谷町/斉藤家 と書くようなもの。

相対PATHは、現在注目しているディレクトリ(カレントディレクトリと呼ぶ)からの経路を書く。住所でいうと、/福井県/越前市 に注目している状態で、宮谷町/斉藤家 と書くようなもの。

ただし、/福井県/福井市 に注目している状態で、片町/山本家 は1つのファイルでも、/福井県/福井市/片町/山本家 とは別に /石川県/金沢市/片町/山本家 があるかもしれない。

上記の絵であれば、/home/tsaitoh/helloworld.c を、相対PATHで書く場合、s53599xx の一つ上にさかのぼって場所を指定することもできる。一つ上のディレクトリ(親ディレクトリ).. (ピリオド2つ)

この場合、” $ cat ../tsaitoh/helloworld.c ” の様な相対PATHでもアクセスできる。

カレントディレクトリ自身を表す場合は、. (ピリオド1つ)を使う。

/home/s53599xx/helloworld.c の場所は、” $ cat ./helloworld.c ” と書くこともできる。

ユーザとグループ

unixでは、ユーザとグループでアクセス制限をすることができる。ユーザ情報は、/etc/passwd ファイルで確認できる。グループ情報は、/etc/group ファイルで確認できる。

$ more /etc/passwd
root:x:0:0:root:/root:/bin/bash
daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin
bin:x:2:2:bin:/bin:/usr/sbin/nologin
(略)
guest00:x:1200:1200:guest00,,,:/home0/guests/guest00:/bin/bash

$ more /etc/group
root:x:0:
daemon:x:1:
bin:x:2:
(略)
guests:x:1200:guest00,guest01,guest02,...
/etc/passwd /etc/group
guest00 — ユーザID
x — 昔は暗号化されたパスワード
1200 — ユーザID番号
1200 — グループID番号(/etc/groupを参照)
guest00,,, — ユーザの正式名や電話番号など
/home0/guests/guest00 — ホームディレクトリ
/bin/bash — 使用する shell
guests — グループID
x — 昔は暗号化されたグループパスワード
1200 — グループID番号
guest00,guest01,guest02 — 所属するユーザ一覧

アクセス制限の実験

/home0/Challenge/AccesControl に、いくつかのファイルが保存してあり、t-saitoh が見ると、以下のようなファイルであった。tree コマンドでは、いくつかのディレクトリとその中のファイルが確認できる。しかし、ls -al にてファイルのアクセス権限が確認できる。tree コマンドで確認できるファイルにアクセスすると何が起こるか確認すること。

$ cd /home0/Challenge/AccessControl
$ id        # 自分のID,グループを確認
uid=1200(guest00) gid=1200(guests) groups=1200(guests)
$ tree      # ディレクトリ構造を表示
$ ls -al    # 権限情報を表示

Windows とアクセスコントロール

Unix のシステムでは、ファイル毎に、ユーザID,グループIDを割り当て、ユーザ, グループ, その他に対して、Read, Write などの制限をかける。Windows では、さらに細かくアクセス制限を加えることができる。Windows では、1つのファイルに対して、ユーザやグループのRead/Writeなどの制限をいくつでも設定できる。Access Control List と呼ばれる。

主要なディレクトリとファイルシステム

unix では、すべてのデバイスを / (ルートディレクトリ) 配下に木構造につなげて管理している。CD-ROM や USB ディスクなどは、指定したディレクトリに mount (マウント) して使用する。

ext4 は、Linux で採用されているファイルシステムで、システムの保存に使われる。

tmpfs は、主記憶(D-RAM) の一部を、ディスクと同じように扱えるようにしたファイルシステム。通称 ram disk(ラムディスク)。保存はメモリへのアクセスなので、保存やアクセスは極めて高速だが、保存領域は少ない。高速に扱えて、システムが再起動された時に消えても問題のない情報を保存するために使われる。

proc は、実行中のプロセス情報を、ハードディスクに保存されたファイルの様に参照できる。

vfat , exfat は、USBメモリ, SDカード のデータ保存で使われるファイルシステムで、Windows(MS-DOS) で使われている保存形式。ファイルにファイル所有者などの概念がない

ntfs は、Windows で使われているファイル形式。

swap は、仮想メモリのためのデータが保存される。主記憶メモリが不足した際に、使用頻度の少ないメモリ領域をハードディスクに保存するための領域。以下のような free コマンドで使用状況が確認できる。一般的に、主記憶メモリの数倍を割り当てる。

派生と継承と仮想関数

前回の派生と継承のイメージを改めて記載する。

// 基底クラス
class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   Person( const char s[] , int x )
     : age( x ) {
      strcpy( name , s ) ;
   }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
// 派生クラス(Student は Person から派生)
class Student : public Person {
private:
   char dep[ 20 ] ;
   int  grade ;
public:
   Student( const char s[] , int x ,
            const char d[] , int g )
            : Person( s , x ) // 基底クラスのコンストラクタ
   {  // 追加された処理
      strcpy( dep , d ) ;
      grade = g ;
   }
   void print() {
      Person::print() ;       // 基底クラスPersonで名前と年齢を表示
      printf( "- %s %d\n" , dep , grade ) ;
   }
} ;
int main() {
   Person saitoh( "t-saitoh" , 55 ) ;
   Student yama( "yamada" , 21 , "ES" , 1 ) ;
   Student nomu( "nomura" , 22 , "PS" , 2 ) ; 
   saitoh.print() ; // 表示 t-saitoh 55
   yama.print() ;   // 表示 yamada 21
                    //      - ES 1
   nomu.print() ;   // 表示 nomura 22
   return 0 ;       //      - PS 2
}

このような処理でのデータ構造は、次のようなイメージで表される。

派生クラスでの問題提起

基底クラスのオブジェクトと、派生クラスのオブジェクトを混在してプログラムを記述したらどうなるであろうか?
上記の例では、Person オブジェクトと、Student オブジェクトがあったが、それをひとまとめで扱いたいこともある。

以下の処理では、Person型の saitoh と、Student 型の yama, nomu を、一つの table[] にまとめている。

int main() {
   Person saitoh( "t-saitoh" , 55 ) ;
   Student yama( "yamada" , 21 , "ES" , 1 ) ;
   Student nomu( "nomura" , 22 , "PS" , 2 ) ;

   Person* table[3] = {
      &saitoh , &yama , &nomu ,
   } ;
   for( int i = 0 ; i < 3 ; i++ ) {
      table[ i ]->print() ;
   }
   return 0 ;
}

C++では、Personへのポインタの配列に代入する時、Student型ポインタは、その基底クラスへのポインタとしても扱える。ただし、このように記述すると、table[] には、Person クラスのデータして扱われる。

このため、このプログラムを動かすと、以下のように、名前と年齢だけが3人分表示される。

t-saitoh 55
yamada   21
nomura   22

派生した型に応じた処理

上記のプログラムでは、 Person* table[] に、Person*型,Student*型を混在して保存をした。しかし、Person*として呼び出されると、yama のデータを表示しても、所属・学年は表示されない。上記のプログラムで、所属と名前を表示することはできないのだろうか?

// 混在したPersonを表示
for( int i = 0 ; i < 3 ; i++ )
   table[i]->print() ;
// Student は、所属と名前を表示して欲しい
t-saitoh 55
yamada 21
- ES 1
nomura 22
- PS 2

上記のプログラムでは、Person型では、後でStudent型と区別ができないと困るので、Person型に、Person型(=0)なのか、Student型(=1)なのか区別するための type という型の識別番号を追加し、type=1ならば、Student型として扱うようにしてみた。

// 基底クラス
class Person {
private:
   int  type ; // 型識別情報
   char name[ 20 ] ;
   int  age ;
public:
   Person( int tp , const char s[] , int x )
     : type( tp ) , age( x ) {
      strcpy( name , s ) ;
   }
   int type_person() { return type ; }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
// 派生クラス(Student は Person から派生)
class Student : public Person {
private:
   char dep[ 20 ] ;
   int  grade ;
public:
   Student( int tp , const char s[] , int x ,
            const char d[] , int g )
            : Person( tp , s , x ) // 基底クラスのコンストラクタ
   {  // 追加された処理
      strcpy( dep , d ) ;
      grade = g ;
   }
   void print() {
      Person::print() ;       // 基底クラスPersonで名前と年齢を表示
      printf( "- %s %d\n" , dep , grade ) ;
   }
} ;
int main() {
   // type=0 は Person 型、type=1は Student 型
   Person saitoh( 0 , "t-saitoh" , 55 ) ;
   Student yama( 1 , "yamada" , 21 , "ES" , 1 ) ;
   Student nomu( 1 , "nomura" , 22 , "PS" , 2 ) ;

   Person* table[3] = {
      &saitoh , &yama , &nomu ,
   } ;
   for( int i = 0 ; i < 3 ; i++ ) {
      switch( table[i]->type_person() ) {
      case 0 :
         table[i]->print() ;
         break ;
      case 1 :
         // 強制的にStudent*型として print() を呼び出す。
         //   最近のC++なら、(static_cast<Student*>(table[i]))->>print() ;
         ((Student*)table[i])->print() ;
         break ;
      }
   }
   return 0 ;
}

しかし、このプログラムでは、プログラマーがこのデータは、Personなので type=0 で初期化とか、Studentなので type=1 で初期化といったことを記述する必要がある。

また、関数を呼び出す際に、型情報(type)に応じて、その型にふさわしい処理を呼び出すための switch 文が必要になる。

もし、派生したクラスの種類がいくつもあるのなら、(1)型情報の代入は注意深く書かないとバグの元になるし、(2)型に応じた分岐処理は巨大なものになるだろう。実際、オブジェクト指向プログラミングが普及する前の初期の GUI プログラミングでは、巨大な switch 文が問題となっていた。巨大な switch 文は、選択肢だけの if else-if else-if が並ぶと処理効率も悪い。

仮想関数

上記の、型情報の埋め込みと巨大なswitch文の問題の解決策として、C++では仮想関数(Virtual Function)が使える。

型に応じて異なる処理をしたい関数があったら、その関数の前に virtual と書くだけで良い。このような関数を、仮想関数と呼ぶ。

// 基底クラス
class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   Person( const char s[] , int x )
     : age( x ) {
      strcpy( name , s ) ;
   }
   virtual void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
// 派生クラス(Student は Person から派生)
class Student : public Person {
private:
   char dep[ 20 ] ;
   int  grade ;
public:
   Student( const char s[] , int x ,
            const char d[] , int g )
            : Person( s , x ) // 基底クラスのコンストラクタ
   {  // 追加された処理
      strcpy( dep , d ) ;
      grade = g ;
   }
   virtual void print() {
      Person::print() ;       // 基底クラスPersonで名前と年齢を表示
      printf( "- %s %d\n" , dep , grade ) ;
   }
} ;
int main() {
   // type=0 は Person 型、type=1は Student 型
   Person saitoh( "t-saitoh" , 55 ) ;
   Student yama( "yamada" , 21 , "ES" , 1 ) ;
   Student nomu( "nomura" , 22 , "PS" , 2 ) ;

   Person* table[3] = {
      &saitoh , &yama , &nomu ,
   } ;
   for( int i = 0 ; i < 3 ; i++ ) {
      table[i]->print() ;
   }
   return 0 ;
}

クラスの中に仮想関数が使われると、C++ では、プログラム上で見えないが、何らかの型情報をオブジェクトの中に保存してくれる。

また、仮想関数が呼び出されると、その型情報を元に、ふさわしい関数を自動的に呼び出してくれる。このため、プログラムも table[i]->print() といった極めて簡単に記述できるようになる。

関数ポインタ

仮想関数の仕組みを実現するためには、関数ポインタが使われる。

以下の例では、返り値=int,引数(int,int)の関数( int(*)(int,int) )へのポインタfpに、最初はaddが代入され、(*fp)(3,4) により、7が求まる。

int add( int a , int b ) {
   return a + b ;
}
int mul( int a , int b ) {
   return a * b ;
}
int main() {
   int (*fp)( int , int ) ;
   fp = add ;
   printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3+4=7
   fp = mul ;
   printf( "%d\n" , (*fp)( 3 , 4 ) ) ; // 3*4=12

   int (*ftable[2])( int , int ) = {
      add , mul ,
   } ;
   for( int i = 0 ; i < 2 ; i++ )
      printf( "%d\n" , (*ftable[i])( 3 , 4 ) ) ;
   return 0 ;
}

仮想関数を使うクラスが宣言されると、一般的にそのコンストラクタでは、各クラス毎の仮想関数へのポインタのテーブルが型情報として保存されるのが一般的。仮想関数の呼び出しでは、仮想関数へのポインタを使って処理を呼び出す。このため効率よく仮想関数を動かすことができる。

仮想関数の実装方法

仮想関数の一般的な実装方法としては、仮想関数を持つオブジェクトには型情報として仮想関数へのポインタテーブルへのポインタを保存する。この場合、仮想関数の呼び出しは、object->table[n]( arg… ) のような処理が行われる。

配列に要素を追加

データが登録済みかどうかを判定する処理を作るために、登録された値を配列に次々と値を追加保存する場合、どのようにプログラムを記述するだろうか?

配列にデータを追加

次々と与えられた値を保存していくのであれば、Java であれば下記のようなコードが一般的であろう。
でも、ArrayList とはどのようにデータを覚えているのだろうか? なぜ 宣言は ArrayList<Integer> array であって ArrayList<int> array で宣言するとエラーが出るのであろうか?

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // ArrayList は連続アドレス空間に保存してくれる可変長配列
        //   ランダムアクセスをする場合に向いている
        ArrayList<Integer> array = new ArrayList<Integer>() ;
        array.add( 11 ) ;
        array.add( 2 ) ;
        array.add( 333 ) ;
        
        for( Integer i : array ) {
            System.out.println( i ) ;
        }
    }
}

このような ArrayList のようなデータ構造の仕組みを考えるために、最も単純な配列でプログラムを作ってみる。

末尾に追加

import java.util.*;

public class Main {
    static int[] array = new int[ 10 ] ;
    static int   size  = 0 ;

    public static void add( int x ) {
        array[ size ] = x ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        add( 11 ) ;
        add( 2 ) ;
        add( 333 ) ;
        
        for( int i = 0 ; i < size ; i++ )
            System.out.println( array[i] ) ;
    }
}

同じ処理をC言語で書いてみる。

#include <stdio.h>

int array[ 10 ] ;
int size = 0 ;

void add( int x ) {          // if ( size < array.length ) ... の判定が必要かも
    array[ size ] = x ;
    size++ ;
}

int main() {
    add( 11 ) ;
    add( 2 ) ;
    add( 333 ) ;

    for( int i = 0 ; i < size ; i++ )
        printf( "%d\n" , array[ i ] ) ;
    return 0 ;
}

しかし、このプログラムでは、最初に宣言した要素数10個を越えてデータを保存できないし、配列溢れさせないためには要素数の上限チェックも必要となるだろう。

昇順に並べながら途中に要素を追加

前述のプログラムでは、配列の末尾の場所を size で覚えておき、末尾にデータを追加していた。でも、配列に保存されている値の中から目的の値が含まれているか検索したいのであれば、配列に要素を昇順に保存しておいて2分探索法を使うのが一般的であろう。では、前述のプログラムを昇順で保存するにはどうすべきか?

最も簡単な方法で書くのであれば、下記のようなコードになるかもしれない。

public static void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) { // ここは2分探索で書けば O( log N ) にできるかも
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )   // 途中に挿入は、コレじゃダメ?
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- ) // 途中にデータを入れるために要素を1つ後ろに移動
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}
void add( int x ) {
    int i ;
    for( i = 0 ; i < size ; i++ ) {
        if ( array[ i ] > x )
            break ;
    }
    // for( int j = i ; j < size ; j++ )
    //     array[ j + 1 ] = array[ j ] ;
    for( int j = size - 1 ; j >= i ; j-- )
        array[ j + 1 ] = array[ j ] ;
    array[ i ] = x ;
    size++ ;
}

このプログラムでは、for( i … ) の処理でデータを挿入すべき場所を見つけ、for( int j … ) の繰り返しでデータを1つ後ろにずらしてから要素を加えている。

for( i … ) の処理は、このプログラムでは O( N ) となっているが、2分探索法を用いれば O( log N ) に改善ができるかもしれない。しかし、for( int j… ) の処理は、データを1つ後ろにずらす必要があるため O( N ) の処理が必要となる。

ここで、途中にデータを追加する処理の効率を改善することを考える。

リスト構造の導入

以下のデータ構造では、配列にデータと次のデータの場所を覚えることで、一見デタラメな順序に保存されているようにみえるが、next[] に次の値の保存されている場所が入っている。

import java.util.*;

public class Main {           //    0    1    2    3    4    5
    static int[] data = new int[] { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
    static int[] next = new int[] { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
    static int   size = 5 ;
    static int   top = 0 ;

    static void insert( int n , int x ) {
        data[ size ] = x ;
        next[ size ] = next[ n ] ;
        next[ n ] = size ;
        size++ ;
    }
    
    public static void main(String[] args) throws Exception {
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
        insert( 2 , 25 ) ;
        for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
            System.out.println( data[ idx ] ) ;
    }
}
#include <stdio.h>

int  data[ 10 ] = { 11 , 55 , 22 , 44 , 33 , 0 , 0 , 0 , 0 , 0 } ;
int  next[ 10 ] = { 2  , -1 , 4  , 1  , 3  , 0 , 0 , 0 , 0 , 0 } ;
int  size = 5 ;
int  top  = 0 ;

void insert( int n , int x ) {
    data[ size ] = x ;
    next[ size ] = next[ n ] ;
    next[ n ] = size ;
    size++ ;
}

int main() {
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    insert( 2 , 25 ) ;
    for( int idx = top ; idx >= 0 ; idx = next[ idx ] )
        printf( "%d\n" , data[ idx ] ) ;
    return 0 ;
}

このようなデータ構造であれば、データ自体は末尾に保存しているが、次の値が入っている場所を修正することで途中にデータを挿入することができる。この方法であれば、途中にデータを入れる場合でもデータを後ろにずらすような処理が不要であり、O(1)で途中にデータを挿入できる。

同じプログラムを、データと次のデータの配列番号のオブジェクトで記述してみた。

import java.util.*;

class DataNext {
    public int data ;
    public int next ;
    DataNext( int d , int n ) {
        this.data = d ;
        this.next = n ;
    }
}

public class Main {
    public static DataNext[] table = {
        new DataNext( 11 , 2 ) ,
        new DataNext( 55 , -1 ) ,
        new DataNext( 22 , 4 ) ,
        new DataNext( 44 , 1 ) ,
        new DataNext( 33 , 3 ) ,
        null , 
        null , 
        null ,
        null ,
        null ,
    } ;
    public static int size = 5 ;
    
    public static void insert( int n , int x ) {
        table[ size ] = new DataNext( x , table[ n ].next ) ;
        table[ n ].next = size ;
        size++ ;
    }
    public static void main(String[] args) throws Exception {
        for( int idx = 0 ; idx >= 0 ; idx = table[ idx ].next )
            System.out.println( table[ idx ].data ) ;
            
        insert( 2 , 25 ) ;
        
        for( int idx = 0 ; idx >= 0 ; idx = table[ idx ].next )
            System.out.println( table[ idx ].data ) ;
    }
}

このプログラムでは、配列の当初の長さを超えてデータを格納することはできない。

リスト構造 ListNode

前述の data と next で次々とデータを続けて保存するために、リスト構造(連結リスト)を定義する。

import java.util.*;

class ListNode {
    int      data ;
    ListNode next ;
    ListNode( int d , ListNode nx ) {
        this.data = d ;
        this.next = nx ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        ListNode top = new ListNode( 11 , new ListNode( 22 , new ListNode( 33 , null ) ) ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;

        top.next = new ListNode( 15 , top.next ) ;

        for( ListNode p = top ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}
#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int       data ;
    ListNode* next ;
} ;

ListNode* newListNode( int d , ListNode* nx ) {
    ListNode* _this = new ListNode() ;
    if ( _this != NULL ) {
        _this->data = d ;
        _this->next = nx ;
    }
    return _this ;
}

int main() {
    ListNode* top = newListNode( 11 , newListNode( 22 , newListNode( 33 , NULL ) ) ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    top->next = newListNode( 15 , top->next ) ;
    for( ListNode* p = top ; p != NULL ; p = p->next )
        printf( "%d\n" , p->data ) ;
    return 0 ;
}

Javaのジェネリクス

Javaのジェネリクス(C++のテンプレート)を使って書いてみた。ジェネリクスは、クラスやメソッドにおいて、特定の型を指定することなく動作するコードを記述することができる機能。これにより、型安全性を保ちながら、コードの再利用性と柔軟性を向上させることがでる。

import java.util.*;

class ListNode<T> {
    T           data ;
    ListNode<T> next ;
    
    ListNode( T d , ListNode<T> n ) {
        this.data = d ;
        this.next = n ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        // var 宣言は型推論で、右辺のデータ型を自動的に選択してくれる。
        // itop は整数型のリスト
        var itop = new ListNode<Integer>( 11 , new ListNode<Integer>( 22 , new ListNode<Integer>( 33 , null ) ) ) ;
        // new List<int>( 11 , ... ) と書くと、<>の中は reference しか使えないと言われる。
        for( var p = itop ; p != null ; p = p.next )
            System.out.println( p.data ) ;

        // stop は文字列型のリスト
        var stop = new ListNode<String>( "aa" , new ListNode<String>( "bb" , new ListNode<String>( "cc" , null ) ) ) ; 
        for( var p = stop ; p != null ; p = p.next )
            System.out.println( p.data ) ;
    }
}

前述のプログラムをJavaのジェネリッククラスで記述

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // LinkedList は上記のリスト構造で保存される。
        //    途中に要素の追加削除を行ったり、シーケンシャルアクセスに向いたデータ構造
        var top = new LinkedList<Integer>() ;
        top.add( 11 ) ;
        top.add( 22 ) ;
        top.add( 33 ) ;
        for( int i : top )            // 11 22 33
            System.out.println( i ) ;
        top.add( 1 , 15 ) ;
        for( int i : top )            // 11 15 22 33
            System.out.println( i ) ;
    }
}

クラスの宣言とコンストラクタ・メソッド

import java.util.*;

// クラス宣言
class Person {
    // データ構造
    String name ;
    int    age ;

    // コンストラクタ(データ構造を初期化する関数)
    Person( String n , int x ) {
        this.name = n ;    // this は対象となるデータそのものを指す
        this.age  = x ;    // 対象が明言されていれば、this は省略可能
    }
    // データを扱うメソッド
    void print() {                 // データを表示
        System.out.println( this.name + "," + this.age ) ;
    }
    boolean sameAge( Person x ) {  // 同じ年齢か判断するメソッド
        return this.age == x.age ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {

        Person tsaitoh = new Person( "Tohru Saitoh" ,  59 ) ;
        Person tomoko  = new Person( "Tomoko Saitoh" , 48 ) ;

        tsaitoh.print() ;  // Tohru Saitoh, 59
        tomoko.print() ;   // Tomoko Saitoh,48

        if ( tsaitoh.sameAge( tomoko ) ) {
            // sameAge( Person x ) では、
            // this = tsaitoh , x = tomoko となって呼び出される
            System.out.println( "同じ年齢ですよ" ) ;
        }
        Person[] family = new Person[ 2 ] ;
        family[0] = tsaitoh ;
        family[1] = tomoko ;
        for( int i = 0 ; i < 2 ; i++ )
            family[ i ].print() ;
    }
}こ

このプログラムのデータ構造は下記のような状態。

フローチャートと整数型

学際科目の情報制御基礎において、プログラムの基本としてフローチャートと基本的な処理を説明し、数値型の注意点を説明。

フローチャートの基本

プログラムの処理の順序を理解するには、初心者であればフローチャート(流れ図)を使う。

処理の1つ1つを箱で表し、流れを箱の間の矢印で示すことでアルゴリズム(プログラムの考え方)や処理順序を表現する。処理単位の箱は、命令の種類によって箱の書き方が決まっている。

上図右側のフローチャートの例では、以下の説明のように実行され、0,1,2,…,9 が表示され、最終的に変数 i が10以上になり処理を停止する。

(1) 変数 i に 0 を保存
(2) 変数 i は10未満なら(3)、10以上なら終了
(3) 変数 i を表示
(4) i = i + 1 右辺の計算結果を、左辺に代入iが0から1に変化
(5) 処理(2)から繰り返し。

上記のようなプログラムは、C言語であれば以下のようになる。

#include <stdio.h>                 | 入出力関数を使うための準備

int main() {                       | 最初に main() という関数が呼び出される。
   int i ;                         | 変数 i の入れ物を準備
   for( i = 0 ; i < 10 ; i++ ) {   | 最初に i = 0 を行い、i < 10 の条件を満たす間繰り返し、
                                   |       繰り返しの度に i を1つ増やす
      printf( "%d\n" , i ) ;       |    i の値を表示
   }
   return 0 ;                      | 正しく終わったら0を返す。
}

練習問題1

以下のフローチャートの処理A,処理B,処理C,処理Dの実行結果を答えよ。

  • 電気電子工学科,電子情報工学科の学生は、出席番号が偶数は処理C,奇数は処理Dについて回答せよ。
  • それ以外の学科の学生は、出席番号が偶数は処理A,奇数は処理Bの結果について回答せよ。
  • このプログラムではどういった意味の値を求めようとしているのか答えよ。

情報量の単位

データを覚える最小単位は、0と1の2通りで表される1bit (ビット)と呼ぶ。単位として書く場合には b で表す。さらに、その1bitを8個組み合わせると、256通りの情報を保存できる。256通りあれば一般的な英数字などの記号を1文字保存する入れ物として便利であり、この単位を 1byte (バイト) と呼ぶ。単位として書く場合には B で表す。

通信関係の人は8bit=1byteを1オクテットと呼ぶことも多い。日本語を表現するには、かなや漢字を使うため16bit = 2byte = 1word(ワード) で表現することが多い。(ただしワードは32bitを意味することもあるので要注意, double word=32bit, quad word=64bit という呼び方もある。)

物理では単位が大きくなると、103=kキロ,106=Mメガ,109=Gギガ,1012=Tテラ を使うが、コンピュータの世界では、103≒210=1024 なので、1kB(キロバイト)というと1024Bを意味することが多い。明確に区別する時は、1024B(バイト)=1KiB(キビバイト), 10242B=1MiB(メビバイト), 10243B=1GiB(ギビバイト) などと記載する。

2進数,8進数,16進数

プログラムの中で整数値を覚える場合は、2進数の複数桁で記憶する。例えば、2進数3桁(3bit)であれば、000, 001, 010, 011, 100, 101, 110, 111 で、10進数であれば 0~7 の8通りの値が扱える。(8進数)

2進数4桁(4bit)であれば、0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111 の16通りを表現できる(16進数)。これを1桁で表現するために、0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F を使って表現する。

例  8進数    16進数
    0123    0x123     ※C言語では、
  +  026   + 0xEA      8進数を表す場合、先頭に0をつけて表す。
 -------- --------     16進数を表す場合、先頭に0xをつけて表す。
    0151    0x20D      0x3+0xA = 0xD
                       0x2+0xE = 2+14 = 16 = 0x0 + 桁上がり
                       0x1+桁上がり = 0x2

整数型と扱える値の範囲

コンピュータの開発が進むにつれ計算の単位となるデータ幅は、8bit, 16bit, 32bit, 64bit と増えていった。整数型データには、正の値しか覚えられない符号無し整数と、2の補数で負の数を覚える符号付き整数に分けられる。

プログラムを作るためのC言語では、それぞれ 8bitの文字型(char)、16bitの short int型、32bitの int 型、64bitの long int 型(C言語では long int で宣言すると32bitの環境も多いので要注意)があり、それぞれに符号なし整数(unsigned), 符号あり整数(signed: C言語の宣言では書かない)がある。

精度 符号あり 符号なし
8bit(1byte) char (int8_t) unsigned char (uint8_t)
16bit(2byte) short int (int16_t) unsigned short int (uint16_t)
32bit(4byte) int (int32_t) unsigned int (uint32_t)
64bit(8byte) long int (int64_t) unsigned long int (uint64_t)

符号付きのデータは、負の数は2の補数によって保存され、2進数の最上位bit(符号ビット)負の数であれば1、正の数であれば0となる。

整数型で扱える数

(例) 符号なしの1byte(8bit)であれば、いくつの数を扱えるであろうか?

符号なしの N bit の整数であれば2N通りの値を表現でき、0(2N-1) までの値が扱える。

bit数 符号なし(unsigned)
8 unsigned char 0~28-1 0~255
16 unsigned short int 0~216-1 0~65535
32 unsigned int 0~232-1 0~4294967295

符号付きの N bit の整数であれば、2の補数表現では最上位ビット(MSB)が符号を表すために使う。8bitの符号付整数-100を考えると:

10進数 16進数 2進数
100)10 64)16 0110,0100)2
-100)10 9C)16 1001,1100)2

正の数なら残りの(N-1)bitで扱うため 0〜2N-1-1を表現できる。負の数は2N-1通りを表現できるので、N bit の符号つき整数は、-2N-1 〜0〜 2N-1-1の範囲の値を覚えられる。

bit数 符号あり(signed)
8 char -27~0~27-1 -128~127
16 short int -215~0~215-1 -32768~32767
32 int -231~0~231-1 -2147483648~2147483647

2の べき乗 の概算

プログラムを作る場合、2のべき乗がだいたいどの位の値なのか知りたいことが多い。この場合の計算方法として、2つの方法を紹介する。

  • 232 = 22 × (210)3 = 4 × 10243 ≒ 4,000,000,000
  • 232をN桁10進数で表すとすれば なので、両辺のlog10を求める。

      (つまり、bit数に0.3をかければ10進数の桁数が求まる。)

数値の範囲の問題で動かないプログラム

この話だけだと、扱える数値の上限について実感がわかないかもしれないので、以下のプログラムをみてみよう。(C言語の詳細は説明していないので、問題点がイメージできるだけでいい。)

組み込み系のコンピュータでは、int 型で宣言される変数でも、16bitの場合もある。以下のプログラムは期待した値が計算できない例である。以下の例では、16bit int型として short int で示す。

// ✳️コード1
#include <stdio.h>
#include <math.h>

int main() { // 原点から座標(x,y)までの距離を求める
   short int x  = 200 ;
   short int y  = 200 ;
   short int r2 = x*x + y*y ;  // (x,y)までの距離の2乗
   short int r  = sqrt( r2 ) ; // sqrt() 平方根
   printf( "%d\n" , r ) ;      // 何が求まるか?
   return 0 ;                  // (例) 200√2 = 282ではなく、120が表示された。
}

コンピュータで一定時間かかる処理を考えてみる。

// コード2.1
// 1 [msec] かかる処理が以下のように書いてあったとする。
short int i ;
for( i = 0 ; i < 1000 ; i++ )
   NOP() ; // NOP() = 約1μsecかかる処理とする。

// ✳️コード2.2
// 0.5 [sec]かかる処理を以下のようにかいた。
short int i ;
for( i = 0 ; i < 500000 ; i++ )
   NOP() ;
// でもこの処理は16bitコンピュータでは、1μsecもかからずに終了する。なぜか?

上記の例は、性能の低い16bit コンピュータの問題で、最近は32bit 整数型のコンピュータが普通だし、特に問題ないと思うかもしれない。でも、32bit でも扱える数の範囲で動かなくなるプログラムを示す。

OS(unix) では、1970年1月1日からの経過秒数で時間(unix時間)を扱う。ここで、以下のプログラムは、正しい値が計算できなかった有名な例である。(2004年1月11日にATMが動かなくなるトラブルの原因だった)

// ✳️コード3.1
int t1 = 1554735600 ; // 2019年4月09日,00:00
int t2 = 1555340400 ; // 2019年4月16日,00:00

// この2日の真ん中の日を求める。
//  t1       |        t2
//  |--------+--------|
//  |      t_mid      |
//  以下のプログラムは、正しい 2019年4月12日12:00 が求まらない。なぜか?
int t_mid = (t1 + t2) / 2;  // (例) 1951年03月25日 08:45 になった。

// コード3.2
//  以下のプログラムは正しく動く。 time_t 型(時間処理用の64bit整数)を使えば問題ない。
time_t t1 = 1554735600 ; // 2019年4月09日,00:00
time_t t2 = 1555340400 ; // 2019年4月16日,00:00

// time_t型が32bitであったとしても桁溢れない式
time_t t_mid = t1 + (t2 - t1) / 2 ;

練習問題2

以下の整数の範囲を具体的な値で答えよ。
出席番号・自分の誕生日(の日にち)に合わせて該当する2問について答えること。

  1. 7bitの符号なし整数で扱える数値の範囲 (出席番号が偶数)
  2. 12bitの符号あり整数で扱える数値の範囲 (出席番号が奇数)
  3. 20bitの符号なし整数で扱える数値の範囲 (誕生日の日づけが偶数)
  4. 24bitの符号あり整数で扱える数値の範囲 (誕生日の日づけが奇数)

練習問題3

先に示した数値の範囲が原因で動かないプログラム(コード1,コード2.2,コード3.1)の中から1つを選んで、計算結果が正しく求まらない原因を、具体的な値を示しながら説明せよ。

練習問題1,練習問題2,練習問題3について、レポートとして提出せよ。

Teamsのこちらの共有フォルダに、回答記入用のひな型がおいてあるので、この書式を参考に各自レポートにまとめ、同フォルダに提出してください。

PHPとデータベースによるバックエンドプログラミング

前回の講義では、Webページの作り方として、JavaScriptを用いたブラウザで動くプログラミングについて説明を行った。今回の授業では、データを管理しているサーバ側(バックエンド)で使われるプログラミング言語 PHP についての紹介と、データを管理するためのプログラム言語 SQL について説明し、簡単な演習をレポート課題とする。

前回授業の未解説部分

PHPとデータベースによるバックエンドプログラミング

派生と継承

隠ぺい化の次のステップとして、派生・継承を説明する。オブジェクト指向プログラミングでは、一番基本となるデータ構造を宣言し、その基本構造に様々な機能を追加した派生クラスを記述することでプログラムを作成する。今回は、その派生を理解するためにC言語で発生する問題点を考える。

派生を使わずに書くと…

元となるデータ構造(例えばPersonが名前と年齢)でプログラムを作っていて、 途中でその特殊パターンとして、所属と学年を加えた学生(Student)という データ構造を作るとする。

// 元となる構造体(Person) / 基底クラス
struct Person {
   char name[ 20 ] ; // 名前
   int  age ;        // 年齢
} ;
// 初期化関数
void set_Person( struct Person* p ,
                 char s[] , int x ) {
   strcpy( p->name , s ) ;
   p->age = x ;
}
// 表示関数
void print_Person( struct Person* p ) {
   printf( "%s %d\n" , p->name , p->age ) ;
}
int main() {
   struct Person saitoh ;
   set_Person( &saitoh , "t-saitoh" , 50 ) ;
   print_Person( &saitoh ) ;
   return 0 ;
}

パターン1(そのまんま…)

上記のPersonに、所属と学年を加えるのであれば、以下の方法がある。 しかし以下パターン1は、要素名がname,ageという共通な部分があるようにみえるが、 プログラム上は、PersonとPersonStudent1は、まるっきり関係のない別の型にすぎない。

このため、元データと共通部分があっても、同じ処理を改めて書き直しになる。(プログラマーの手間が減らせない)

// 元のデータに追加要素(パターン1)
struct PersonStudent1 {
   // Personと同じ部分
   char name[ 20 ] ; // 名前
   int  age ;        // 年齢

   // 追加部分
   char dep[ 20 ] ;  // 所属
   int  grade ;      // 学年
} ;
void set_PersonStudent1( struct PersonStudent1* p ,
                         char s[] , int x ,
                         char d[] , int g ) {
   // set_Personと同じ処理を書いている。
   strcpy( p->name , s ) ;
   p->age = x ;

   // 追加された処理
   strcpy( p->dep , d ) ;
   p->grade = g ;
}

// 名前と年齢 / 所属と学年を表示
void print_PersonStudent1( struct PersonStudent1* p ) {
   // print_Personと同じ処理を書いている。
   printf( "%s %d\n" , p->name , p->age ) ;
   printf( "- %s %d¥n" , p->dep , p->grade ) ;
}

int main() {
   struct PersonStudent1 yama1 ;
   set_PersonStudent1( &yama1 ,
                       "yama" , 22 , "PS" , 2 ) ;
   print_PersonStudent1( &yama1 ) ;
   return 0 ;
}

パターン2(元データの処理を少し使って…)

パターン1では、機能が追加された新しいデータ構造のために、同じような処理を改めて書くことになりプログラムの記述量を減らせない。面倒なので、 元データ用の関数をうまく使うように書いてみる。

// 元のデータに追加要素(パターン2)
struct PersonStudent2 {
   // 元のデータPerson
   struct Person person ;

   // 追加部分
   char          dep[ 20 ] ;
   int           grade ;
} ;

void set_PersonStudent2( struct PersonStudent2* p ,
                         char s[] , int x ,
                         char d[] , int g ) {
   // Personの関数を部分的に使う
   set_Person( &(p->person) , s , x ) ;

   // 追加分はしかたない
   strcpy( p->dep , d ) ;
   p->grade = g ;
}

void print_PersonStudent2( struct PersonStudent2* p ) {
   // Personの関数を使う。
   print_Person( &p->person ) ;
   printf( "- %s %d¥n" , p->dep , p->grade ) ; 
}

int main() {
   struct PersonStudent2 yama2 ;
   set_PersonStudent2( &yama2 ,
                       "yama" , 22 , "PS" , 2 ) ;
   print_PersonStudent2( &yama2 ) ;
   return 0 ;
}

このパターン2であれば、元データ Person の処理をうまく使っているので、 プログラムの記述量を減らすことはできるようになった。

しかし、print_PersonStudent2() のような処理は、名前と年齢だけ表示すればいいという場合、元データ構造が同じなのに、 PersonStudent2 用のプログラムをいちいち記述するのは面倒ではないか?

そこで、元データの処理を拡張し、処理の流用ができないであろうか?

基底クラスから派生クラスを作る

オブジェクト指向では、元データ(基底クラス)に新たな要素を加えたクラス(派生クラス)を 作ることを「派生」と呼ぶ。派生クラスを定義するときは、クラス名の後ろに、 「:」,「public/protected/private」, 基底クラス名を書く。

// 基底クラス
class Person {
private:
   char name[ 20 ] ;
   int  age ;
public:
   Person( const char s[] , int x )
     : age( x ) {
      strcpy( name , s ) ;
   }
   void print() {
      printf( "%s %d\n" , name , age ) ;
   }
} ;
// 派生クラス(Student は Person から派生)
class Student : public Person {
private:
   // 追加部分
   char dep[ 20 ] ;
   int  grade ;
public:
   Student( const char s[] , int x ,
            const char d[] , int g )
     : Person( s , x ) // 基底クラスのコンストラクタ
   {  // 追加された処理
      strcpy( dep , d ) ;
      grade = g ;
   }
} ;

int main() {
   Person saitoh( "t-saitoh" , 50 ) ;
   saitoh.print() ;
   Student yama( "yama" , 22 , "PS" , 2 ) ;
   yama.print() ;  // "yama 22"が表示される
   return 0 ;
}

ここで注目すべき点は、main()の中で、Studentクラス”yama”に対し、yama.print() を呼び出しているが、パターン2であれば、print_PersonStudent2()に相当するプログラムを 記述していない。 しかし、この派生を使うと Person の print() が自動的に流用することができる。 これは、基底クラスのメソッドを「継承」しているから、 このように書け、名前と年齢「yama 22」が表示される。

さらに、Student の中に、以下のような Student 専用の新しい print()を記述してもよい。

class Student ...略... {
   ...略...

   // Student クラス専用の print() 
   void print() {
      // 親クラス Person の print() を呼び出す
      Person::print() ;
      // Student クラス用の処理
      printf( "%s %d\n" , dep , grade ) ;
   }
} ;
void main() {
   ...略...
   Student yama( "yama" , 22 , "PS" , 2 ) ;
   yama.print() ;
}

この場合は、継承ではなく機能が上書き(オーバーライト)されるので、 「yama 22 / PS 2」が表示される。

派生クラスを作る際の後ろに記述した、public は、他にも protected , private を 記述できる。

public    だれもがアクセス可能。
protected であれば、派生クラスからアクセスが可能。
          派生クラスであれば、通常は protected で使うのが一般的。
private   派生クラスでもアクセス不可。

C言語で無理やりオブジェクト指向の”派生”を使う方法

オブジェクト指向の機能の無いC言語で、このような派生と継承を実装する場合には、共用体を使う以下のようなテクニックが使われていた。
unix の GUI である X11 でも共用体を用いて派生を実装していた。

// 基底クラス
struct PersonBase {     // 基底クラス
   char name[ 20 ] ;
   int  age ;
} ;

struct PersonStudent {  // 派生クラス
   struct PersonBase base ;
   char dep[ 20 ] ;
   int  grade ;
} ;
                                   //(base) //(student)
union Person {                     // name  //[name]
   struct PersonBase    base ;     // age   //[age ]
   struct PersonStudent student ;           // dep
} ;                                         // grade

void person_Print( struct Person* p ) {
   printf( "%s %d\n" , p->base.name , p->base.age ) ;   
}

int main() {
   struct PersonBase    tsaitoh = { "tsaitoh" , 55 } ;
   struct PersonStudent mitsuki = { { "mitsuki" , 21 } , "KIT" , 4 } ;
   print_Person( (struct Person*)&tsaitoh ) ;
   print_Person( (struct Person*)&mitsuki ) ;  // 無理やり print_Person を呼び出す
   return 0 ;
}

仮想関数への伏線

上記のような派生したプログラムを記述した場合、以下のようなプログラムでは何が起こるであろうか?

class Student ... {
   :
   void print() {
      Person::print() ;                    // 名前と年齢を表示
      printf( " %s %d¥n" , dep , grade ) ; // 所属と学年を表示
   }
} ;
int main() {
   Person saitoh( "t-saitoh" , 55 ) ;
   saitoh.print() ;                // t-saitoh 55 名前と年齢を表示

   Student mitsu( "mitsuki" , 20 , "KIT" ,  3 ) ;
   Student ayuka( "ayuka" ,   18 , "EI" ,   4 ) ;
   mitsu.print() ;                 // mitsuki 20 / KIT 3  名前,年齢,所属,学年を表示
   ayuka.print() ;                 // ayuka 18   / EI  4  名前,年齢,所属,学年を表示

   Person* family[] = {
      &saitoh , &mitsu , &ayuka ,  // 配列の中に、Personへのポインタと
   } ;                             // Studentへのポインタが混在している
                                   // 派生クラスのポインタは、
                                   // 基底クラスのポインタとしても扱える
   for( int i = 0 ; i < 3 ; i++ )
      family[ i ]->print() ;       // t-saitoh 55/mitsuki 20/ayuka 18
   return 0 ;                      // が表示される。 
}                                  // # "mitsuki 20/KIT 3" とか "ayuka 18/EI 4"
                                   // # が表示されてほしい?

Javaのオブジェクト指向の基礎

前期中間前レポート課題(選択2)

4年の情報構造論で、リスト構造などの内容を進める前に、3年プログラミング応用でクラスなどに自信がない人向けの簡単レクチャ。

クラスは、データ構造と手続き

例えば、名前と年齢のデータをクラスで扱うのであれば、以下のようなコードが基本となるだろう。

import java.util.*;

class NameAge {
    String name ;          // インスタンス変数
    int    age ;           // インスタンス変数
    static int count = 0 ; // クラス変数
    // コンストラクタ
    NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

実行結果
tsaitoh,59
member = 1
age = 59
tomoko,48
member = 2

クラスとは、データ構造(オブジェクト)とそのデータ構造を扱うための関数(メソッド)をまとめて扱う。

クラス NameAge の中で宣言されている、NameAge() の関数は、オブジェクトを初期化するための関数(メソッド)であり、特にコンストラクタと呼ばれる。

実際にデータを保存するための tsaitoh や tomoko とよばれる変数に NameAge オブジェクトの実体(インスタンス)を作る時には 「new クラス名」 とやることで、初期化ができる。

イメージでは、下図のようなデータ構造ができあがる。

でも、年齢の覚え方は、将来的に誕生日を覚えるように変化するかもしれない。この際に、Main 関数の中で age を使うと後で混乱の元になるかもしれない。こういう時は、NameAge クラス以外では中身を勝手に使わせないために、インスタンス変数などに public / private といったアクセス制限を加える。

import java.util.*;
class NameAge {
    private String name ;          // インスタンス変数
    private int    age ;           // インスタンス変数
    public  static int count = 0 ; // クラス変数
    // コンストラクタ
    public  NameAge( String s , int a ) {
        this.name = s ;
        this.age  = a ;
        count++ ;
    }
    // メソッド
    public void print() {
        System.out.println( this.name + "," + this.age ) ;
        System.out.println( "member = " + count ) ;
    }
} ;

public class Main {
    public static void main(String[] args) throws Exception {
        NameAge tsaitoh = new NameAge( "tsaitoh" , 59 ) ;
        tsaitoh.print() ;
        System.out.println( "age = " + tsaitoh.age ) ;
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ここがエラーになる。NameAge::age は private 
        NameAge tomoko  = new NameAge( "tomoko" ,  48 ) ;
        tomoko.print() ;
    }
}

クラス自体も、public class NameAge … のように宣言することもあるが、public なクラスは 1つ の *.java ファイルの中に1つしか書けないというルールがあるので要注意。

練習問題

科目(Subject)と学生(Student)の情報があり、科目を受講した成績(Result)で成績を管理している。
このデータを管理するためのクラスを宣言し、下に示すようなデータSubject,Result,Studentの配列を作り、下に示したような出力が得られるプログラムを作成せよ。

科目: Subject
id    name      teacher    // Subject[] subject_table = {
10010 情報構造論 t-saitoh   //    new Subject( 10010 , "情報構造論" , "t-saitoh" ) ,
10020 電気磁気学 takaku     //    new Subject( ....
10030 電気回路   komatsu    // } ;

成績: Result
s_id  id         point      // Result[] result_table = {
58563 10020      83         //    new Result( 16213 , 10020 , 83 ) ,
58564 10010      95         //    new Result( ...
58573 10030      64         // } ;
58563 10010      89

学生: Student
s_id  name      age        // Student[] student_table = {
58563 斉藤太郎   18          //    new Student( 16213 , "斉藤太郎" , 18 ) ,
58564 山田次郎   19          //    new Student( ...
58573 渡辺花子   18          // } ;

以下のようなデータが出力されること
斉藤太郎 電気磁気学 83
渡辺花子 情報構造論 95
山田次郎 電気回路   64
斉藤太郎 情報構造論 89

処理速度を計測

前期中間前レポート課題(選択1)

例年であれば、プログラム作成中心のレポート課題をやってもらっているけど、前期中間試験は今回早めに行われるので、プログラム作成か、処理速度のオーダを実際に計測実験のいずれかとする。

現在時間を ミリ秒の精度で求める System.currentTimeMills() を使って、様々なプログラムの処理時間を計測してみよう。ただし、OS によって 100ミリ秒未満はあまり正確に測れない。このため、処理時間は繰り返し処理などを入れることで、10秒程度になるようにすること。また、動作例で示した Paiza.io では、長い処理時間のプログラムは、途中で強制終了させられるので、自分のパソコンにインストールしてある環境で動作させること。また、並列処理しているプログラムの影響を受ける可能性もあることから、他の処理の影響がでないように工夫すること。

様々なプログラムの実行時間を計測してみよう

import java.util.*;

public class Main {
    // 乱数を配列にセット
    public static void array_set_random( int[] array ) {
        Random rnd = new Random() ;
        for( int i = 0 ; i < array.length ; i++ )
            array[ i ] = rnd.nextInt( array.length ) ;
    }
    // 配列を選択法でソート
    public static void array_sort( int[] array ) {
        for( int i = 0 ; i < array.length - 1 ; i++ ) {
            int min = i , j ;
            for( j = i + 1 ; j < array.length ; j++ ) {
                if ( array[ min ] > array[ j ] )
                    min = j ;
            }
            int tmp = array[ i ] ;
            array[ i ] = array[ min ] ;
            array[ min ] = tmp ;
        }
    }
    public static void main(String[] args) throws Exception {
        // 変化させるデータ件数
        int[] data_n = {
            2500 ,
            5000 ,
            7500 ,
            10000
        } ;
        for( int i = 0 ; i < data_n.length ; i++ ) {
            int[] array = new int[ data_n[ i ] ] ;
            // 配列を乱数で埋める時間は測りたくない
            array_set_random( array ) ;
            long start = System.currentTimeMillis() ;
            array_sort( array ) ;
            // ソート結果の表示時間は測りたくない
            //for( int x = 0 ; x < array.length ; x++ )
            //    System.out.print( array[ x ] + " " ) ;
            //System.out.println() ;
            long end   = System.currentTimeMillis() ;
            System.out.println( "Time = " + (end - start) ) ;
        }
    }
}

プログラムによっては、処理時間が短すぎる場合があるので、下記のように 1000 回ループさせるなどで、一定時間以上の処理となるように工夫すること。

public static int fact( int x ) {
    if ( x == 1 )
        return 1 ;
    else
        return x * fact( x - 1 ) ;
}
public static void main(String[] args) throws Exception {
    int[] data_n = { 2 , 4 , 6 , 8 , 10 } ;
    for( int i = 0 ; i < data_n.length ; i++ ) {
        long start = System.currentTimeMillis() ;
        for( int j = 0 ; j < 1000 ; j++ ) {
            int ans = fact( data_n[ i ] ) ;
        }
        long end = System.currentTimeMillis() ;
        System.out.println( "Time = " + ( end - start ) ) ;
    }
}

レポート内容

データ件数や 引数に与える数によって、処理時間が変化するプログラムを記述し、そのプログラムを N を変化させながら上記のプログラムなどを参考に処理時間を計測する。時間計測には誤差が大きく含まれる可能性があることから、複数回実行して平均をとるなどの工夫もすること。

授業中に示したプログラムなどの計測を行う場合は、ループのプログラムの変化と、別プログラムの再帰の場合の変化の2つについて結果を示すこと。創造工学演習の再帰問題の課題の整数比の直角三角形探索、辺の組み合わせ問題、N Queen、ハノイの塔など、自分で興味のあるテーマを選んだ場合は1つでも良い。

この上で、(1) プログラムリスト, (2) 時間計測にあたり工夫したこと, (3) 実際の実行結果のグラフ, (4) その結果の考察した結果をレポートにまとめて提出せよ。

コンピュータとN進数

3年の情報制御基礎の授業の一回目。この授業では、情報系以外の学生も受講することから、基礎的な共通的な話題を中心に説明を行う。

情報制御基礎のシラバス

情報制御基礎では、ここに上げたシラバス(2025)に沿って授業を行う。

基本的に、センサーから読み取ったデータを使って動く制御系システムを作る場合の基礎知識ということで、アナログ量・デジタル量の話から、移動平均やデータ差分といった数値処理や、そこで求まった値を制御に用いるための基礎的な話を行う。

コンピュータと組み込み系

最近では、コンピュータといっても様々な所で使われている。

  1. 科学技術計算用の大型コンピュータ(最近なら富岳が有名)や
  2. インターネットの処理を行うサーバ群
    (必要に応じてサービスとして提供されるものはクラウドコンピューティングと呼ぶ)、
  3. デスクトップパソコン・ノートパソコン
  4. タブレットPCやスマートフォンのような端末、
  5. 電化製品の中に収まるようなワンチップコンピュータ

などがある。(3)のパソコンでもグラフィックス表示機能のために GPU(Graphics Processing Unit) を搭載したものは(ゲームでの3次元表示用)、高速計算に使われることも多い。最近では、GPU をAIの処理における神経細胞を真似するニューラルネットワークの計算に使うことも増えてきて、GPU を NPU(Neural Processing Unit)と呼ぶこともある。


(2) サーバ:ブレードサーバ

(5) ワンチップコンピュータ:PIC 12F675

身近で使われている情報制御という点では、(5)のような小型のコンピュータも多く、こういったものは組み込み型コンピュータとも呼ばれる。しかし、こういったコンピュータは、小さく機能も限られているので、

  • 組み込み系では、扱える数値が整数で 8bit や 16bit といった精度しかなかったり、
  • 実数を伴う複雑な計算をするには、処理時間がかかったりする

ため、注意が必要である。

この情報制御基礎の授業では、組み込み系のコンピュータでも数値を正しく扱うための知識や、こういった小さいコンピュータで制御を行うことを踏まえたプログラミングの基礎となる知識を中心に説明を行う。


2進数と10進数

コンピュータの中では、電圧が高い/低いといった状態で0と1の2通りの状態を表し、その 0/1 を組み合わせて、大きな数字を表す(2進数)。

練習として、2進数を10進数で表したり、10進数を2進数に直してみよう。

N進数を10進数に変換

N進数で “abcde” があったとする。(2進数で”10101)2“とか、10進数で”12345)10“とか)

この値は、以下のような式で表せる。

(例1)

(例2)

10進数をN進数に変換

N進数のは、前式を変形すると、以下のような式で表せることから、

値をNで割った余りを求めると、N進数の最下位桁eを取り出せる。

このため、10進数で与えられた35を2進数に変換するのであれば、35を2で次々と割った余りを、下の桁から書きならべれば2進数100011)2が得られる。

実数の場合

途中に小数点を含むN進数のab.cde)Nであれば、以下の値を意味する。

ここで、小数点以下だけを取り出した、0.cde)Nを考えると、

の値に、Nをかけると、次のように変形できる。

この式を見ると、小数部にNをかけると、整数部分に小数点以下1桁目が取り出せる

このため、10進数で与えられた、0.625を2進数に変換するのであれば、0.625に次々と2をかけて、その整数部を上の桁から書きならべれば、2進数0.101)2が得られる。

ただし、10進数で0.1という値で、上記の計算を行うと、延々と繰り返しが発生する。つまり、無限小数になるので注意せよ。

2の補数と負の数

コンピュータの中で引き算を行う場合には、2の補数がよく使われる。2の補数とは、2進数の0と1を入替えた結果(1の補数)に、1を加えた数である。

元の数に2の補数を加えると(2進数が8bitの数であれば)、どのような数でも1,0000,0000という値になる。この先頭の9bit目が必ずはみ出し、この値を覚えないのであれば、元の数+2の補数=0とみなすことができる。このことから、2の補数= (-元の数) であり、負の数を扱うのに都合が良い。

練習問題

(1) 自分の誕生日で、整数部を誕生日の日、小数点以下を誕生日の月とした値について、2進数に変換せよ。(例えば、2月7日の場合は、”7.02″という小数点を含む10進数とする。)

変換の際には、上の説明の中にあるような計算手順を示すこと。また、その2進数を10進数に直し、元の値と同じか確認すること。(ただし、結果の2進数が無限小数になる場合最大7桁まで求めれば良い。同じ値か確認する際には無限少数の場合は近い値になるか確認すること)

(2) 自分の誕生日の日と、自分の学籍番号の下2桁の値を加えた値について、8bitの2進数で表わせ。(2月7日生まれの出席番号13番なら7+13=21)

その後、8bitの2進数として、2の補数を求めよ。また、元の数と2の補数を加えた値についても検証すること。

レポートの提出先は、こちらのリンクを参照(この中にレポート書式のひな型を置いてあります)

クイックソートと選択ソート

データ数 N = 10 件でソート処理の時間を計測したら、選択ソートで 10msec 、クイックソートで 20msec であった。

  1. データ件数 N= 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
    • TS(10)=Ts x 100 = 10msec よって Ts = 0.1msec
      • 0.1msec * 100 * 100 = 1000 msec
    • TQ(10)=Tq x 10 x log10 10 = 20msec よって Tq=2msec
      • 2msec * 100 * log10 100 = 400 msec
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

設問2 は、通常の関数電卓では求まらないので、数値的に方程式を解く機能を持った電卓が必要。

上記の計算時間は、計算しやすい値を例に示したが、一般的なプロセッサであれば、10件~30件程度で選択ソートとクイックソートの処理時間が入れ替わる。

これらを踏まえ、ライブラリとして使われるクイックソートプログラムでは、データ件数が20件ほど未満になったら、ソート方法を選択ソートに切り替えるように作られている。

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー