ホーム » スタッフ (ページ 35)
「スタッフ」カテゴリーアーカイブ
シェルスクリプト
前回の授業では、OSでのリダイレクト・パイプの概念とプロセスの概念について説明を行ってきた。これによりプログラムの実行結果を他のプログラムに渡すことができる。これらの機能を使うと、いくつかのプログラムを次々と実行させるなどの自動化をしたくなってくる。そこで、今回の授業では、OSとプログラムの間の情報を伝え合う基本機能の説明や、プログラムの起動をスクリプトとしてプログラム化するためのシェルスクリプト(shell script)について説明する。
環境変数
OSを利用していると、その利用者に応じた設定などを行いたい場合が多い。このような情報を管理する場合には、環境変数が使われる。環境変数はプロセス毎に管理され、プロセスが新しく子供のプロセス(子プロセス)を生成すると、環境変数は子プロセスに自動的に引き渡される。代表的な環境変数を以下に示す。
- HOME – ユーザがログインした際の起点となるディレクトリであり、/home/ユーザ名 となっているのが一般的。
シェルの中では”~” で代用できる。( “cd ~” で、最初のディレクトリに戻る ) - LC_ALL, LANG – ユーザが使う言語。OSからのメッセージなどを日本語で表示したい場合には、ja_JP.UTF-8 などを指定。
- TZ – ユーザの時差の情報(Time Zone) 日本であれば、”JST-9″ を設定するのが一般的。
日本標準時 “JST” で、グリニッジ標準時(GMT)との時差を表す “-9” の組み合わせ。 - PATH – ユーザがよく使うコマンドの保存されているディレクトリの一覧。/bin:/usr/bin の様にディレクトリ名を”:”区切りで書き並べる。
- LD_LIBRARY_PATH – 共有ライブラリの保存されているディレクトリの一覧。
環境変数と同じように、シェルの中で使われるものはシェル変数と呼ぶ。この変数は、子プロセスに引き渡されない。
環境変数を表示するには、env コマンド(環境変数を表示)や、set コマンド(環境変数やシェル変数を表示)を用いる。シェルの中で特定の環境変数を参照する場合には、$変数名 とする。echo コマンドで PATH を表示するなら、”echo $PATH” とすればいい。
guest00@nitfcei:~$ env SHELL=/bin/bash : guest00@nitfcei:~$ echo $PATH /bin:/usr/bin:/usr/local/bin
変数に値を設定する場合には、“変数名=値” の様に設定する。この変数を環境変数にするには、export コマンドを用いるか、“export 変数名=値” を用いる。
((( 環境変数の設定 ))) guest00@nitfcei:~$ PATH=/bin:/usr/bin guest00@nitfcei:~$ echo $PATH guest00@nitfcei:~$ export PATH guest00@nitfcei:~$ export PATH=/bin:/usr/bin:/usr/local/bin ((( PATHの確認 ))) guest00@nitfcei:~$ which zsh # which はコマンドの場所を探してくれる /bin/zsh guest00@nitfcei:~$ export PATH=/usr/local/bin:/usr/bin:/bin guest00@nitfcei:~$ which zsh /usr/bin/zsh ((( LC_ALL,LANG の確認 ))) guest00@nitfcei:~$ export LC_ALL=C guest00@nitfcei:~$ man man (英語でマニュアルが表示される) guest00@nitfcei:~$ export LC_ALL=ja_JP.UTF-8 guest00@nitfcei:~$ man man (日本語でマニュアルが表示される) ((( TZタイムゾーンの確認 ))) guest00@nitfcei:~$ export TZ=GMT-0 guest00@nitfcei:~$ date 2022年 7月 4日 月曜日 05:23:23 GMT # イギリスの時間(GMT=グリニッジ標準時間)が表示された guest00@nitfcei:~$ export TZ=JST-9 guest00@nitfcei:~$ date # 日本時間(JST=日本標準時間)で表示された 2022年 7月 4日 月曜日 14:23:32 JST guest00@nitfcei:~$ TZ=GMT-0 date ; date # 環境変数を一時的に変更して date を実行 2022年 7月 4日 月曜日 05:23:23 GMT 2022年 7月 4日 月曜日 14:23:32 JST
プログラムとコマンドライン引数と環境変数
この後に説明するシェルスクリプトなどの機能を用いる場合は、自分のプログラムとのデータのやり取りにコマンドライン引数と環境変数を使う。また、プログラムの実行に失敗した時に別の処理を実行するためには、main関数の返り値を使うことができる。
コマンドライン引数
コマンドライン引数は、プログラムを起動する時の引数として書かれている情報であり、C言語でこの情報を用いる時には、main関数の引数”int main( int argc , char** argv ) …” により値をもらうことができ、以下のようなプログラムを記述することで受け取ることができる。
((( argv.c ))) #include <stdio.h> int main( int argc , char** argv ) { for( int i = 0 ; i < argc ; i++ ) { printf( "argv[%d] = %s\n" , i , argv[ i ] ) ; } return 0 ; } ((( argv.c を実行してみる ))) guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argv.c . guest00@nitfcei:~$ gcc argv.c guest00@nitfcei:~$ ./a.out 111 aaa 234 bcdef argv[0] = ./a.out argv[1] = 111 argv[2] = aaa argv[3] = 234 argv[4] = bcdef
注意点:コマンドライン引数の0番目には、プロセスを起動した時のプロセス名が入る。
環境変数の参照
C言語のmain関数は、コマンドライン引数のほかに環境変数も参照することができる。envpの情報は、getenv関数でも参照できる。
((( argvenvp.c ))) #include <stdio.h> int main( int argc , char** argv , char** envp ) { // コマンドライン引数argc,argvの処理 for( int i = 0 ; i < argc ; i++ ) { printf( "argv[%d] = %s\n" , i , argv[ i ] ) ; } // 環境変数envpの処理 for( int i = 0 ; envp[i] != NULL ; i++ ) { printf( "envp[%d] = %s\n" , i , envp[ i ] ) ; } return 0 ; } ((( argvenvp.c を実行してみる ))) guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/argvenvp.c . guest00@nitfcei:~$ gcc argvenvp.c guest00@nitfcei:~$ ./a.out argv[0] = ./a.out envp[0] = SHELL=/bin/bash :
プロセスの返す値
プログラムによっては、処理が上手くいかなかったことを検知して、別の処理を実行したいかもしれない。
こういう場合には、C言語であれば main の返り値に 0 以外の値で return させる。( exit関数を使ってもいい )
以下の例では、入力値の平均を出力するが、データ件数が0件であれば平均値を出力できない。こういう時に、”return 1 ;” のように値を返せば、シェル変数 $? (直前のコマンドの返り値) に return で返された値を参照できる。
((( average.c ))) #include <stdio.h> int main() { int count = 0 ; int sum = 0 ; char buff[ 1024 ] ; while( fgets( buff , sizeof( buff ) , stdin ) != NULL ) { int value ; if ( sscanf( buff , "%d" , &value ) == 1 ) { sum += value ; count++ ; } } if ( count == 0 ) { // データ件数が0の場合は平均が計算できない。 fprintf( stderr , "No data\n" ) ; // プログラムが失敗したことを返すには 0 以外の値を return する。 return 1 ; // exit( 1 ) ; } else { printf( "%lf\n" , (double)sum / (double)count ) ; } return 0 ; } ((( average.c を動かしてみる ))) guest00@nitfcei:~$ gcc average.c guest00@nitfcei:~$ ./a.out 12 14 ^D # Ctrl-D で入力を終わらせる 13.00000 guest00@nitfcei:~$ echo $? # プロセスの実行結果の値を参照するためのシェル変数 $? 0 guest00@nitfcei:~$ ./a.out ^D # データを入力せずにすぐに終了させる。 No data guest00@nitfcei:~$ echo $? 1
シェルスクリプト
今まで、コマンドラインで命令の入力をしてきたが、こういったキーボードと対話的処理を行うプログラムは shell (シェル) と呼ばれ、今回の演習では、/bin/bash を用いている。 shell は、キーボードとの対話的処理だけでなく、shell で入力するような処理をファイルに記録しておき、そのファイルに記載されている順に処理を実行することができる。
guest00@nitfcei:~$ cp /home0/Challenge/3-shellscript/helloworld.sh . guest00@nitfcei:~$ cat helloworld.sh #!/bin/bash echo "Hello World" message="こんにちは" # シェル変数への代入 echo "Hello World = $message" # シェル変数の参照 guest00@nitfcei:~$ bash helloworld.sh # bash で helloworld.sh を実行する Hello World Hello World = こんにちは
シェルスクリプトの基本は、キー入力で実行するようなコマンドを書き並べればいい。
しかし、プログラムを実行する度に、bash ファイル名 と入力するのは面倒。こういう時には以下の2つの設定を行う。
- シェルスクリプトの先頭行に 実行させる shell の名前の前に “#!” をつける。
この行は、通称”シバン shebang (シェバン)“と呼ばれ、bashで実行させたいのなら”#!/bin/bash“、プログラミング言語 Perl で実行させたいのなら “#!/usr/bin/perl” とか、Python で実行させたいのなら、”#!/usr/bin/python” のようにすればいい。(今回のサンプルはすでに記入済み) - 保存したスクリプトに対して、実行権限を与える。
“ls -al “で “rw-r–r–” のようなファイルの書き込みパーミッションが表示されるが、通常ファイルの場合は、“x”の表示があると、プログラムとして実行可能となる。(フォルダであれば、rwxr-xr-x のように”x”の表示があると、フォルダの中に入ることができる)
((( 実効権限の設定 ))) guest00@nitfcei:~$ chmod 755 helloworld.sh guest00@nitfcei:~$ ./helloworld.sh Hello World Hello World = こんにちは
$HOME/.bashrc
シェルスクリプトは、Linux の環境設定を行うためのプログラム言語として使われている。
例えば、ユーザがログインする際には、そのユーザがどういった言語を使うのか(LC_LANG,LANG)や、どういったプログラムをよく使うのか(PATH,LD_LIBRARY_PATH)などは、そのユーザの好みの設定を行いたい。こういう時に、shell に bash を使っているのであれば、$HOME/.bashrc に、shell を使う際の自分好みの設定を記載すればいい。
((( $HOME/.bashrc の例 ))) #!/bin/bash # PATHの設定 export PATH=/usr/local/bin:/usr/bin:/bin # MacOS でインストールされているソフトで PATH を切り替える if [ -d /opt/homebrew/bin ]; then # /opt/homebrew/bin のディレクトリがあるならば... # HomeBrew export PATH=/opt/homebrew/bin:$PATH elif [ -d /opt/local/bin ]; then # /opt/local/bin のディレクトリがあるならば... # MacPorts export PATH="/opt/local/bin:$PATH" fi
ユーザ固有の設定以外にも、OSが起動する時に、起動しておくべきプログラムの初期化作業などにもシェルスクリプトが使われている。
例えば、/etc/init.d/ フォルダには、Webサーバ(apache2)やsshサーバ(ssh) といったサーバを起動や停止をするための処理が、シェルスクリプトで記載してあり、OS 起動時に必要に応じてこれらのシェルスクリプトを使ってサーバソフトを起動する。(ただし最近は systemd が使われるようになってきた)
理解度確認小テスト
D/A・A/D変換回路と誤差
小型コンピュータを使った制御では、外部回路に指定した電圧を出力(D/A変換)したり、外部の電圧を入力(A/D変換)したりすることが多い。以下にその為の回路と動作について説明する。
D/A変換回路
ラダー抵抗回路によるD/A変換の仕組みを引用
このような回路で、D0,D1,D2 は、デジタル値の0=0[V] , 1=5[V] であった場合、Output 部分の電圧は、(D0,D1,D2)の値が、(0,0,0),(0,0,1),…(1,1,1)と変化するにつれ、5/8[V]づつ増え、(1,1,1)で 5*(7/8)=4.4[V]に近づいていく。最後に、Output が出力によって電圧が変化しないように、アンプ回路を通す。
DCモータをアナログ量で制御しないこと
このように、電圧をコンピュータから制御するようになると、ロボットで模型用の直流モータの回転速度をこれで制御したい…と考えるかもしれない。
しかし、直流モータは、ブラシとコイル(電磁石)を組み合わせたものだが、モーターが回転しだす瞬間でみれば、コイルは単なる導線である。このため、小さい電流でゆっくりモータを回転させようとすると、たとえ小さい電圧でも導線(抵抗はほぼ0[Ω])には大量の電流が流れ、モータをスイッチングする回路は焼き切れるかもしれない。
PWM変調
こういう場合には、PWM変調(Pulse Width Modulation) を行う。電圧の高さは一定で、高速回転させるときは長時間電圧をONにするが、低速回転させるときはONとOFFを繰り返し信号でONの時間を短くする。
このような波形であれば、低速度でも電流が流れる時間が短く、大量の電流消費は避けられ、モーターをまわす力も安定する。
A/D変換回路
D/A変換とは逆に、アナログ量をデジタル値に変換するには、どのようにするか?
このような場合には、A/D変換回路を用いる。一般的な回路では、以下のような逐次比較型A/D変換を用いる。
この回路では、変換開始と共に入力値をサンプル保持回路でアナログ量を保存する。
その後、Registerの中のデジタル値を、D/A 変換回路でアナログ量に変換した結果を、比較器(Comparator)でどちらが大きいか判断し、その結果に応じて2分探索法とかハイアンドローの方式のように、比較を繰り返しながらデジタル値を入力値に近づけていく。
ハイアンドロー(数あてゲーム)
数あてゲームで、デタラメな0〜127までの整数を決めて、ヒントを元にその数字を当てる。回答者は、数字を伝えると、決めた数よりHighかLowのヒントをもらえる。
最も速い回答方法は…例えば決めた数が55だとすると
・初期状態 ??????? 0..127 ・64 - Low 0?????? 0..63 ・32 - High 01????? 32..63 ・48 - High 011???? 48..63 ・56 - Low 0110??? 48..55 ・52 - High 01101?? 52..55 ・54 - High 011011? 54..55 ・55 - Bingo 0110111 55確定どんな値でも、7回(27=127)までで当てることができる。
量子化と量子化誤差
アナログデータ(連続量)をデジタルデータなどの離散的な値で近似的に表すことを、量子化という。
量子化誤差とは、信号をアナログからデジタルに変換する際に生じる誤差のことをいう。
アナログ信号からデジタル信号への変換を行う際、誤差は避けられない。アナログ信号は連続的で無限の正確さを伴うが、デジタル信号の正確さは量子化の解像度やアナログ-デジタル変換回路のビット数に依存する。
偶然誤差
アナログ信号がA/D変換回路に入るまでに、アナログ部品の電気的変動(ノイズ)が原因で値が変動することもある。ノイズが時間的に不規則に発生し、値が増えてしまったり減ってしまったり偶然に発生するものは偶然誤差という。偶然誤差を加えると相殺されてほぼ0になるのであれば、統計的な手法で誤差の影響を減らすことができる。
なぜデジタル信号を使うのか
コンピュータが信号処理でなぜ使われるのか?例えば、下の信号のように、電圧の低い/高いで0/1を表現したとする。
ノイズが混入しづらい
このデータ”01011100″を通信相手に送る場合、通信の途中でノイズ(図中の赤)のような信号が加わった場合、アナログ信号では、どれがノイズなのか判別することはできない。しかしデジタル信号であれば、真ん中青線より上/下か?で判別すれば、小さいノイズの影響は無視して、元どおりの”01011100″を取り出せる。この0か1かを判別するための区切り(図中青線)は、しきい値と呼ばれる。
ノイズを見つける・治す
また、”01011100″のデータを送る通信の途中で、しきい値を越えるような大きなノイズが混ざって、受信したとする。この場合、単純に受け取るだけであれば、”01010100″で間違った値を受け取っても判別できない。しかし、データを送る際にパリティビット(偶数パリティであれば全データの1の数が偶数になるように)1ビットのデータを加える。このデータを受け取った際に、ノイズで1ビット反転した場合、1の数が奇数(3個)なので、ノイズでビット反転が発生したことがわかる。これをパリティチェックと言う。
このように、デジタル信号を使えば、しきい値を越えない程度のノイズならノイズの影響を無視できるし、たとえ大きなノイズでデータに間違いがあっても、パリティチェックのような方法を使えば間違って伝わったことを判別できる。
パリティチェックは、元のデータに1bitの信号を追加することで誤り検出ができるが、2bit同時に変化してしまうと誤りを見つけられない。そこで、元データにさらに多くのbit情報を追加すると、1bitの間違いを元に戻すようにもできる。誤り検出・訂正
電子回路で制御するかコンピュータで制御するか
これ以外にも、デジタル信号にする理由がある。
アナログ回路(電子回路)で制御しようとすると、抵抗やコイルやコンデンサといった受動素子が必要となるが、その中でもコイルは小型化がしづらい部品で、制御回路全体の小型化が難しい。大量生産ができるような回路なら小型化ができるかもしれないが、多品種少量の生産物では小型化のための開発費用の元がとれない。しかし、大量生産された安価な小型コンピュータで制御すれば、制御回路全体の小型化も可能となる。
また、電子回路の特性を調整するには、抵抗などの部品をはんだ付けをしながら部品を交換することになるかもしれない。しかしながら、アナログ信号をデジタル信号にしてしまえば、ノイズを減らすための平均化処理などは計算で実現できるし、特性を変化させるための調整もプログラムの数値を変更するだけで可能となる。
UMLと構造図
前回の説明のUMLのできたころの話を踏まえ、UMLの中のプログラムの構造図の説明を行う。
UML(Unified Modeling Language)記法が生まれるまで
巨大なプロジェクトでプログラムを作る場合、対象となるシステムを概念として表現する場合、オブジェクト指向分析(OOA: Object Oriented Analysis)やオブジェクト指向設計(OOD: Object Oriented Design)とよばれるソフトウェア開発方法が重要となる。(総称して OOAD – Object Oriented Analysis and Design)
これらの開発方法をとる場合、(1)自分自身で考えを整理したり、(2)グループで設計を検討したり、(3)ユーザに仕様を説明したりといった作業が行われる。この時に、自分自身あるいはチームメンバーあるいはクライアントに直感的に図を用いて説明する。この時の図の書き方を標準化したものが UML であり、(a)処理の流れを説明するための振る舞い図(以前であればフローチャートやPAD)と、(b)データ構造を説明するための構造図を用いる。
UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA中心)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE)を元に1990年頃に 発生し、ブーチのBooch法(どちらかというとOOD中心)の考えをまとめ、 UML(Unified Modeling Language)としてでてきた。
UMLでよく使われる図を列記すると、以下の物が挙げられる。
- 構造図
- クラス図
- コンポーネント図
- 配置図
- オブジェクト図
- パッケージ図
- 振る舞い図
- アクティビティ図
- ユースケース図
- ステートチャート図(状態遷移図)
- 相互作用図
- シーケンス図
- コミュニケーション図(コラボレーション図)
UMLを正しく使うことができるようになれば、UMLで仕様書を書けばそれがそのままプログラムになることが理想的な姿かもしれない。ソフトウェア開発やソフトウェアの保守にソフトウェアツールを利用することは、CASE(Computer Aided Software Engineering)と呼ばれ、そのようなツールをCASEツールと呼ぶ。地元福井の永和システムマネジメントでは、astar* というCASEツールを開発している。
UMLの構造図の書き方の説明。 詳しくは、参考ページのUML入門などが、分かりやすい。
クラス図
クラス図は、構造図の中の基本的な図で、 枠の中に、上段:クラス名、中段:属性(要素)、下段:メソッド(関数)を記載する。 属性やメソッドの可視性を示す場合は、”-“:private、”+”:public、”#”:protected 可視性に応じて、”+-#”などを記載する。
関連
クラスが他のクラスと関係がある場合には、その関係の意味に応じて、直線や矢印で結ぶ。
(a)関連(association):単純に関係がある場合、
(b)集約(aggregation):部品として持つが、弱い結びつき。関係先が消滅しても別に存在可能。(has-a)
(c)コンポジション(composition):部品として持つが強い結びつき。関係先と一緒に消滅。(has-a)
(d)依存(dependency):依存関係にあるだけ
(e)派生(generalization):派生・継承した関係(is-a)
(f)実現(realization): Javaでのinterfaceによる多重継承
上図の例では、乗り物クラスVehicleから自動車Carが派生し(CarからVehicleへの三角矢印―▷)、 自動車は、エンジン(Engine)を部品として持つ(EngineからCarへのひし形矢印―◆)。エンジンは車体と一緒に廃棄なら、コンポジション(C++であれば部品の実体を持つ)で実装する。
自動車は、同じく車輪(Wheel)を4つ持つが、自動車を廃棄してもタイヤは別に使うかもしれないので、集約(部品への参照を持つ)で実装する(WheelからCarへのひし形矢印―◇)。 集約で実装する場合は、C++などであれば、ポインタで部品を持ち、部品の廃棄(delete)は、別に行うことになる。
Javaなどのプログラム言語では、オブジェクトはデータの実体へのポインタで扱われるため、コンポジションと集約を区別して表現することは少ない。
is-a 、has-a の関係
前の課題でのカモノハシクラスで、羽や足の情報をどう扱うべきかで、悩んだ場合と同じように、 クラスの設計を行う場合には、部品として持つのか、継承として機能を持つのか悩む場合がある。 この場合には、“is-a”の関係、“has-a”の関係で考えると、部品なのか継承なのか判断しやすい。
たとえば、上の乗り物(Vehicle)クラスと、車(Car)のクラスは、”Car is-a Vehicle” といえるので、is-a の関係。 “Car is-a Engine”と表現すると、おかしいことが判る。 車(Car)とエンジン(Engine)のクラスは、”Car has-a Engine”といえるので、has-a の関係となる。 このことから、CarはVehicleからの派生であり、Carの属性としてEngineを部品として持つ設計となる。
オブジェクト図
クラス図だけで表現すると、複雑なクラス関係では、イメージが分かりづらい場合がでてくる。 この場合、具体的な値を図に書き込んだオブジェクトで表現すると、説明がしやすい場合がある。 このように具体的な値で記述するクラス図は、オブジェクト図と言う。 書き方としては、クラス名の下に下線を引き、中段の属性の所には具体的な値を書き込んで示す。
パッケージ図
パッケージ図は、クラス図をパッケージ毎に分類して記載する図。 パッケージのグループを、フォルダのような図で記載する。

IT専科から引用
コンポーネント図とコンポジット構造図
コンポジット構造図は、クラスやコンポーネントの内部構造を示すもので、コンポーネント図は、複数のクラスで構成される処理に、 インタフェースを用意し、あたかも1つのクラスのように扱ったもの。 接続するインタフェースを飴玉と飴玉を受けるクチのイメージで、提供側を◯───で表し、要求側を⊃──で表す。

IT専科から引用
配置図
配置図は、システムのハードウェア構成や通信経路などを表現するための図。 ハードウェアは直方体の絵で表現し、 デバイスの説明は、”≪device≫”などを示し、実行環境には、”≪executionEnvironment≫” などの目印で表現する。

IT専科から引用
リスト処理
リスト構造
リスト構造は、データと次のデータへのポインタで構成され、必要に応じてメモリを確保することで、配列の上限が制限にならないようにする。また、次のデータへのポインタでつなげているため、途中へのデータ挿入が簡単にできるようにする。
まずは、メモリ確保とポインタをつなげるイメージを確実に理解してもらうために、1つ1つのデータをポインタでつなげる処理を示す。
#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 を指定することで、ダイヤモンド型継承の 2つの属性をうまく処理してくれるようになる。
しかし、多重継承は処理の曖昧さや効率の悪さもあることから、採用されていないオブジェクト指向言語も多い。特に 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 ) { // 要素を1つ後ろにずらす処理(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 ; }