Webページの生成とプログラム言語
前回の講義では、OSの仕組みとインターネット(Web)の仕組みについて、総括・復習をおこなった。
前回の理解確認の Forms では、間違った回答をした人もある程度いたので、もう一度回答しても良いものとします。ただし、2回目の回答がある場合は、点数を 2/3 にて集計します。
2回目の授業では、インターネットのWebページを作るために使われているHTMLやCSSやプログラム言語について解説を行う。
インターネットの仕組みとDNSの演習
Webページの生成とプログラム言語
理解確認
- こちらの小テストに回答してください。
繰り返し処理と処理時間の見積もり
単純サーチの処理時間
ここで、プログラムの実行時間を細かく分析してみる。
// ((case-1)) // 単純サーチ O(N) #define SIZE 1024 int a[ SIZE ] ; // 配列 int size ; // 実際のデータ数(Nとする) int key ; // 探すデータ for( int i = 0 ; i < size ; i++ ) if ( a[i] == key ) break ;
例えばこの 単純サーチをフローチャートで表せば、以下のように表せるだろう。フローチャートの各部の実行回数は、途中で見つかる場合があるので、最小の場合・最大の場合を考え平均をとってみる。また、その1つ1つの処理は、コンピュータで機械語で動くわけだから、処理時間を要する。この時間を ,,, とする。
この検索処理全体の時間 を考えると、平均時間とすれば、以下のように表せるだろう。
ここで例題
この単純サーチのプログラムを動かしてみたら、N=1000で、5μ秒かかったとする。では、N=10000であれば、何秒かかるだろうか?
感のいい学生であれば、直感的に 50μ秒 と答えるだろうが、では、Tβ,Tα は何秒だったのだろうか? 上記のT(N)=Tα+N ✕ Tβ に当てはめると、N=1000,T(N)=5μ秒の条件では、連立方程式は解けない。
ここで一番のポイントは、データ処理では N が小さな値の場合(データ件数が少ない状態)はあまり考えない。N が巨大な値であれば、Tαは、1000Tβに比べれば微々たる値という点である。よって
で考えれば良い。これであれば、T(1000)=5μ秒=Tβ×1000 よって、Tβ=5n秒となる。この結果、T(10000)=Tβ×10000=50μ秒 となる。
2分探索法と処理時間
次に、単純サーチよりは、速く・プログラムとしては難しくなった方法として、2分探索法の処理時間を考える。
// ((case-2)) // 2分探索法 int L=0 , R=size ; // プログラムは複雑になった while( L != R ) { int M = (L + R) / 2 ; if ( a[M] == key ) break ; else if ( a[M] < key ) L = M + 1 ; else R = M ; }
このプログラムでは、1回のループ毎に対象となるデータ件数は、となる。説明を簡単にするために1回毎にN/2件となると考えれば、M回ループ後は、件となる。データ件数が1件になれば、データは必ず見つかることから、以下の式が成り立つ。
…両辺のlogをとる
2分探索は、繰り返し処理であるから、処理時間は、
ここで、本来なら log の底は2であるが、後の見積もりの例では、問題に応じて底変換の公式で係数が出てくるが、これはTβに含めて考えればいい。
単純なソート(選択法)の処理時間
次に、並べ替え処理の処理時間について考える。
単純な並べ替えアルゴリズムとしてはバブルソートなどもあるが、2重ループの内側のループ回数がデータによって変わるので、選択法で考える。
int a[ 1000 ] = { 対象となるデータ } ; int size = N ; for( int i = 0 ; i < size - 1 ; i++ ) { int tmp ; // i..size-1 の範囲で一番大きいデータの場所を探す int m = i ; for( int j = i + 1 ; j < size ; j++ ) { if ( a[j] > a[m] ) m = j ; } // 一番大きいデータを先頭に移動 tmp = a[i] ; a[i] = a[m] ; a[m] = tmp ; }
このプログラムの処理時間T(N)は…
… i=0の時
… i=1の時
:
… i=N-1の時
…(参考 数列の和の公式)
となる。
オーダー記法
ここまでのアルゴリズムをまとめると以下の表のようになる。ここで処理時間に大きく影響する部分は、最後の項の部分であり、特にその項の係数は、コンピュータの処理性能に影響を受けるが、アルゴリズムの優劣を考える場合は、それぞれ、 の部分の方が重要である。
単純サーチ | |
2分探索法 | |
最大選択法 |
そこで、アルゴリズムの優劣を議論する場合は、この処理時間の見積もりに最も影響する項で、コンピュータの性能によって決まる係数を除いた部分を抽出した式で表現する。これをオーダー記法と言う。
単純サーチ | オーダーNのアルゴリズム | |
2分探索法 | オーダー log N のアルゴリズム | |
最大選択法 | オーダー N2 のアルゴリズム |
練習問題
- ある処理のデータ数Nに対する処理時間が、であった場合、オーダー記法で書くとどうなるか?
- コンピュータで2分探索法で、データ100件で10[μsec]かかったとする。
データ10000件なら何[sec]かかるか?
(ヒント: 底変換の公式) - の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?また、このような処理時間となるアルゴリズムの例を答えよ。
- の処理時間を要するアルゴリズムを、オーダー記法で書くとどうなるか?
(ヒント: ロピタルの定理)
- 2と4の解説
- 1は、N→∞において、N2 ≪ 2Nなので、O(2N) 。厳密に回答するなら、練習問題4と同様の説明を行う。
- 3は、O(1)。誤答の例:O(0)と書いちゃうと、T(N)=Tα×0=0になってしまう。事例は、電話番号を、巨大配列の”電話番号”番目の場所に記憶するといった方法。(これはハッシュ法で改めて講義予定)
再帰呼び出しの予習
次の講義の基礎を確認という意味で、再帰呼出しと簡単な処理の例を説明する。
最初に定番の階乗(fact)
次に、フィボナッチ数列の場合
次の講義への導入問題
ここで示す導入問題をすべて答えるには、若干の予習が必要です。まずはどういう考え方をすれば解けるかな…を考えてみてください。
- fact(N)の処理時間を、Tfact(N) = … のような式で表現し、処理時間をオーダ記法で答えよ。
- 以下のプログラムの実行結果を答えよ。また、関数sum()の処理時間を対象となるデータ件数N=R–Lを用いて Tsum(N) = …のような式で表現せよ。
int a[] = { 1 , 5 , 8 , 9 , 2 , 3 , 4 , 7 } ; int sum( int a[] , int L , int R ) { if ( R-L == 1 ) { return a[L] ; } else { int M = (L + R) / 2 ; return sum( a , L , M ) + sum( a , M , R ) ; } } int main() { printf( "%d¥n" , sum( a , 0 , 8 ) ) ; return 0 ; }
創造工学演習・PHPとDB(予備実験)
インターネットを活用したプログラムを作成する場合、データを保存管理するためのデータベースと、データベースのデータを処理するためのプログラム言語が必要となってくる。今回の予備実験では、そのためにリレーショナルデータベースと、Webの動的なプログラム言語である PHP について説明する。
リレーショナル・データベース
データベースは、データを保存し、矛盾が発生しない様に管理してくれるシステムであり、インターネットで活用されている。
データを確実に保存し、矛盾なく扱うためには、本来複雑なプログラムが必要となる。この中で、データを表形式のテーブルを組み合わせて管理するシステムはリレーショナルデータベースと呼ばれる。リレーショナルデータベースでは、データの問い合わせなどの処理が簡単にできるように、SQL と呼ばれる言語を使って処理を行う。
大量のデータをインターネットの中で利用するためには、ネットワークを経由してデータの問い合わせが求められ、有名なデータベースシステムには、Oracle, MySQL などがある。今回の実験では、ネットワーク機能は持たないが簡単な手続きで使うことができる SQLite を使って説明する。
また、今回の予備実験では時間も限られることから、複数の表を組み合わせた SQL の処理については割愛する。
SQLの基本
リレーショナルデータベースでは、データの基本は表形式データであり、1つの表に相当するデータはテーブルと呼ぶ。
以下の様な名前・住所・年齢のデータがあったとすると、1人前のデータをレコードと呼び、name, addr, age といった属性はカラムと呼ぶ。
name | addr | age | |
t-saitoh | 越前市 | 55 | ←レコード |
sakamoto | 福井市 | 50 | |
murata | 福井市 | 35 | |
↑カラム |
データの型には、文字列型(char型,varchar型,text型)や、数値型(integer型,decimal型,real型)などがあり、create table 文にてカラムの型を定義する。
create table テーブルを作る
データベースの表を使う最初には、create table 文を実行する。C言語での struct 文をイメージすると解り易いかもしれないが、データはデータベースの中に永続的に保存されるので、システムを動かす最初に一度実行するだけで良い。
上記のような名前・住所・年齢のデータ構造であれば、次の様な create table 文を使う。
create table テーブル名 ( カラム名1 型1 , カラム名2 型2 ) ; -- 例 -- create table PERSON ( -- テーブル名:PERSON name varchar( 20 ) , -- 名前 addr varchar( 20 ) , -- 住所 age integer , -- 年齢 primary key( name ) -- name はデータ検索のキーであり重複は許されない ) ;
これと同じ様な処理をC言語で書くのであれば、以下の様な構造体宣言と同じであろう。
struct PERSON { char name[ 20 ] ; // 名前 char addr[ 20 ] ; // 住所 int age ; // 年齢 } ;
drop table テーブルを消す
データベースは永続的に保存されるので、テーブル全体のデータが不要であれば、drop table 命令で、テーブル全体を消す。
drop table テーブル名 ; -- 例 -- drop table PERSON ;
insert into レコードを追加
データベースに1レコードを保存するには、insert文を用いる。
insert into テーブル名 ( カラム名... ) values( 値... ) ; -- 例 -- insert into PERSON ( name , addr , age ) values ( 't-saitoh' , '越前市' , 55 ) ; insert into PERSON ( name , addr , age ) values ( 'sakamoto' , '福井市' , 50 ) ; insert into PERSON ( name , addr , age ) values ( 'murata' , '福井市' , 35 ) ;
delete レコードを消す
データベースのレコードを消すには、delete 文を用いる。条件を満たす複数のデータをまとめて消すことができる。
delete from テーブル名 where 条件 ; -- 例 -- -- 40歳未満のデータを全て消す。 murata,福井市,35 が消える。 delete from PERSON where age < 40 ;
update レコードを更新
データベースのレコードを修正するには、update 文を用いる。条件を満たす複数のデータをまとめて修正することもできる。
update テーブル名 set カラム = 値 where 条件 ; -- 例 -- -- 住所が越前市のレコードの年齢を 0 にする。 update PERSON set age = 0 where addr == '越前市' ;
select データを探す
データベースの内容を参照するための命令が select 文。where を記載することで、特定の条件のデータだけを選択したり、特定のカラムだけを抽出することができる。
select カラム名 from テーブル名 where 条件 ; -- 例 -- -- PERSON の全データを出力 select * from PERSON ; -- PERSON の住所が福井市だけを選別し、名前と住所を抽出 select name,addr from PERSON where addr = '福井市' ; -- PERSON の年齢の最高値を出力 (集約関数) select max(age) from PERSON where addr = '福井市' ; -- PERSON の年齢条件を満たす人数を数える (集約関数) select count(name) from PERSON where age >= 50 ;
動的なプログラム言語とPHP
本来、Webサーバが作られた頃は、論文や研究用のデータを公開する物であったが、扱うデータが増えるにつれ、特定の論文や研究データの一覧を表示したり探したりという処理が求められた。こういった処理のためにWebページのアクセスを受けた時に処理を実行する CGI という機能があったが、これを発展させてできたプログラム言語が PHP である。
PHPでは、ページを表示するための HTML の中に <?php … ?> のといった開始タグ・終了タグの中に、ブラウザから送られてきたデータに合わせて、処理を行うPHPの命令を記述し、データを(一般的にはHTML形式で)表示することができる。基本文法は C 言語に似ているが、様々なデータを扱うために変数にはどのような型でも保存できるようになっている。
ブラウザからデータを送るためのform文
ブラウザで入力欄を作ったり選択肢を表示し、その結果を送るための HTML は、入力フォーム(form)と呼ぶ。
<form method="get" action="処理ページ" > <input type="text" name="変数名" /> <input type="radio" name="変数名" value="値" /> <input type="checkbox" name="変数名" value="値" /> <textarea cols="横文字数" rows="行数"></textarea> <select name="変数名"> <option value="値1">表示1</option> <option value="値2">表示2</option> </select> <input type="submit" value="実行ボタンに表示する内容" /> </form>
formでは、入力する項目に変数名の名前を付け、action=”” で示したページにデータを送る。
PHPのプログラムの基本
PHPのプログラムは、外見は一般的に HTML ファイルであり、途中で <?php のタグからは、?> までの範囲が、PHP で処理が行われる。PHP のプログラムで print が実行されると、その場所に print 内容が書かれているような HTML ファイルが生成され、ブラウザで表示される。
PHP の中で変数は、$ で始まり、型宣言は基本的に不要である。
文字データを連結する場合は、“.” 演算子を使う。ダブルクオテーション”…”で囲まれた文字列の中の $名前 の部分は、変数名として扱われ、変数名の内容に置き換えられる。
HTMLのform文の action 属性で示された php であれば、PHPの中で送られてきた値を $_GET[‘変数名’] (method=”get”の場合)、 $_POST[‘変数名’] (method=”post”の場合)、または $_REQUEST[‘変数名’] (method=”get” or “post”) で参照できる。
((( sample.php ))) <html> <head> <title>sample.php</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <body> <form action="sample.php" method="POST"> <input name="A" type="text" /> <!-- 変数 $A --> + <input name="B" type="text" /> <!-- 変数 $B --> = <?php ini_set( 'error_reporting' , E_WARNING ) ; if ( $_REQUEST[ "A" ] != "" && $_REQUEST[ "B" ] != "" ) { print $_REQUEST[ "A" ] + $_REQUEST[ "B" ] ; } else { print "<INPUT TYPE=submit>" ; } ?> </form> </body> </html>
PHPでデータベースを扱う
SQLのデータベースを、プログラム言語の中で扱う場合は、その記述も色々である。PHPでは以下の様にSQLを扱う。
((( survey-init.php ))) <html> <head> <title>survey_init.php</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <body> <?php // デバッグ用にエラー警告を表示する ini_set( 'error_reporting' , E_WARNING ) ; // データベースに接続する $data_dir = "../public_data" ; $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ; // データベースを初期化する $init_sql = "drop table if exists Survey ;" . "create table Survey (" . " uid varchar( 20 ) ," . " item varchar( 10 )" . ") ;" . "insert into Survey ( uid , item ) values ( 't-saitoh' , '猫' ) ;" . "insert into Survey ( uid , item ) values ( 'tomoko' , 'ケーキ' ) ;" . "insert into Survey ( uid , item ) values ( 'mitsuki' , 'ボードゲーム' ) ;" ; if ( $dbh->exec( $init_sql ) < 0 ) { print "Error: $init_sql" ; } // データベースの表形式を読み出し、表形式で出力する。 print "<table border='1'>\n" ; print "<tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ; $select_sql = "select uid,item from Survey ;" ; foreach( $dbh->query( $select_sql ) as list( $uid , $item ) ) { print "<tr><td>$uid</td><td>$item</td></tr>\n" ; } print "<table>\n" ; // データベースの単一データを取り出す $count_sql = "select count(item) from Survey where item = 'ケーキ' ;" ; print $dbh->query( $count_sql )->fetchColumn() ; ?> </body> </html>
PHPの主要なSQL関数(PDO)
$dbh = new PDO(…) ; データベースに接続するハンドラを取得。 $dbh->exec( “create…” ) ; データベースでSQLを実行。 $dbh->query( “select…” ) ; データベースに問い合わせ。「1レコードに対応した配列」が全データだけ繰り返す、2次元配列を返す。 $dbh->query( “…” )->fetchColumn() 結果が1つだけの問い合わせ。集約関数の結果を参照する場合に用いる。
練習問題(1)
- 上記の survey-init.php の select 文の部分を編集し、色々なデータ検索を試してみよ。
入力フォームのデータをデータベースに書き込む
((( survey-vote.php ))) <?php // エラー警告を表示 ini_set( 'error_reporting' , E_WARNING ) ; // form から送られてきた変数を保存 $uid = $_REQUEST[ "uid" ] ; $item = $_REQUEST[ "item" ] ; // データベースに接続する $data_dir = "../public_data" ; $dbh = new PDO( "sqlite:$data_dir/sqlite.db" ) ; // データベースに項目を追加する if ( $uid != "" && $item != "" ) { $insert_sql = sprintf( "insert into Survey( uid , item ) values ( %s , %s ) ;" , $dbh->quote( $uid ) , $dbh->quote( $item ) ) ; $dbh->exec( $insert_sql ) ; // reload処理で追記しないためページを強制的に再表示させる header( "Location: survey-vote.php" ) ; } ?> <html> <head> <title>survey_vote.php</title> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <body> <form method="get" action="survey-vote.php"> 名前: <input type="text" name="uid" /> 好きな物:<input type="text" name="item" /> <input type="submit" value="投票" /> </form> <?php // データベースの表形式を読み出し、表形式で出力する。 print "<table border='1'>\n" ; print " <tr><td align='center'>uid</td><td align='center'>item</td></tr>\n" ; $select_sql = "select uid,item from Survey ;" ; foreach( $dbh->query( $select_sql ) as list( $t_uid , $t_item ) ) { print " <tr><td>$t_uid</td><td>$t_item</td></tr>\n" ; } print "</table>\n" ; ?> </body> </html>
練習問題(2)
- 上記の survey-vote.php のプログラムを編集し色々な入力方法・出力方法を試してみよ。
- 例えば、入力の item 選択に select や ラジオボタン フォームを使う。
- 例えば、出力結果で、item の投票結果を、棒グラフで出力する。