リスト処理
リスト構造
リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。
まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、１つ１つのデータをポインタでつなげる処理を示す。
#include <stdio.h>
#include <stdlib.h>
// List構造の宣言
struct List {
int data ; // データ保存部
struct List* next ; // 次のデータへのポインタ
} ;
int main() {
struct List* top ; // データの先頭
struct List* p ;
// (1)
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 111 ;
// (2)
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 222 ;
// (3)
top->next->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->next->data = 333 ;
top->next->next->next = NULL ; // 末尾データの目印
for( p = top ; p != NULL ; p = p->next ) {
printf( "%d¥n" , p->data ) ;
}
return 0 ;
}
このようなメモリーの中のポインタの指し示す番地のイメージを、具体的な番地の数字を書いてみると、以下のような図で表せる。先頭の111が入った部分が1000番地であったなら、topというポインタには1000番地が入っている。
NULLって何？
前回の授業で説明した、次の配列の添え字の番号を使う方式では、データの末尾を示すためには、-1 を使った。-1 は、配列の添え字で通常ありえない値であり、次のデータはないという目印とした。
同じように、C言語では、通常あり得ないポインタとして、0 番地を示す NULL が定義されている。NULLポインタの先を参照してはいけない。このリスト処理では、末尾を表す目印として使っている。
#define NULL 0
補助関数
上記のプログラムでは、(struct…)malloc(sizeof(…))を何度も記載し、プログラムが分かりにくいので、以下に示す補助関数を使うと、シンプルに記載できる。
struct List* cons( int x , struct List* n ) {
struct List* ans ;
ans = (struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
int main() {
struct List* top ;
top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ;
:
return 0 ; // Listの開放free()は省略
}
補助関数の名前の cons は、constructor の略であり、古くから使われている List Processor(LISP)※ というプログラム言語でのリスト(セル)を生成する関数が cons 。
typedefを使った書き方
List構造の宣言は、古い書き方では typedef を使うことも多い。typedef は、型宣言において新しい型の名前をつける命令。
// typedef の使い方 // typedef 型宣言 型名 ; typedef unsigned int uint32 ; // 符号なし32bit整数をシンプルに書きたい uint32 x = 12345 ; typedef struct LIST { // 構造体のタグ名と新しくつける型名と重複できない int data ; // のでこの時点のタグ名は "LIST" としておく struct LIST* next ; } List ; List* cons( int x , List* n ) { // C++なら struct List { ... } ; と書く List* ans ; // だけでこういう表記が可能 ans = (List*)malloc( sizeof( List ) ) ; : ((略)) } int main() { List* top ; top = cons( 111 , cons( 222 , cons( 333 , NULL ) ) ) ; : ((略)) }最近のC言語(C++)では、構造体のタグ名がそのまま型名として使えるので、こういう書き方をする必要はなくなってきている。
// 最近のC++なら... struct List { public: int data ; List* next ; public: List( int x , List* n ) : data( x ) , next( n ) {} } ; int main() { List* top = new List( 111 , new List( 222 , new List( 333 , NULL ) ) ) ; : // Listの開放deleteは省略 }LISP※と関数型プログラミング言語
LISPの歴史は長く、最古のFORTRAN,COBOLに次ぐ3番目ぐらいに遡る。最初は、人工知能※※(AI)のプログラム開発のための関数型プログラミング言語として作られた。特徴として、データもプログラムもすべてリスト構造(S式)で表すことができ、プログラムは関数型に基づいて作られる。
関数型プログラミングは、Ruby や Python でも取り入れられている。関数型プログラミングは、処理を関数をベースに記述することで「副作用を最小限にすることができ」、極端な話をすればループも再帰呼出しの関数で書けばいい…。
LISPの処理系は、最近では Scheme などが普通だが、プログラムエディタの Emacs は、内部処理が LISP で記述されている。
古いAI※※と最近のAIの違い
最近では、AI(Artificial Intelligence) という言葉が復活してきたが、LISP が開発された頃の AI と最近注目されている AI は、微妙に異なる点がある。
LISPが開発された頃の AI は、関数型のプログラム言語で論理的思考を表現することが目標であった。頭脳を左脳と右脳の違いで表現することが多いが、どちらかというとLISPの時代のAI「分析的で論理的に優れ、言語力や計算機能が高い」とされる左脳を作り出すことを目指していた。しかしながら、この時代では、漠然としたパターンを認識したりするような「感覚的、直感的な能力に優れ総合判断力を司る右脳」のような処理は苦手であった。
しかしながら、最近注目されている AI は、脳神経を真似たニューラルネットワークから発展した機械学習やディープラーニングという技法により今まで難しかった右脳の機能を実現することで、最近のAIでは左脳と右脳の機能を兼ね備えたものとなっている。
将棋のプログラミングで例えるなら、左脳(古いAI)に例えられるのが正確に先の手を読む機能であり、右脳に例えられる機能が大局観(全体の良し悪しを見極める判断能力)といえる。
簡単なリスト処理の例
先に示したリスト構造について簡単なプログラム作成を通して、プログラミングに慣れてみよう。
// 全要素を表示する関数
void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d " , p->data ) ;
printf( "¥n" ) ;
}
// データ数を返す関数
int count( struct List* p ) {
int c = 0 ;
for( ; p != NULL ; p = p->next )
c++ ;
return c ;
}
int main() {
struct List* top = cons( 111 , cons( 444 , cons( 333 , NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , count( top ) ) ;
return 0 ;
}
リスト処理を自分で考えて作成
以下のようなプログラムを作ってみよう。意味がわかって慣れてくれば、配列の部分の for の回し方が変わっただけということに慣れてくるだろう。
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの平均値を返す
double mean( struct List* p ) {
// (111+444+333)/3=296.0
自分で考えよう
}
// リストの中から指定した値の場所を返す
int find( struct List* p , int key ) {
// find( top , 444 ) = 1 (先頭0番目)
// 見つからなかったら -1
自分で考えよう
}
再帰呼び出しでリスト処理
リスト処理の応用のプログラムを作るなかで、2分木などのプログラミングでは、リスト処理で再帰呼出しを使うことも多いので、先に示したプログラムを再帰呼び出しで書いたらどうなるであろうか？
// 全データを表示
void print( struct List* p ) {
if ( p == NULL ) {
printf( "¥n" ) ;
} else {
printf( "%d " , p->data ) ;
print( p->next ) ; // 末尾再帰
}
}
// データ数を返す関数
int count( struct List* p ) {
if ( p == NULL )
return 0 ;
else
return 1 + count( p->next ) ; // 末尾再帰
}
// 全要素の合計
int sum( struct List* p ) {
// sum( top ) → 888
自分で考えよう
}
// リストの最大値を返す
int max( struct List* p ) {
// max( top ) → 444 (データ件数0の場合0を返す)
自分で考えよう
}
// リストの中から指定した値を探す。
int find( struct List* p , int key ) {
// find( top , 444 ) = 1
// 見つかったら1 , 見つからなかったら 0
自分で考えよう
}
理解度確認
上記プログラム中の sum() , max() , find() を再帰呼び出しをつかって記述せよ。
リダイレクト・パイプ
Linuxを使う上で、キーボードでコマンドを入力しているが、こういうコマンドの管理を行うプログラムを shell と呼ぶ。shell には、色々なものがある(sh, csh, bash, zsh)が、広く使われている bash( born-again shell )について説明する。最初に、コマンドの入出力を組み合わせるために重要となるリダイレクトとパイプについて説明し、次にコマンドなどの処理単位となるジョブやプロセスの考え方について説明を行う。
標準入出力とリダイレクト
出力リダイレクト
C言語のプログラミングで、プログラムの実行結果をレポートに張り付ける時はどのように行っているだろうか？多くの人は、実行画面を PrintScreen でキャプチャした画像を張り付けているかもしれない。しかし、数十行にわたる結果であれば何度もキャプチャが必要となる。
そこで、今日の最初はリダイレクト機能について説明する。
“gcc ファイル.c” は、C言語のプログラムをコンパイルし、a.out という実行ファイルを生成する。”./a.out” にてプログラムを実行する。実行する命令に、“> ファイル名” と書くと、通常の出力画面(標準出力) をファイル名に記録してくれる。これを出力リダイレクトと呼ぶ。また、“>> ファイル名” と書くと、既存ファイルの後ろに追記してくれる。
guest00@nitfcei:~$ cat helloworld.c
#include <stdio.h>
int main() {
printf( "Hello World\n" ) ;
return 0 ;
}
guest00@nitfcei:~$ gcc helloworld.c
guest00@nitfcei:~$ ./a.out
Hello World
guest00@nitfcei:~$ ./a.out > helloworld.txt
guest00@nitfcei:~$ cat helloworld.txt
Hello World
guest00@nitfcei:~$ ./a.out >> helloworld.txt
guest00@nitfcei:~$ cat helloworld.txt
Hello World
Hello World
入力リダイレクト
次に、1行に名前と3教科の点数が書いてある複数行に渡るデータの各人の平均点を求めるプログラムを考える。
guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-each-low.c .
guest00@nitfcei:~$ cat avg-each-low.c
#include <stdio.h>
// ((input)) ((output))
// saitoh 43 54 82 saitoh 59.67
// tomoko 89 100 32 tomoko 73.67
// mitsuki 79 68 93 mitsuki 80.00
int main() {
char name[ 100 ] ;
int point[ 3 ] ;
while( scanf( "%s%d%d%d" ,
name , &point[0] , &point[1] , &point[2] ) == 4 ) {
double sum = 0.0 ;
for( int i = 0 ; i < 3 ; i++ )
sum += point[i] ;
printf( "%s %6.2f\n" , name , sum / 3.0 ) ;
}
return 0 ;
}
guest00@nitfcei:~$ gcc avg-each-low.c
guest00@nitfcei:~$ ./a.out
saitoh 43 54 82 入力
saitoh 59.67 出力
tomoko 89 100 32 入力
tomoko 73.67 出力
^D ← Ctrl-D を押すとファイル入力を終了
しかし、プログラムの書き方を間違えてプログラムを修正していると、動作確認のたびに何度も同じデータを入力するかもしれないが、面倒ではないだろうか？
プログラムを実行する時に、“< ファイル名” をつけると、通常はキーボードから入力する所を、ファイルからの入力に切り替えて実行することができる。このようなscanf()を使う時のようなプログラムの入力を標準入力といい、それをファイルに切り替えることを入力リダイレクトと呼ぶ。
guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/name-point3.txt . guest00@nitfcei:~$ cat name-point3.txt saitoh 43 54 82 tomoko 89 100 32 mitsuki 79 68 93 guest00@nitfcei:~$ ./a.out < name-point3.txt saitoh 59.67 tomoko 73.67 mitsuki 80.00
この入力リダイレクトと出力リダイレクトを合わせて使うこともできる。
guest00@nitfcei:~$ ./a.out < name-point3.txt > name-avg.txt guest00@nitfcei:~$ cat name-avg.txt saitoh 59.67 tomoko 73.67 mitsuki 80.00
パイプ
先の名前と3教科のプログラムの結果から、全員の平均点をも計算したい場合、どのようなプログラムを作るだろうか？C言語だけの知識なら、各人の行のデータを計算するループの中に、全員の合計と人数を求めるプログラムを書いて、最後に平均点を出力するだろう。
一方で、複数人の名前と平均点のデータから平均点を求めるプログラムを書いて、前述のプログラムの実行結果を使う人もいるだろう。
以下の例では、“gcc -o avg-each-row avg-each-row.c” で、avg-each-row という実行ファイル、“gcc -o avg-all avg-all.c” で、avg-all という実行ファイルを生成し、avg-each-row で入力リダイレクト・出力リダイレクトを使って、name-avg.txt を作り、avg-all を入力リダイレクトで、最終結果を表示している。
guest00@nitfcei:~$ cp /home0/Challenge/2.1-RedirectPipe.d/avg-all.c .
guest00@nitfcei:~$ cat avg-all.c
#include <stdio.h>
// ((input)) ((output))
// saitoh 59.67 73.11
// tomoko 73.67
// mitsuki 80.00
int main() {
char name[ 100 ] ;
double point ;
double sum = 0 ;
int count = 0 ;
while( scanf( "%s%lf" , name , &point ) == 2 ) {
sum += point ;
count++ ;
}
printf( "%6.2f\n" , sum / (double)count ) ;
return 0 ;
}
guest00@nitfcei:~$ gcc -o avg-each-low avg-each-low.c
guest00@nitfcei:~$ gcc -o avg-all avg-all.c
guest00@nitfcei:~$ ./avg-each-low < name-point3.txt > name-avg.txt
guest00@nitfcei:~$ ./avg-all < name-avg.txt
71.11
しかし、いちいち入出力の結果を name-avg.txt を作るのは面倒である。であれば、以下の様なイメージで処理をすれば答えが求まる。
name-point3.txt→(avg-each-row)→name-avg.txt→(avg-all)→結果
これは、パイプ機能を使って以下の様に動かすことができる。
guest00@nitfcei:~$ ./avg-each-low < name-point3.txt | ./avg-all 71.11 guest00@nitfcei:~$ cat name-point3.txt | ./avg-each-low | ./avg-all 71.11
プログラムを実行する時に、“A | B” ように書くと、プログラムA の標準出力結果を、プログラムB の標準入力に接続させて、2つのプログラムを実行できる。このような機能を、パイプと呼ぶ。上記例の2つめ “cat… | ./avg-each-low | ./avg-all” では3つのプログラムをパイプでつないでいる。
リダイレクトのまとめ
| 入力リダイレクト(標準入力) | 実行コマンド < 入力ファイル |
| 出力リダイレクト(標準出力) | 実行コマンド > 出力ファイル |
| 出力リダイレクト(標準出力の追記) | 実行コマンド >> 出力ファイル |
| 標準エラー出力のリダイレクト | 実行コマンド 2> 出力ファイル |
| パイプ コマンドAの標準出力をコマンドBの標準入力に接続 |
コマンドA | コマンドB |
C言語のコンパイルまとめ
| C言語のコンパイル(実行ファイルはa.out) | gcc ソースファイル |
| 実行ファイル名を指定してコンパイル | gcc -o 実行ファイル ソースファイル |
高専プロコンin群馬大会-本戦参加3チーム
4EIの創造工学演習の授業にて作成しているシステム開発にて高専プロコンin群馬に応募していましたが、下記3チームが無事書類審査を通過し、10月15日(土),16日(日)に開催される本戦に参加することとなりました。また、3EIのグループによる競技部門についても、本戦参加も決定となりました。
課題部門
- 「お神輿わっしょい – 自宅でお神輿担ぎを疑似体験 – 」4EI：出倉、越元、小見山、ヤン
- 「PaOn – 子供に身近な公園を自宅に！ – 」4EI：泉、伊藤、並河、松田、山岸、清水
自由部門
- 「妄想サイクリング – 観客を巻き込む VRフィットネスゲーム – 」4EI：戸田、中村、吹谷、武藤
表計算ソフトの使い方(絶対参照・相対参照)
今日の表計算ソフトを使った演習では、下記のサンプルファイルを練習に使うので、Teamsで参照してください。
前回課題の答え合わせ
前回のレポートでは、sin(83度)(例)といった数値の有効数字を考えるというものを考えてもらったので、この有効数字をどう記載すべきか考えてみる。
課題を示す Excel ファイルでは、75度～89度あたりの角度で出題をするようにしてあった。注意しないといけない点は、sinは90度に近づくほど、1に近づく。このため、0.99…といった数値が求まるが、角度がちょっと変化しても、0.99といった部分はほぼ変化しない。だから、83が有効数字2桁ということで、0.99 といった有効数字2桁の書き方では、ちょっと不十分かもしれない。
そこで、83度(有効数字2桁)が小数点以下を丸められた数値と仮定する。この場合、元の数値は 82.5度～83.5度 の可能性がある。これらの値のsinを計算すると、0.9914から0.9935の間であり、小数点以下3桁目は、1～3 の値であり、結果を 0.992 (有効数字3桁) と記載しても良いかもしれない。
sin(82.5°) = 0.991444861 sin(83.0°) = 0.992546152 sin(83.5°) = 0.993571856
表計算ソフトの使い方
情報制御基礎では、プログラムで計算する所を、Excel のような表計算ソフトを用いて検証してもらったりする予定なので、Excel で計算式を使う方法を説明する。
セルの場所と簡単な式
簡単な、品名・単価・個数・価格の表を考える。以下の表のように、列の名前と、品名・単価・個数まで入力した後、単価と個数をかけた価格を求めるとする。
Excel では、表の列には左から、A,B,C,D… , 表の行には上から1,2,3,4,5 と番号が振られていて、特定の列・特定の行のデータを表す時には、列行を組み合わせ、A1に品名、B3に￥80、C5に4 が入っている。
例えば、D2 に、ノート単価120円、ノート個数3個をかけた値を入れたい場合は、D2の場所に、
=B2*C2
を書き込めば、その場所には360が表示される。
先頭の”=”を入力した後、該当する”B2″の場所をクリックするなりカーソルを操作すると、カーソルのセルの場所”B2″が自動的に入力される。さらに”*”を入力した後、”C2″の場所をクリックすれば”C2″が入力される。
Excelでは、入力する文字列の先頭が”=”の場合は、残り部分は計算式として扱われる。
D3には、”=B3*C3″を入力すれば、160 が表示される。しかし、この様な式を何度も入力するのは面倒である。
この場合、セル・カーソルを、D2 に合わせ、[右ボタン]-[コピー]を行い、D3 で[右ボタン]-[貼り付けオプション]-[貼り付け]を行えば、”=B3*C3″が入力される。
ここで注意しないといけないのが、式を張り付ける場合には、貼り付け先のセルの場所が一つ下の行なので、行番号を表す2の部分が1つ下の行番号3に書き換えられて、貼り付けが行われる。(相対参照)
関数式
例えば、下左図のような、数字とその平方根の表を作る場合、A2 に 1、B2に =sqrt( A2 ) を入力、A3 に =A2+1 を入力したあと、B2の式をB3にコピー＆ペーストし、A3,B3 を A4～A6にペーストすればいい。
B2に入力したような、sqrt( A2 ) のようなものは、関数式と呼ばれる。
また、A3,B3 といった複数の行・列をまとめた範囲を示す時は、A3:B3 といった表記方法であらわす。
絶対参照と相対参照
最初の例に戻って、単価と個数の積で今度は税率を加えて計算する例を考える。また、税率は後で変化するかもしれないので、B1 のセルに税率を記入しておく場合を考える。
この場合、D3 には、” =B3*C3*(1+B1) ” を入力すればいい。
ただ、このように式を入力すると、D3 の計算式を、D4,D5,D6 にコピーすると、セル D4 には =B4*C4*(1+B2) が入力されてしまい、B2 には単価という文字が記載されているため、正しい結果が求まらない。
こういった場合には、絶対参照を用いる。D3 に記入する式を
=B3*C3*(1+$B$2)
とし、この D3 の式を D4 にコピー＆ペーストすると、列記号、行番号の前に$がついた部分の式は、貼り付け場所に応じて変化しない。
このような、$B$2 といったセルの参照は、絶対参照と呼ぶ。これに対し、B2 といったセル参照は、貼り付け場所に応じて書き換えられるので、相対参照と呼ぶ。
絶対参照と相対参照が混ざった、$B2, B$2 といった書き方もある。
式の入力時に[F4ボタン]を押す度に、B2→$B$2→B$2→$B2→B2 と変化する$B2 は、式をコピーすると列部分はBのまま、行部分は場所に合わせて変化する。
B$2 は、式をコピーすると列部分は場所に合わせて変化し、行部分は2のままとなる。
レポート課題(第5回)
Excel で、xを0〜180度まで変化させたときのsin(x),位相をyとした時のsin(x+y)の値の表を作り、グラフ機能で表示せよ。A列は角度・B列はsin(x)・C列はsin(x+y)の値とし、yの値は”C1″に保存されているものとする。
この時、計算式の入力をどのように行なったのか(相対参照や絶対参照をどのように使ったのか)説明を、グラフの下に入力欄を設け記入せよ。
なお、Excel の sin() 関数は、引数がラジアンで入力する必要があるので、計算式には注意せよ。
そして出来上がった Excel のファイルを、Teams のこちらのフォルダに提出せよ。
多重継承の問題
派生や継承について、一通りの説明が終わったので、データ構造(クラスの構造)の定義の方法にも様々な考え方があり、どのように実装すべきかの問題点を考えるための説明を行う。その中で特殊な継承の問題についても解説する。
動物・鳥類・哺乳類クラス
派生や継承を使うと、親子関係のあるデータ構造をうまく表現できることを、ここまでの授業で示してきた。
しかしながら、以下に述べるような例では、問題が発生する。
// 動物クラス
class Animal {
private:
char name[ 10 ] ;
public:
Animal( const char s[] ) {
strcpy( name , s ) ;
}
const char* get_name() const { return name ; }
virtual void move() = 0 ;
virtual void birth() = 0 ;
} ;
// 鳥類クラス
class Bird : public Animal {
public:
Bird( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s fry.\n" , get_name() ) ;
}
virtual void birth() {
printf( "%s lay egg.\n" , get_name() ) ;
}
} ;
// 哺乳類クラス
class Mammal : public Animal {
public:
Mammal( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s walk.\n" , get_name() ) ;
}
virtual void birth() {
printf( "%s lay baby.\n" , get_name() ) ;
}
} ;
int main() {
Bird chiken( "piyo" ) ;
chiken.move() ;
chiken.birth() ;
Mammal cat( "tama" ) ;
cat.move() ;
cat.birth() ;
return 0 ;
}
ここで、カモノハシを作るのであれば、どうすれば良いだろうか？
鳥類・哺乳類とは別にカモノハシを作る
class SeaBream : public Animal {
public:
Mammal( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s walk.\n" , get_name() ) ;
}
virtual void birth() {
printf( "%s lay egg.\n" , get_name() ) ;
}
} ;
この例では、簡単な処理だが、move() の中身が複雑であれば、改めて move() を宣言するのではなく、継承するだけの書き方ができないだろうか？
多重継承
C++ には、複数のクラスから、派生する多重継承という機能がある。であれば、鳥類と哺乳類から進化したのだから、以下のように書きたい。
class SeaBream : public Bird , Mammal {
//
} ;
しかし、カモノハシに move() を呼び出すと、鳥類の move() と哺乳類の move() のどちらを動かすか曖昧になる。
しかし一番の問題は、派生クラスは親クラスのデータ領域と、派生クラスのデータ領域を持つため、鳥類の name[] と、哺乳類の name[] を二つ持つことになる。
足と羽のクラスを作る場合(本来は継承で実装すべきではない)
class Animal {
private:
char name[ 10 ] ;
public:
Animal( const char s[] ) {
strcpy( name , s ) ;
}
const char* get_name() const { return name ; }
virtual void move() = 0 ;
} ;
// 羽
class Wing {
public:
const char* move_method() { return "fly" ; }
} ;
//
class Leg {
public:
const char* move_method() { return "walk" ; }
} ;
class Bird : public Animal , Wind {
public:
Bird( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s %s.\n" , get_name() , move_method() ) ;
}
} ;
class Mammal : public Animal , Leg {
public:
Mammal( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s %s.\n" , get_name() , move_method() ) ;
}
} ;
ただし、ここで述べた方式は、UML による設計の際に改めて説明を行うが、is-a , has-a の関係でいうなら、
- Bird is a Animal.
- Bird has a Wing.
であることから、Wing は 継承で実装するのではなく、集約もしくはコンポジションのような部品として実装すべきである。
C++では、以下のような方法で、ダイヤモンド型の継承問題を解決できる。
class Animal {
private:
char name[ 10 ] ;
public:
Animal( const char s[] ) {
strcpy( name , s ) ;
}
const char* get_name() const { return name ; }
virtual void move() = 0 ;
virtual void birth() = 0 ;
} ;
// 鳥類クラス
class Bird : public virtual Animal {
public:
Bird( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s fry.\n" , get_name() ) ;
}
virtual void birth() {
printf( "%s lay egg.\n" , get_name() ) ;
}
} ;
// 哺乳類クラス
class Mammal : public virtual Animal {
public:
Mammal( const char s[] ) : Animal( s ) {}
virtual void move() {
printf( "%s walk.\n" , get_name() ) ;
}
virtual void birth() {
printf( "%s lay baby.\n" , get_name() ) ;
}
} ;
class SeaBream : public virtual Bird , virtual Mammal {
public:
SeaBream( const char s[] ) : Animal( s ) {}
void move() {
Mammal::move() ;
}
void birth() {
Bird::birth() ;
}
} ;
ただし、多重継承は親クラスの情報と、メソッドを継承する。この場合、通常だと name[] を二つ持つことになるので、問題が発生する。そこで、親クラスの継承に virtual を指定することで、ダイヤモンド型継承の ２つの属性をうまく処理してくれるようになる。
しかし、多重継承は処理の曖昧さや効率の悪さもあることから、採用されていないオブジェクト指向言語も多い。特に Java は、多重継承を使えない。その代わりに interface という機能が使えるようになっている。
多重継承を使える CLOS や Python では、適用するメソッドやインスタンス変数の曖昧さについては親クラスへの優先度を明確にできる機能がある。曖昧さの問題を避けるのであればクラス限定子”::”を使うべきである。
リスト構造の導入
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造の導入の説明を行う。
配列の利点と欠点
今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。しかし、配列には苦手な処理がある。
例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。処理に要する時間としては となる。
// この関数は見つかったら、見つかった場所、見つからない場合は -1 を返す。
int find( int array[] , int left , int right , int key ) {
// データは left から right-1までに入っているとする。
while( left < right ) {
int mid = (left + right) / 2 ; // 中央の場所
if ( array[ mid ] == key )
return mid ; // 見つかった
else if ( array[ mid ] > key )
right = mid ; // 左半分にある
else
left = mid + 1 ; // 右半分にある
}
return -1 ; // 見つからない
}
int a[] = { 12 , 34 , 41 , 53 , 62 , 79 , 80 } ;
int main() {
int ans = find( a , 0 , 7 , 62 ) ; // 配列 a[] から 62 を探す
printf( "%d¥n" , ans ) ; // 4が表示される
return 0 ;
}
しかし、この配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。
void entry( int array[] , int* psize , int key ) {
// データを入れるべき場所を探す処理
for( int i = 0 ; i < *psize ; i++ ) // O(N) の処理だけど、
if ( array[ i ] > key ) // O(log N) でも書けるけど
break ; // 今回は単純に記載する。
if ( i < *psize ) {
// 要素を１つ後ろにずらす処理(A)
for( int j = *psize ; j > i ; j-- ) // O(N)の処理
array[ j ] = array[ j - 1 ] ;
array[ i ] = key ;
} else {
array[ *psize ] = key ;
}
(*psize)++ ;
}
/// よくある間違い ///
/// 上記処理の(A)の部分を以下のように記載した ///
/// 問題点はなにか答えよ ///
// for( int j = i ; j < size ; j++ )
// array[ j + 1 ] = array[ j ] ;
// array[ i ] = key ;
int main() {
int a[ 100 ] ;
int size = 0 ;
int x ;
// 入力された値を登録していく繰り返し処理
while( scanf( "%d" , &x ) == 1 ) {
// x を追加する。
entry( a , &size , x ) ;
}
return 0 ;
}
これで判るように、昇順に並んだ配列にデータを追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。
この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。
このことから、昇順に並べられた配列は、データの追加処理の発生頻度が少ない場合は2分探索法で効率が良いが、データの追加や削除が頻繁に発生する時はあまり効率が良くない。
順序が重要なデータ列で途中へのデータ挿入削除を高速化
例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
以下の説明のような方法であれば、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、スムーズに回覧板を回すことができる。
101 102 103 104 105 106 アパートの番号 [ 105 | 106 | -1 | 102 | 104 | 103 ] 回覧板を回す次の人の部屋番号 101号室の次は、105号室、 105号室の次は、104号室、 : 106号室の次は、103号室、 103号室の次は、おしまい(-1)
このように「次のデータの場所」という概念を使うと、データの順序を持って扱うことができる。これをプログラムにしてみよう。
struct LIST {
int data ; // 実際のデータ
int next ; // 次のデータの配列の添字
} ;
struct LIST array[] = {
/*0*/ { 11 , 2 } ,
/*1*/ { 67 , 3 } , // 末尾にデータ34を加える
/*2*/ { 23 , 4 } , // { 23 , 5 } ,
/*3*/ { 89 , -1 } , // 末尾データの目印
/*4*/ { 45 , 1 } ,
/*5*/ { 0 , 0 } , // { 34 , 4 } ,
} ;
int main() {
for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) {
printf( "%d¥n" , array[ idx ].data ) ;
}
return 0 ;
}
この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。(O(N)の処理が発生しない)
しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。そこで、必要に応じてメモリを確保するテクニックを導入する。
複素数クラスでre-imとr-thのコンストラクタ
複素数クラスの課題で、直交座標系のコンストラクタと曲座標系のコンストラクタを作りたいとの質問。でも、以下のようなコンストラクタでは、どちらも Complex( double , double ) であり、区別できない。
class Complex {
private:
double re , im ;
public:
Complex( double x , double y ) // コンストラクタ
: re( x ) , im( y ) {}
Complex( double r , double th )
// Complex(double,double)では直交座標系のコンストラクタと区別できない。
: re( r * cos( th ) ) , im( r * sin( th ) ) {}
// Complex( double r , double th ) { // これもダメ...
// return Complex( r * cos(th) , r * sin(th) ) ;
// }
// static は、静的メンバ関数(オブジェクトに対してのメソッドではない)
static Complex complex_rth( double r , double th ) {
return Complex( r * cos(th) , r * sin(th) ) ;
}
} ;
int main() {
Complex a( 1.0 , 1.0 ) ;
Complex b = Complex::complex_rth( 1 , 45.0/180.0*3.14 ) ;
a.print() ;
b.print() ;
return 0 ;
}
色々な書き方はあると思うけど、static Complex Complex::complex_rth( double r , double th ) ; を宣言するのが自然かな…と思ったけど、初期化が Complex a = Complex::complex_rth( 1 , 2 ) ; みたいに書くことになってちょっとダサい。”Complex::” のクラス限定子が邪魔っぽいけど、関数の名前空間を不必要に使わないという意味ではいいのかもしれないが。 C++ の complex クラスを見たら、以下のように使えるようになっていた。なるほど。
class Complex {
private:
double re , im ;
public:
Complex( double x , double y ) : re( x ) , im( y ) {}
void print() const { printf( "%lf+j%lf\n" , re , im ) ; }
} ;
// 曲座標系のコンストラクタ? (正確に言えばコンストラクタではない)
inline Complex polar( double r , double th ) {
return Complex( r * cos( th ) , r * sin( th ) ) ;
} ;
int main() {
Complex a( 1 , 2 ) ;
Complex b = polar( 3 , 30.0 / 180.0 * 3.141592 ) ;
Complex c( polar( 3 , 30.0 / 180.0 * 3.141592 ) ) ;
// こっちの書き方の方がコンストラクタを使ってるっぽく見える。
// デフォルトコピーコンストラクタが使われている。
a.print() ;
b.print() ;
c.print() ;
return 0 ;
}
様々なデータの覚え方のレポート課題
前回の malloc() + free() の資料で、様々なデータ構造の覚え方の例やメモリイメージを説明し、前期中間のレポート課題を示す。
malloc+freeの振り返り
// 文字列(可変長)の保存
char str[] = "ABCDE" ;
char* pc ;
pc = (char*)malloc( strlen( str ) + 1 ) ;
if ( pc != NULL ) { // ↑正確に書くと sizeof( char ) * (strlen(str)+1)
strcpy( pc , str ) ;
////////////////////
// pcを使った処理
////////////////////
free( pc ) ;
}
//
// 可変長の配列の保存
int data[] = { 11 , 22 , 33 } ;
int* pi ;
pi = (int*)malloc( sizeof( int ) * 3 ) ;
if ( pi != NULL ) {
for( int i = 0 ; i < 3 ; i++ )
pi[ i ] = data[ i ] ;
////////////////////
// piを使った処理
////////////////////
free( pi ) ;
}
//
// 1件の構造体の保存
struct Person {
char name[ 10 ] ;
int age ;
} ;
struct Person* pPsn ;
pPsn = (struct Person*)malloc( sizeof( struct Person ) ) ;
if ( pPsn != NULL ) {
strcpy( pPsn->name , "t-saitoh" ) ;
pPsn->age = 55 ;
////////////////////
// pPsnを使った処理
////////////////////
free( pPsn ) ;
}
安全な1行1件のデータ入力
C言語では、scanf などの関数は、バッファオーバーフローなどの危険性があるため、以下のような処理を使うことが多い。fgets は、指定されたファイルから1行分のデータを読み込む。sscanf は、文字列のなかから、scanf() と同じようなフォーマット指定でデータを読み込む。
fgets は、これ以上の入力データが無い場合には、NULL を返す。
(Windowsであれば、キー入力でCtrl+Z を入力、macOSやLinuxであれば、Ctrl+Dを入力で終了)
sscanf() は、読み込めたデータ件数を返す。
int main() {
char buff[ 1024 ] ;
for( int i = 0 ; i < 3 ; i++ ) {
if ( fgets( buff , sizeof( buff ) , stdin ) != NULL ) {
char name[ 1024 ] ;
int age ;
if ( sscanf( buff , "%s%d" , name , &age ) == 2 ) {
// 名前と年齢の２つのデータが正しく読み込めたとき
...
}
}
}
return 0 ;
}
様々なデータの覚え方
配列サイズ固定・名前が固定長
例えば、このデータ構造であれば、table1[] の場合、長い名前にある程度対応できるように nameの配列を100byteにしたりすると、データ件数が少ない場合には、メモリの無駄も多い。
そこで、実際に入力された存在するデータだけをポインタで覚える方法 table2[] という保存方法も考えられる。
// 固定長データのプログラム
#define SIZE 50
// 名前(固定長)と年齢の構造体
struct NameAge {
char name[ 32 ] ;
int age ;
} ;
struct NameAge table1[ SIZE ] ;
int size1 = 0 ;
void entry1( char s[] , int a ) {
strcpy( table1[ size1 ].name , s ) ;
table1[ size1 ].age = a ;
size1++ ;
}
// ポインタで覚える場合
struct NameAge* table2[ SIZE ] ;
int size2 = 0 ;
void entry2( char s[] , int a ) {
table2[size2] = (struct NameAge*)malloc( sizeof( struct NameAge ) ) ;
if ( table2[size2] != NULL ) { // なぜ != NULL のチェックを行うのか、説明せよ
strcpy( table2[size2]->name , s ) ;
table2[size2]->age = a ;
size2++ ;
}
}
// データ出力
void print_NA( struct NameAge* p ) {
printf( "%s %d¥n" , p->name , p->age ) ;
}
int main() {
// table1に保存
entry1( "t-saitoh" , 55 ) ;
entry1( "tomoko" , 44 ) ;
print_NA( &table1[0] ) ;
print_NA( &table1[1] ) ;
// table2に保存
entry2( "t-saitoh" , 55 ) ;
entry2( "tomoko" , 44 ) ;
print_NA( _________________ ) ; // table2の中身を表示せよ
print_NA( _________________ ) ;
return 0 ;
}
配列サイズ固定・名前が可変長
しかしながら、前回の授業で説明したように、際限なく長い名前があるのであれば、以下の様に名前は、ポインタで保存し、データを保存する時に strdup(…) を使って保存する方法もあるだろう。
// 名前が可変長のプログラム
// 名前(固定長)と年齢の構造体
struct NamePAge {
char* name ; // ポインタで保存
int age ;
} ;
struct NamePAge table3[ SIZE ] ;
int size3 = 0 ;
void entry3( char s[] , int a ) {
table3[ size3 ].name = strdup( s ) ; // ★★★★
table3[ size3 ].age = a ;
size3++ ;
}
// ポインタで覚える場合
struct NamePAge* table4[ SIZE ] ;
int size4 = 0 ;
void entry4( char s[] , int a ) {
table4[size4] = (struct NamePAge*)malloc( ____________________ ) ;
if ( table4[size4] != NULL ) { // ↑適切に穴埋めせよ
table4[size4]->name = strdup( s ) ; // ★★★★
_________________________________ ; // ←適切に穴埋めせよ
size4++ ;
}
}
// データ出力
void print_NPA( struct NameAge* p ) {
printf( "%s %d¥n" , ____________ , ____________ ) ;
} // ↑適切に穴埋めせよ
int main() {
// table3に保存
entry3( "t-saitoh" , 55 ) ;
entry3( "jyugemu jyugemu ..." , 44 ) ;
print_NPA( _________________ ) ; // table3[] の中身を表示せよ。
print_NPA( _________________ ) ;
// table4に保存
entry4( "t-saitoh" , 55 ) ;
entry4( "jyugemu jyugemu ..." , 44 ) ;
print_NPA( table4[0] ) ;
print_NPA( table4[1] ) ;
return 0 ;
}
データ件数が可変長ならば
前述のプログラムでは、データ件数全体は、SIZE という固定サイズを想定していた。しかしながら、データ件数自体も数十件かもしれないし、数万件かもしれないのなら、配列のサイズを可変長にする必要がある。
struct NamePAge* table5 ;
int size5 = 0 ;
void entry5( char s[] , int a ) {
strcpy( table5[ size5 ].name , s ) ;
table5[ size5 ].age = a ;
size5++ ;
}
int main() {
// table5に保存
table5 = (struct NameAge*)malloc( sizeof( struct NameAge ) * 2 ) ;
if ( table5 != NULL ) {
entry5( "t-saitoh" , 55 ) ;
entry5( "tomoko" , 44 ) ;
}
return 0 ;
}
メモリの管理に十分気を付ける必要があるが、名前の長さも配列全体のサイズも可変長であれば、以下のようなイメージ図のデータを作る必要があるだろう。(JavaScriptやJavaといった言語ではデータのほとんどがこういったポインタで管理されている)
レポート課題
授業での malloc , free を使ったプログラミングを踏まえ、以下のレポートを作成せよ。
以下のデータのどれか1つについて、データを入力し、何らかの処理を行うこと。
課題は、原則として、(自分の出席番号%3)+1 についてチャレンジすること。
- 名前と電話番号
- 名前と身長・体重
- 名前と生年月日
このプログラムを作成するにあたり、以下のことを考慮しmallocを適切に使うこと。
名前は、長い名前の人が混ざっているかもしれない。
保存するデータ件数は、10件かもしれない1000件かもしれない。(データ件数は、処理の最初に入力すること。)
ただし、mallocの理解に自信がない場合は、名前もしくはデータ件数のどちらか一方は固定値でも良い。
レポートには、(a)プログラムリスト, (b)プログラムの説明, (c)正しく動いたことがわかる実行例, (d)考察 を記載すること。
考察には、自分のプログラムが正しく動かない事例はどういう状況でなぜ動かないのか…などを検討したり、プログラムで良くなった点はどういう所かを説明すること。
ネットワークとセキュリティ
ネットワークからの攻撃とFireWall
脆弱性とバッファオーバーフロー
プログラムには、何らかのバグが潜んでいる可能性があり、悪用すると悪意のプログラムの実行や、情報の漏えい、システム異常を発生させサービスができなくするなどの脆弱性があって、悪意のある利用者から攻撃をうける可能性がある。
例えば、下記のようなC言語のプログラムは、配列をはみ出るようなデータを与えることで、関数の戻り番地を破壊させ、はみ出た部分に送り込んだ悪意のプログラムを実行させることが可能となる。このような入力用のデータ領域(バッファ)をはみ出させる攻撃はバッファオーバーフローと呼ばれる。
ルータとFireWall
外部にサービスを提供するようなシステムで、何らかの脆弱性のあるプログラムが使われていると、外部からのネットワーク接続で悪意のあるプログラム(マルウェア)を実行させられてしまうかもしれない。
このため、コンピュータでは不必要なプログラム(ネットワークサービス)は、起動されないようにする必要がある。もしくは、そのサービスは外部から利用できないように、途中のルータで FireWall(防火壁) を設置する。
FireWall では、(1)攻撃の可能性のあるIPアドレスからの接続を拒否、(2)外部に公開していないネットワークサービスのポート番号の接続を拒否といった方法をとる(拒否リスト方式)。もっと厳しい対策であれば、(3)特定のIPアドレスの機器からのみ接続を許可、(4)許可されているネットワークサービスのポート番号だけからだけ許可する方式をとる(許可リスト方式)
外部に公開する必要のないサービスがFireWallなどで正しく保護されていないと、攻撃をうける可能性がある。
ネットワーク接続のための装置
ルータやFireWallなどの仕組みをもう少し理解するために、組織内でネットワークを接続するための機器とその機能について改めて確認する。
ルータとは
元々の有線LANでは、1本のケーブルを時分割多重で共有しながら通信を行う。このため、瞬間的にはとある機器がネットワークを使用している時は、他の機器はデータ通信ができなくなる。この1本の線を大量の機器で使おうとすると、機器が使えるタイミングは減ってしまう。そこで、1本の線に直接接続する機器を分割したサブネットに分けて、必要な時だけ隣接するサブネットにパケットを中継するルータ or ブリッジが重要となる。
ルータは、隣接するサブネットのネットワーク番号(IPアドレスとサブネットマスク)を確認し、パケットを流す先を決定する。このネットワーク番号(IPアドレスとサブネットマスクの論理積)と中継を依頼するゲートウェイ(転送先)の一覧をルーティングテーブルと呼ぶ。
組織内のルータであれば、ネットワークの構造に合わせてあらかじめルーティングテーブルを定義しておく(静的ルーティング)。組織と組織を接続するようなルータは、自分に送ってほしいネットワーク番号の情報を相互に交換している(動的ルーティング)。
ブリッジとHUB
スイッチングHUB
機器を接続するための古いHUB(ダムHUB)では、通信中は他の機器の通信ができず効率が悪い。最近のHUBでは、通信する相手に応じて、内部のネットワークケーブルをスイッチのように接続・分離することができるスイッチングHUBを用いる。通信相手の識別には、一般的にMACアドレスが用いられる。(レイヤ2でのスイッチングHUB)
家庭用のスイッチングHUBは、特に細かい設定などは不要で管理機能が無いものは、アン マネージド スイッチングHUBと呼ばれる。
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スイッチと呼ぶ。
インターネットと接続するルータの機能
ネットワーク通信のIPアドレスとポート番号
クライアントの機器と通信相手との通信では、通信相手のIPアドレスとポート番号を指定してパケットを送出するが、処理結果を送信元に送り返すために、送信元のIPアドレスとポート番号が付加されている。送信元ではポート番号は、通信でよく使われる0～1023までのポート番号(ウェルノウンポート)以外で、1024～65535のポート番号(エフェメラルポート)の中から使われていないものをランダムに選んで使う。
送信相手に届いたパケットの返信データには、送信元と送信相手のIPアドレスとポート番号を入れ替えたものを割り当てることで、送信元にパケットが戻ってくる。
- DIP = 送信先IPアドレス、DP = 送信先ポート番号
- SIP = 送信元IPアドレス、SP = 送信元ポート番号
NAT(Network Address Translation)
現在広く使われているIPv4アドレス(32bit)では、40億台の機器間の通信しかできない。このため、組織内だけで使われるIPアドレス(プライベートIPアドレス)を使い、インターネットではグローバルIPアドレスを使う。
プライベートIPアドレス クラスA/8 10.0.0.0～10.255.255.255 大規模組織向け クラスB/12 172.16.0.0～172.31.255.255 中規模組織向け クラスC/16 192.168.0.0～192.168.255.255 家庭用ルータ向け
組織内のLANからインターネット(WAN)に接続する際には、プライベートアドレスをグローバルアドレスに変換するNAT(Network Address Translation)の機能が使われる。
NATの問題点
しかし、インターネットの内側で異なる機器で同じポート番号が割り振られると、戻ってきたパケットをどちらの機器に送ればいいのか区別できなくなる。
NAPT(Netowrk Address and Port Translation)
そこで、最近のNATでは、IPアドレスの変換だけでなくポート番号の付け替えも行われる。この機能は正式には NAPT(Network Address and Port Translation) と呼ぶが、単に NAT と呼ぶことも多い。Linuxでは、NAPTの実装をIPマスカレードと呼ぶ。
FireWall と DMZ
組織内で外部に公開しているサーバがある場合は、以下の図のような構成にするかもしれない。しかし、このようなネットワーク構成では、FireWallの内側の公開サーバが攻撃されて、踏み台となった場合、組織内のPCが簡単に攻撃をうけてしまう。
そこで、外部からの接続を行う DMZ(De-Militarized Zone 非武装地帯) を設け、外部公開用の公開サーバは DMZ 内に設置する。外部とつながる FireWall では、外部からのパケットは DMZ に流れるように構成する。DMZ 内のサーバが踏み台になった場合を想定し、組織内のルータでは DMZ のサーバと組織内PCは通信できないように FireWall を2重に設置する。
実数の取り扱いと誤差
実数型(float / double)
実数型は、単精度実数(float型)と、倍精度実数(double型)があり、それぞれ32bit,64bitでデータを扱う。
指数表現は、大きい値や小さい値を表現する場合に使われ、物理などで1.2345×10-4といった、仮数×基数指数で表現する方法。数学や物理では基数に10を用いるが、コンピュータの世界では基数を2とすることが多い。
単精度型(float)では、符号1bit,指数部8bit,仮数部23bitで値を覚え、数値としては、以下の値を意味する。(精度が低いので普通のコンピュータではあまり使われることはない)
符号✕ 1.仮数部 ✕ 2(指数数部-127)
符号部は、正の値なら0, 負の値なら1 を用いる。
仮数部が23bitなので、有効桁(正しい桁の幅)は約7桁となる。
例えば、float型で扱える最大数は、以下のようになる。
0,1111,1111,111,1111,1111,1111,1111,1111 = 1.1111…×2128 ≒ 2129 ≒ 1038
倍精度型(double)では、符号1bit,指数部11bit,仮数部52bitで値を覚え、数値としては、以下の意味を持つ。
符号✕ 1.仮数部 ✕ 2(指数部-1023)
これらの実数で計算を行うときには、0.00000001011×210といった値の時に、仮数部に0が並んだ状態を覚えると、計算の精度が低くなるので、1.01100000000×22のように指数部の値を調整して小数点の位置を補正しながら行われる。
double型の場合、52bit=10進数16桁相当の有効桁、最大数で、1.1111…×21024≒10308
倍精度型を使えば、正しく計算できるようになるかもしれないが、実数型はただの加算でも仮数部の小数点の位置を合わせたりする処理が必要で、浮動小数点専用の計算機能を持っていないような、ワンチップコンピュータでは整数型にくらべると10倍以上遅い場合もある。
実数の注意点
C言語でプログラムを作成していて、簡単な数値計算のプログラムでも動かないと悩んだことはないだろうか？解らなくて友達のプログラムを真似したら動いたけど、なぜ自分のプログラムは動かなかったのか深く考えたことはあるだろうか？
単純な合計と平均
整数を入力し、最後に合計と平均を出力するプログラムを以下に示す。
しかし、C言語でこのプログラムを動かすと、10,10,20,-1 と入力すると、合計(sum)40,件数(cnt)3で、平均は13と表示され、13.33333 とはならない。
小数点以下も正しく表示するには、どうすればいいだろうか？
ただし、変数の型宣言を “double data,sum,cnt ;” に変更しないものとする。
// 入力値の合計と平均を求める。
#include <stdio.h>
int main() {
int data ;
int sum = 0 ;
int cnt = 0 ;
for(;;) {
printf( "数字を入力せよ。-1で終了¥n" ) ;
scanf( "%d" , &data ) ;
if ( data < 0 )
break ;
cnt = cnt + 1 ;
sum = sum + data ;
}
printf( "合計 %d¥n" , sum ) ;
printf( "平均 %d¥n" , sum / cnt ) ;
}
C言語では、int型のsum / int型のcnt の計算は、int 型で計算を行う(小数点以下は切り捨てられる)。このため、割り算だけ実数で行いたい場合は、以下のように書かないといけない。
printf( "平均 %lf¥n" , (double)sum / (double)cnt ) ;
// (double)式 は、sum を一時的に実数型にするための型キャスト
まずは動く例
以下のプログラムは、見れば判るけど、th を 0度〜360度まで5度刻みで変化させながら、y = sin(th) の値を表示するプログラム。
// sin の値を出力
#include <stdio.h>
#include <math.h>
int main() {
double th , y ;
for( th = 0.0 ; th <= 360.0 ; th += 5.0 ) {
y = sin( th / 180.0 * 3.1415926535 ) ;
printf( "%lf %lf¥n" , th , y ) ;
}
return 0 ;
}
動かないプログラム
では、以下のプログラムはどうだろうか？
// case-1 ---- プログラムが止まらない
#define PI 3.1415926535
int main() {
double th , y ;
// 0〜πまで100分割でsinを求める
for( th = 0.0 ; th != PI ; th += PI / 100.0 ) {
y = sin( th ) ;
printf( "%lf %lf¥n" , th , y ) ;
}
return 0 ;
}
// case-2 ---- y の値が全てゼロ
int main() {
int th ;
double y ;
for( th = 0 ; th <= 360 ; th += 5 ) {
y = sin( th / 180 * 3.1415926535 ) ;
printf( "%d %lf¥n" , th , y ) ;
}
return 0 ;
}
どちらも、何気なく読んでいると、動かない理由が判らないと思う。そして、元のプログラムと見比べながら、case-1 では、「!=」を「<=」に書き換えたり、case-2 では、「int th ;」を「double th ;」に書き換えたら動き出す。
では何が悪かったのか…
回答編
数値と誤差
コンピュータで計算すると、計算結果はすべて正しいと勘違いをしている人も多い。ここで、改めて誤差について考える。特に、計器で測定した値であれば、測定値自体に誤差が含まれている。
こういった誤差が含まれる数字を扱う場合注意が必要である。例えば実験値を手書きで記録する場合、12.3 と 12.300 では意味が異なる。測定値であやふやな桁を丸めたのであれば、前者は 12.2500〜12.3499… の間の値であり有効数字3桁である。後者は、12.2995〜12.300499… の間の値であり、有効数字5桁である。このため、誤差が含まれる数字の加算・減算・乗算・除算では注意が必要である。
加減乗除算の場合
加減算であれば小数点の位置を揃え、誤差が含まれる桁は有効桁に含めてはいけない。
上記の計算では、0.4567の0.0567の部分は意味がないデータとなる。(情報落ち)
乗除算であれば、有効桁の少ない値と有効桁の多い値の計算では、有効桁の少ない方の誤差の影響が計算結果に出てくるため、通常は、有効桁5桁と2桁の計算であれば、乗除算結果は少ない2桁で書くべきである。
桁落ち
有効桁が大きい結果でも、減算が含まれる場合は注意が必要である。
例えば、以下のような計算では、有効桁7桁どうしでも、計算結果の有効桁は3桁となる。
このような現象は、桁落ちと呼ばれる。
演習問題(4回目)
こちらのフォルダに示す、Excel の表で、有効桁を考えてもらうための演習問題(ランダムに値が作られます)を有効数字を考えながら計算し、答えをレポートにまとめてください。例を以下に示す。
