ホーム » 2019 (ページ 8)
年別アーカイブ: 2019
リスト構造について
データ処理において、配列は基本的データ構造だが、動的メモリ確保の説明で述べたように、基本の配列では大きさを変更することができない。これ以外にも、配列は途中にデータを挿入・削除を行う場合、の処理時間を伴う。以下にその問題点を整理し、その解決策であるリスト構造について説明する。
配列の利点と欠点
今までデータの保存には、配列を使ってきたが、配列は添字で場所を指定すれば、その場所のデータを簡単に取り出すことができる。配列には苦手な処理がある。例えば、配列の中から目的のデータを高速に探す方式として、2分探索法を用いる。
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 ; // 見つからない }
しかし、配列の中に新たに要素を追加しようとするならば、データは昇順に並んでいる必要があることから、以下のようになるだろう。
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つ後ろにずらす処理 for( int j = *psize ; j > i ; j-- ) // O(N)の処理 array[ j ] = array[ j - 1 ] ; array[ i ] = key ; } else { array[ *psize ] = key ; } (*psize)++ ; }
これで判るように、データを配列に追加する場合、途中にデータを入れる際にデータを後ろにずらす処理が発生する。
この例は、データを追加する場合であったが、不要となったデータを取り除く場合にも、データの場所の移動が必要である。
順序が重要なデータ列で途中へのデータ挿入削除
例えば、アパート入居者に回覧板を回すことを考える。この中で、入居者が増えたり・減ったりした場合、どうすれば良いか考える。
通常は、自分の所に回覧板が回ってきたら、次の入居者の部屋番号さえわかっていれば、回覧板を回すことができる。
101 102 103 104 105 106 [ 105 | 106 | -1 | 102 | 104 | 103 ]
このように次のデータの場所という概念を使うと、データの順序を持って扱うことができる。
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 } , } ; for( int idx = 0 ; idx >= 0 ; idx = array[ idx ].next ) { printf( "%d¥n" , array[ idx ].data ) ; }
この方法を取れば、途中にデータ入れたり、抜いたりする場合に、データの移動を伴わない。
しかし、配列をベースにしているため、配列の上限サイズを超えて格納することはできない。
移動平均の処理
前回の授業で説明したようなA/D変換した数値データを読み取った場合、どのようなことが発生するか考える。
例えば、以下に示すような測定値があったとする。
- 2018-06-05-wave.csv
6/21のデータはファイルの行末文字の影響で Microsoft Visual Studio の scanf_s() を使うとデータが1件しか読み込めない問題がありました。現時点の上記ファイルは修正済みです。
このデータの一部をグラフ化してみると、次のような波形であった。
この波形をみると、大きく見ればsinカーブだが、細かい点を見るとデータにブレがある。
誤差の原因
このような測定結果が得られた場合、本来コンピュータで処理したいデータは何であろうか?
原因は様々なものが考えられるが、
- 回路のノイズ対策が不十分で、外部の電気的な影響が混入。
オシロスコープで周期を図ると、60Hz なら、交流電源だったり… - D/A 変換を行う場合には、量子化誤差かもしれない。
例えば、最初の波形が、加速度センサーの値であったとして、船の上で揺れているために、大きな周期で加速度が変化しているかもしれない。一方で、船自体がエンジンによる揺れで加速度が変化しているかもしれない。
船の中で波の揺れと、エンジンの揺れが観測されている加速度センサーの情報で、船の揺れの大きさ・揺れの周期を知りたい場合、どうすればいいだろうか?
移動平均
このデータを見ると、10個のデータまでの間で、波形が上下に変動している。船の揺れとエンジンの揺れが原因であれば、10個ぐらいのデータのゆらぎが、エンジンによる揺れと考えられる。では、この10個ぐらいの範囲で値が上下の影響を減らしたければ、どうすればいいか?一番簡単な方法は、前後10個のデータで平均を取ればいいだろう。増減する値を加えれば、プラスの部分とマイナスの部分の値が相殺されて0に近くはず。そこでは、Excel で前後データの平均をとってみよう。
Excelで前後11点の平均を求める式をセルに入れる
青線:元波形データ(B列)、赤線:前後11点の平均(C列)
このように、データの前後の決められた範囲の平均を平均する処理は、移動平均(単純移動平均)と呼ぶ。
時間tにおけるデータをとした場合、前後5点の移動平均
は、以下のような式で表せるだろう。
移動平均のプログラム
Excel で計算と同じ処理をプログラムで行うと以下のようになるだろう。
// moving-average.c #include <stdio.h> #define WIDTH 5 double data[ 1000 ] ; // 元データ double ans[ 1000 ] ; // 平均後のデータ int main() { int t , i , size ; // 最初に全部のデータを読み込む for( size = 0 ; size < 1000 ; size++ ) { int num ; // コンマ区切りのデータを読む // 2つのデータが読み込めない時は入力を終了 if ( scanf( "%d,%lf" , &num , &data[size] ) != 2 ) break ; } // 移動平均を求める for( t = WIDTH ; t < size - WIDTH ; t++ ) { // t番目のデータの前後WIDTH個の合計 double sum = 0 ; for( i = -WIDTH ; i <= WIDTH ; i++ ) sum += data[ t + i ] ; ans[ t ] = sum / (2*WIDTH + 1) ; } // 計算後のデータをコンマ区切りで出力 for( t = 0 ; t < size ; t++ ) { printf( "%d, %10.6lf, %10.6lf\n" , t , data[ t ] , ans[ t ] ) ; } return 0 ; }
このプログラムを動かすと、データ番号とデータ値をコンマ区切りで与えること。
入力リダイレクトと出力リダイレクト
上記のプログラムでは、キーボードからデータを入力しなくてはいけない。これでは入力が大変なので、保存したファイルを使ってプログラムにデータを与える。
上記のプログラムを、パソコンの Z:¥課題¥moving-average.c に保存したとする。このプログラムを「コンパイル&実行」すれば、Z:¥課題¥moving-average.exe という実行プログラムが作られ、プログラムが起動する。このままでは、キーボードからデータを入力する必要がある。
(1) ファイルから入力した値を使って処理を行うのであれば、コマンドを起動。
タスクバー左側の検索バーに、cmd.exe と入力すれば、命令入力画面が表示される。
(2) コマンド画面で、以下のように入力し、moving-average.exe があるか確認する。
C:¥WINDOWS¥System32> Z: 青は表示される部分、赤が入力 Z:¥> cd Z:¥課題 Z:¥課題¥> dir *.exe 06/21/2019 12:30PM 12345 moving-average.exe
(3) 最初のデータの記録されたCSVファイルを Z:¥課題 に保存する。
(4) コマンド画面で、以下のようにプログラム名の後ろに “< ファイル名” をつけて起動すると、キーボード入力の代わりに、ファイルから読み込んでプログラムが動く。このような起動は、入力リダイレクトと呼ぶ。
Z:¥課題¥> moving-average.exe < 2018-06-05-wave.csv xx, xxx.xxxx, xxx.xxxx ←結果が画面に表示される
(5) これでは、結果がよく分からないので、ファイルに保存し Excel でグラフ化する。コマンド画面で、以下のようにプログラム名の後ろに“> ファイル名” をつけて起動すると、結果を画面に出力する代わりに、ファイルに結果を保存してくれる。このような起動は、出力リダイレクトと呼ぶ。
Z:¥課題¥> moving-average.exe < 2018-06-05-wave.csv > out.csv
出力された out.csv は、データがコンマ区切りなので、Excel でひらけば、結果を表として簡単に読み込める。後は、グラフ化したい範囲を、マウスでドラッグ(もしくはシフトキーを押しながらカーソル移動)し、[挿入]-[グラフ]-[散布図]-[折れ線グラフ] でグラフ化すればいい。
自宅学習の課題
表計算ソフトで、移動平均を計算させてみよう。 ※
- 元波形
- 前後5点で移動平均
- 前後11点で移動平均
- 前後51点で移動平均
をとるような表計算の式を書き込んで、その結果の波形がどんなグラフになるのか確認しておくこと。
UMLの歴史と意味
プログラミングでの演習もほぼ終わり、オブジェクト指向での設計の話へ。 オブジェクト指向でUMLの書き方は、統一した図法という意味で重要であることを 示しながら、全体の説明を行う。
最初に、UML以前の説明として、フローチャート図やPADの説明を行う。 処理の流れを記載するものとして、使われてきているがデータ構造の設計も重要。
UMLは、ランボーによるOMT(Object Modeling Technique どちらかというとOOA中心?)と、 ヤコブソンによるオブジェクト指向ソフトウェア工学(OOSE)を元に1990年頃に 発生し、ブーチのBooch法(どちらかというとOOD中心?)の考えをまとめて、 UML(Unified Modeling Language)としてでてきた。
OMTでは、OOA(Object Oriented Analyze:分析中心)として(1)問題記述、(2)オブジェクトモデルの記述、(3)状態遷移図の作成、(4)データフロー図の作成といったプロセスが行われる。 これに、OOD(Object Oriented Design:実装目的)でOOA段階の図法に加え、 ユースケース図、シーケンス図などを加えながら設計を行う。 この2つをOOADとまとめる場合も多い。
UMLでよく使われる図を列記すると、以下の物が挙げられる。
- 構造図
- クラス図
- コンポーネント図
- 配置図
- オブジェクト図
- パッケージ図
- 振る舞い図
- アクティビティ図
- ユースケース図
- ステートチャート図(状態遷移図)
- 相互作用図
- シーケンス図
- コミュニケーション図(コラボレーション図)
複雑な継承
課題で取り組んでもらっている、動物の進化を表すクラスの概要を示す。
動物・鳥類・哺乳類クラス
// 動物クラス 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() ) ; } } ;
# うーむ、継承する処理が1行程度でかける処理だと、どのやり方も「継承が便利」というように見えないな…(x_x;
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 という機能が使えるようになっている。
簡単テストの解説
前に実施した簡単テストの答え。
キーワードの理解
型の理解
上記の問題だけでは、説明しきれないので、下図左のプログラムと、その printf() で表示するデータの型を示す。
型の意味を考えたうえで、何が表示されるか考えよう。
関数の理解
簡単テスト
情報構造論のテストにて結果は両極端な成績。苦手な人は基本理解が怪しいみたい。ということでC言語の理解の確認。
キーワードの理解
以下のプログラムの下線部 A-I の各単語を説明するのにふさわしいものを、(a)~(f)で選べ。キーワードは予約語と呼ばれることも多い。
(a) 型を表すキーワード、(b) キーワード、(c) 変数名、
(d) 関数名、(e) ファイル名、(f) それ以外
解答欄
A_____, B_____, C_____, D_____, E_____,
F_____, G_____, H_____, I_____
型の理解
以下のプログラムの下線部 A-D の型を答えよ。
(a) int , (b) int型へのポインタ, (c) char, (d) char型へのポインタ, (e) void
解答欄
A_____, B_____, C_____, D_____
関数の理解
以下のように、文字列を src から dest にコピーする(ただし最大文字数 countまで) strncpy を作った。
この関数の下線に示す仮引数部分を完成せよ。
解答欄________________________________
型の無い言語からC言語を学ぶと
情報構造論の中間試験の採点をしていて気づいたこと。
プログラムが解っていない学生の回答で、関数呼び出しで実引数に int とか実引数の型を書く学生がいる。
int foo( int x ) { return x * x ; } void main() { for( int i = 0 ; i < 10 ; i++ ) printf( "%d" , foo( int i ) ) ; } ~~~ なぜ int を書くの?
でも、最近の学生はプログラミングで最初に習うプログラム言語が、JavaScript だったり、Python だったりと、型の無い言語であることが多い。
こういう学生さんは、関数宣言と関数呼び出しでは、以下のような感じで習うことだろう。
// JavaScript function foo( x ) { return x * x ; } for( var i = 0 ; i < 10 ; i++ ) print( foo( i ) ) ; ## Python def foo( x ) return x * x for i in range( 0 , 10 ) print( foo( i ) )
んで、こういう学生さんは、関数宣言の仮引数部分を見ると、変数名しか書いてない。この後にC言語を習うと、仮引数の宣言で foo( int x ) みたいに書いてあると、そこに int と書かないとダメみたいに思う、もしくは int x で一つの引数みたいに思うんだろうな。
だから、関数呼び出しの実引数にで、foo( int i ) みたいに型名を書いてしまうと思われる。int というのは、整数型にするためのもの…みたいなイメージなんだろうか?。
C言語での関数宣言と関数呼び出しの説明
// fooという関数の宣言 int foo( int x ) // foo()の関数の答えの型は、int型。 ~~~~~~仮引数 { // 仮引数 x の型は、int 型。 return x * x ; } void main() { for( int i = 0 ; i < 10 ; i++ ) printf( "%d¥n" , foo( i ) ) ; ~~~実引数 // foo() の第一引数は、整数型を書かないといけない。 // 1番目の実引数 i の型は、int i で宣言されているから、int 型。 // foo( 1.2 ) と書くと、第一引数は double だから、 // 引数の型が合わないのでエラー。 }
関数宣言の引数は、仮引数と呼ぶ。関数を呼び出すときの引数は、実引数と呼ぶ。
C言語では、関数宣言の仮引数には「型」を明示する必要がある。(というか変数宣言では型を明示しないとダメ)
さらにC言語では関数を呼び出すときに、仮引数と実引数で「型」が一致していないとエラーとなる。
JavaScript や Python では、変数に「型」という概念が不要なので、仮引数宣言には「型」を明示する必要がない。
C言語 や Java は、静的な型付けの言語。最初から型がきまっていないとダメな言語。
これに対し、JavaScript や Python という言語は、動的な型付けの言語。プログラム言語が実行中に型を意識しながら動く言語。
福井高専の対外接続の速度
福井高専ではSINETによって接続されているけど、次の更新の際に十分な性能があるかのために、ネットワーク利用状況の確認。
瞬間最大風速で、150Mbps 。ムーアの法則に従うとすれば、2年で2倍と考えると、2022年で約500Mbps, 2025年で1.2Gbps 程度となる。特に今後 学内でBYODが拡大すると、さらなる通信速度が必要と考えられる。
MoodleのSTACKをインストール
数学の先生より、本校で運用している Moodle サーバで、数学の表示や小テストのためのプラグインの STACK をインストールしてほしいとの要請があったので、インストールしてみた。
maxima,gnuplotなどのインストール
STACK は、数式表示に maxima 、グラフ表示に gnuplot を使うのでインストール
# aptitude install maxima # aptitude install gnuplot gnuplot-common
mathjaxのインストール
JavaScript で 数式表示をするための mathjax をインストール
# aptitude install libjs-mathjax fonts-mathjax-extras
プログラムは /usr/share/javascript/mathjax/ に保存されているので moodle から使えるように、ライブラリに登録
# cd /usr/share/moodle/lib # ln -sf /usr/share/javascript/mathjax .
STACKに必要なmoodleプラグインのインストール
“moodle stack”でググったサイトの情報では、zip で拾ってきて、解凍、リネームとか書いてあったけど面倒なので、他のやり方として git の説明があったので、そのまま git を実行
# cd /usr/share/moodle # git clone git://github.com/maths/ moodle-qbehaviour_dfexplicitvaildate.git question/behaviour/dfexplicitvaildate # git clone git://github.com/maths/ moodle-qbehaviour_dfcbmexplicitvaildate.git question/behaviour/dfcbmexplicitvaildate # git clone git://github.com/maths/ moodle-qbehaviour_adaptivemultipart.git question/behaviour/adaptivemultipart
一旦、管理者アカウントでログインし、管理ブロックから通知をクリックしてインストールを完了させる。
STACK本体のインストール
さらに、stack 本体をインストール
# git clone git://github.com/maths/quiz_stack.git mod/quiz/report/stack
管理ブロックから通知をクリックしてインストールを完了。
# git clone git://github.com/maths/moodle-qformat_stack.git question/format/stack
再び、管理ブロックから通知をクリックしてインストールを完了。
最後に動作確認で、無事数式やグラフが表示されていたので、大丈夫だろう。
遅すぎるのでCASのキャッシング
インストールの参考にしたサイトの記事では、数式やグラフ表示などで CAS を使うけど、大量の情報が残ってHDDを消費するとの記載が書いてあったので、キャッシングしない設定にしていた。しかし、遅すぎて使い物にならないのでは意味がないので、「データベースのキャッシュ」にしてみた。
当面、これで運用してみて、HDD が逼迫するようであれば、Moodle サーバはAzureサーバ上なので、HDD の設定を検討してみよう。
TCP/IPのWikipedia記事の輪読
工業英語の高久研・斉藤研の中間試験以後のテーマは、以下の通りとする。
- 以下に示す Wikipedia 英語版の TCP/IP(Internet Protocol Suite) の記事を、全員で輪読とする。
- 範囲は最初から、See also の前まで。
- 担当者は、自分の範囲について記事を和訳し(意訳で良い)、1行目英語2行目和訳した資料を作成し、担当回に配布し、文毎に英語音読,和訳とその説明を行ってもらう。
- 記事の中の専門用語についても、質問がでたら対応できるように調べ、配布資料に簡単な説明も別途併記すること。(用語調査は日本語情報を調べて良い)
- 担当回の配布資料は、輪読後に和訳に問題の箇所があったら修正し再提出を行う事。修正箇所は赤字で示す事。和訳の修正がない場合も、修正点がないことを明記して再提出すること。
- 期間内に輪読が終わった場合は、自分の担当範囲の専門用語から自分の興味のある単語を選び、そのWikipedia英語版の説明記事の概要部分について、上記と同等の資料にてレポートとする。
講義は、斉藤が水曜3限目が授業のため、高久・斉藤グループのみ、水曜3限目卒業研究、木曜3限目工業英語とする。他の授業の都合で入れ替えが出来ない時は、別途指示をします。
今日は、上記資料をダウンロードし大まかに人数分で範囲分けを行い、担当箇所を決めて担当者とその範囲を報告すること。そのあと、自分の担当箇所の和訳作業の時間とする。