ホーム » 2022 » 5月 (ページ 2)

月別アーカイブ: 5月 2022

2022年5月
1234567
891011121314
15161718192021
22232425262728
293031  

検索・リンク

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@演習サーバ

ファイル操作の基本

まずは基本操作をしてみよう。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- rwx 所有者が 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 が見ると、以下のようなファイルであった。

$ 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 コマンドで使用状況が確認できる。一般的に、主記憶メモリの数倍を割り当てる。

フローチャートと整数型

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

フローチャートの基本

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

処理の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の補数表現では最上位ビットが符号を表すために使われる。

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 ;                  // (例) 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のこちらの共有フォルダに、回答記入用のひな型がおいてあるので、この書式を参考に各自レポートにまとめ、同フォルダに提出してください。

派生と継承

隠ぺい化の次のステップとして、派生・継承を説明する。オブジェクト指向プログラミングでは、一番基本となるデータ構造を宣言し、その基本構造に様々な機能を追加した派生クラスを記述することでプログラムを作成する。今回は、その派生を理解するために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"
                                   // # が表示されてほしい?

lexのそれ以外のアクション

flex+bisonを使った関数電卓を作る専攻科の実験で、空白処理の質問が出た。

こちらのような mycalc.l だと、空白の場合の処理とか、それ以外の文字が入力された時の処理は記述していない。

lex の出力する C 言語のソースをざらっと読むと、正規表現で指定しないパターンに対しては、そのまま文字を出力する処理( ECHO という入力文字をそのまま出力する #define マクロ)が生成される。だから、例で示したプログラムだと、式として”1+ab2″ を入力すると”ab>>3″と出力される。

%%
文字1 アクション1  # このような処理を書くと、雑な説明でいうなら、以下のような処理が作られる
文字2 アクション2
%%
switch( 入力文字 ) {
case '文字1' :
   アクション1 ;
   break ;
case '文字2' :
   アクション2 ;
   break ;
default :
   ECHO ;  // 入力文字をそのまま出力するマクロ
   break ;
}

このため空白を読み捨てる、それ以外の文字が入力されたら字句解析段階でのエラーを出力するのであれば、lex の正規表現の処理の部分に以下のようなものを追加する必要がある。

[ ¥t] ;   /* 空白やタブ文字の時は何もしない */

.     {   /* それ以外の文字は、エラーメッセージとエラーとなった文字を出力して中断 */
          /* 正規表現の . は、任意の1文字という意味 */
          printf("lex:error ") ; ECHO ; exit( 1 ) ;
      }

再帰呼び出しと再帰方程式

前回の授業では、簡単な再帰呼び出しのプログラムについて再帰方程式などの説明を行った。今日の授業では、ハノイの塔の処理時間や、マージソートのプログラムの処理時間について検討を行う。

ハノイの塔

ハノイの塔は、3本の塔にN枚のディスクを積み、(1)1回の移動ではディスクを1枚しか動かせない、(2)ディスクの上により大きいディスクを積まない…という条件で、山積みのディスクを目的の山に移動させるパズル。

一般解の予想

ハノイの塔の移動回数を とした場合、 少ない枚数での回数の考察から、 以下の一般式で表せることが予想できる。

 … ①

この予想が常に正しいことを証明するために、ハノイの塔の処理を、 最も下のディスク1枚への操作と、その上の(N-1)枚のディスクへの操作に分けて考える。

再帰方程式

上記右の図より、N枚の移動をするためには、上に重なるN-1枚を移動させる必要があるので、

 … ②
 … ③

ということが言える。(これがハノイの塔の移動回数の再帰方程式)
ディスクが枚の時、予想が正しいのは明らか①,②。
ディスクが 枚で、予想が正しいと仮定すると、 枚では、

 … ③より
 … ①を代入

となり、 枚でも、予想が正しいことが証明された。 よって数学的帰納法により、1枚以上で予想が常に成り立つことが証明できた。

理解度確認

  • 前再帰の「ピラミッドの体積」pyra() を、ループにより計算するプログラムを記述せよ。
  • 前講義での2分探索法のプログラムを、再帰によって記述せよ。(以下のプログラムを参考に)。また、このプログラムの処理時間にふさわしい再帰方程式を示せ。
int a[ 10 ] = {
   7 , 12 , 22 , 34 , 41 , 56 , 62 , 78 , 81 , 98
} ;
int find( int array[] , int L , int R , int key ) { // 末尾再帰
   // 目的のデータが見つかったら 1,見つからなかったら 0 を返す。
   if ( __________ ) {
      return ____ ; // 見つからなかった
   } else {
      int M = _________ ;
      if ( array[ M ] == key )
         return ____ ;
      else if ( array[ M ] > key )
         return find( array , ___ , ___ , key ) ;
      else
         return find( _____ , ___ , ___ , ___ ) ;
   }
}
int main() {
   if ( find( a , 0 , 10 , 56 ) )
      printf( "みつけた¥n" ) ;
}

再帰を使ったソートアルゴリズムの分析

データを並び替える有名なアルゴリズムの処理時間のオーダは、以下の様になる。

この中で、高速なソートアルゴリズムは、クイックソート(最速のアルゴリズム)とマージソート(オーダでは同程度だが若干効率が悪い)であるが、ここでは、再帰方程式で処理時間をイメージしやすい、マージソートにて説明を行う。

マージソートの分析


マージソートは、与えられたデータを2分割し、 その2つの山をそれぞれマージソートを行う。 この結果の2つの山の頂上から、大きい方を取り出す…という処理を繰り返すことで、 ソートを行う。

このことから、再帰方程式は、以下のようになる。

  • Tm(1)=Ta

この再帰方程式を、N=1,2,4,8…と代入を繰り返していくと、 最終的に処理時間のオーダが となる。






よって、処理時間のオーダは  となる。

選択法とクイックソートの処理時間の比較

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

  1. データ件数 = 100 件では、選択法,クイックソートは、それぞれどの程度の時間がかかるか答えよ。
  2. データ件数何件以上なら、クイックソートの方が高速になるか答えよ。

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

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

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

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

複素数クラスによる演習

複素数クラスの例

隠蔽化と基本的なオブジェクト指向の練習課題として、前回の授業では、直交座標系による複素数クラスを示した。今回の授業では、演習を行うとともに直交座標系を極座標系にクラス内部を変更したことにより、隠蔽化の効果について考えてもらい、第1回レポートとする。

直交座標系

前回の授業で示した直交座標系のクラス。比較対象とするために再掲。

#include <stdio.h>
#include <math.h>

// 直交座標系の複素数クラス
class Complex {
private:
   double re ; // 実部
   double im ; // 虚部
public:
   void print() {
      printf( "%lf + j%lf¥n" , re , im ) ;
   }
   Complex( double r , double i ) // 実部虚部のコンストラクタ
     : re( r ) , im( i ) {}
   Complex()                      // デフォルトコンストラクタ
     : re( 0.0 ) , im( 0.0 ) {} 
   void add( Complex z ) {
      // 加算は、直交座標系だと極めてシンプル
      re = re + z.re ;
      im = im + z.im ;
   }
   void mul( Complex z ) {
      // 乗算は、直交座標系だと、ちょっと煩雑
      double r = re * z.re - im * z.im ;
      double i = re * z.im + im * z.re ;
      re = r ;
      im = i ;
   }
   double get_re() {
      return re ;
   }
   double get_im() {
      return im ;
   }
   double get_abs() { // 絶対値
      return sqrt( re*re + im*im ) ;
   }
   double get_arg() { // 偏角
      return atan2( im , re ) ;
   }
} ; // ←何度も繰り返すけど、ここのセミコロン忘れないでね
int main() {
   // 複素数を作る
   Complex a( 1.0 , 2.0 ) ;
   Complex b( 2.0 , 3.0 ) ;

   // 複素数の計算
   a.print() ;
   a.add( b ) ;
   a.print() ;
   a.mul( b ) ;
   a.print() ;

   return 0 ;
}

極座標系

上記の直交座標系の Complex クラスは、加減算の関数は単純だけど、乗除算の関数を書く時には面倒になってくる。この場合、極座標系でプログラムを書いたほうが判りやすいかもしれない。

// 局座標系の複素数クラス
class Complex {
private:
   double r ;  // 絶対値 r
   double th ; // 偏角   θ
public:
   void print() {
      printf( "%lf ∠ %lf¥n" , r , th / 3.14159265 * 180.0 ) ;
   }
   Complex() // デフォルトコンストラクタ
     : r( 0.0 ) , th( 0.0 ) {}

   // 表面的には、同じ使い方ができるように
   //  直交座標系でのコンストラクタ
   Complex( double x , double y ) {
      r  = sqrt( x*x + y*y ) ;
      th = atan2( y , x ) ;    // 象限を考慮したatan()
   }
   // 極座標系だと、わかりやすい処理
   void mul( Complex z ) {
      // 極座標系での乗算は
      r = r * z.r ;    // 絶対値の積
      th = th + z.th ; // 偏角の和
   } 
   // 反対に、加算は面倒な処理になってしまう。
   void add( Complex z ) {
      ; // 自分で考えて
   }
   // ゲッターメソッド
   double get_abs() {
      return r ;
   }
   double get_arg() {
      return th ;
   }
   double get_re() {  // 直交座標系との互換性のためのゲッターメソッド
      return r * cos( th ) ;
   }
   double get_im() {
      return r * sin( th ) ;
   }
} ; // ←しつこく繰り返すけど、セミコロン忘れないでね(^_^;

このように、プログラムを開発していると、当初は直交座標系でプログラムを記述していたが、途中で極座標系の方がプログラムが書きやすいという局面となるかもしれない。しかし、オブジェクト指向による隠蔽化を正しく行っていれば、利用者に影響なく「データ構造」や「その手続き(メソッド)」を書換えることも可能となる。

このように、プログラムをさらに良いものとなるべく書換えることは、オブジェクト指向ではリファクタリングと呼ぶ。
正しくクラスを作っていれば、クラス利用者への影響が最小にしながらリファクタリングが可能となる。

const 指定 (経験者向け解説)

C++ では、間違って値を書き換えるような処理を書けないようにするための、const 指定の機能がある。

void bar( char* s ) {       // void bar( const char* s ) {...}
   printf( "%s\n" , s ) ;   //  で宣言すべき。
}

void foo( const int x ) {
   //     ~~~~~~~~~~~
   x++ ; // 定数を書き換えることはできない。
   printf( "%d\n" , x ) ;
}
int main() {
   const double pi = 3.141592 ;
   // C言語で #define PI 3.141592 と同等

   bar( "This is a pen" ) ; // Warning: string constant to 'char*' の警告
   int a = 123 ;
   foo( a ) ;

   return 0 ;
}

前述の、getter メソッドの例では要素を参照するだけで、オブジェクトの中身が変化しない。逆に言えば、getter のメソッド内にはオブジェクトに副作用のある処理を書いてはいけない。こういった用途に、オブジェクトを変化させないメソッド宣言がある。先の、get_re() は、

class ... {
   :
   inline double get_re() const {
               //         ~~~~~
      re = 0 ; // 文法エラー
      return re ;
   }
} ;

クラスオブジェクトを引数にする場合

前述の add() メソッドでは、”void add( Complex z ) { … }” にて宣言をしていた。しかし、引数となる変数 z の実体が巨大な場合、この書き方では値渡しになるため、データの複製の処理時間が問題となる場合がある。この場合は、(書き方1)のように、z の参照渡しにすることで、データ複製の時間を軽減する。また、この例では、引数 z の中身を間違って add() の中で変化させる処理を書いてしまうかもしれない。そこで、この事例では(書き方2)のように const 指定もすべきである。

// (書き方1)
class Complex {
   :
   void add( Complex& z ) {
      re += z.re ;
      im += z.im ;
   }
} ;
// (書き方2)
class Complex {
   :
   void add( const Complex& z )
   {  //     ~~~~~~~~~~~~~~~~
      re += z.re ;
      im += z.im ;
   }
} ;

レポート1(複素数の加減乗除)

授業中に示した、直交座標系・極座標系の複素数のプログラムをベースに、記載されていない減算・除算のプログラムを作成し、レポートを作成する。 レポートには、下記のものを記載すること。

  • プログラムリスト
  • プログラムへの説明
  • 動作確認の結果
  • プログラムより理解できること。
  • 実際にプログラムを書いてみて分かった問題点など…

システム

最新の投稿(電子情報)

アーカイブ

カテゴリー