リスト構造の生成。テスト直しの後に実施した説明が抜けているので、 リストの生成と処理の部分も含めて2週分を記載。

リスト生成の基礎

リスト構造のイメージを分かってもらうために、面倒だけど データ生成を単調に書いた例。

struct List {
int data ;
struct List* next ;
} ;
// 最初は単純に...
// malloc失敗チェックは省略
struct List* top ;
top = (struct List*)malloc( sizeof( struct List ) ) ;
top->data = 1 ;
top->next = (struct List*)malloc( sizeof( struct List ) ) ;
top->next->data = 2 ;
top->next->next = NULL ;

さすがに面倒なので、補助関数を使う。

// 補助関数を使って
struct List* cons( int x , struct List* n ) {
struct List* ans =
(struct List*)malloc( sizeof( struct List ) ) ;
if ( ans != NULL ) {
ans->data = x ;
ans->next = n ;
}
return ans ;
}
struct List* top = cons( 1 , cons( 2 , NULL ) ) ;

リストを使った簡単な処理

リストの末端には、これ以上データが続いていないことを表すNULLが入っている。

void print( struct List* p ) {
for( ; p != NULL ; p = p->next )
printf( "%d¥n" , p->data ) ;
}
int sum( struct List* p ) {
int s = 0 ;
for( ; p != NULL ; p = p->next )
s += p->data ;
return s ;
}
void main() {
struct List* top = cons( 1, cons( 2, cons( 3, NULL ) ) ) ;
print( top ) ;
printf( "%d¥n" , sum( top ) ) ;
}

リスト構造の応用では、2分木なども説明するので、その説明の導入として、 再帰で同じ処理を書いてみる。

void print( struct List* p ) {
if ( p != NULL ) {
printf( "%d¥n" , p->data ) ;
print( p->next ) ;
}
}
int sum( struct List* p ) {
if ( p == NULL ) {
return 0 ;
} else {
return p->data + sum( p->next ) ;
}
}

入力しながらリストを追加

手作業でリストを生成するような処理では、汎用性が無いので、 データを入力しながらリストを生成してみる。

void main() {
struct List* top = NULL ;
int x ;
while( scanf( "%s" , &x ) == 1 ) {
top = cons( x , top ) ;
}
}

しかし、上記の例では、新しい要素をリストの先頭に挿入する方法なので、 データは入力順序と逆順に保存される。 入力順序と同じように、最後のデータが末尾に入るように書くには、 末尾に挿入するデータの場所を覚えるポインタ(tail)を使って、 以下のように書くことができる。

void main() {
struct List* top = NULL ;
struct List** tail = &top ;
int x ;
while( scanf( "%s" , &x ) == 1 ) {
*tail = cons( x , NULL ) ;
tail = &( (*tail)->next ) ;
}
}

前期の後半はファイルについての説明を細かく行う。 まずは、ファイルとOSは切っても切れない関係ということで、 簡単にOSの歴史を説明。

OSの歴史と役割

簡単にOSの意味を説明するために、簡単に歴史を紹介。 最初のコンピュータが出てきた時代は、すべてが機械語で、 ハードディスクにデータを記録するためにも、面倒なプログラムを自分で書いていた。 しかし、ハードの複雑化と共に、ファイルにデータを記録するといった一般的な処理は 基本となる共通の処理をあらかじめ書いておくことで、 プログラムを共通化できるようになった。

OS,CPUの歴史をパソコンに限定して説明する。 最初のパソコンのOSはBASICだった。しかし機能が不足して16bit化される時に、 新しいOSが必要となりMS-DOSが作られ、異なるハードウェアでも 共通の機能で使えるようになった。

一方、8bit時代にAppleⅡを開発していたApple社は、 Lisaなどを経てGraphical User Interface(GUI)で操作しやすいMacintoshを開発する。 この操作性の影響を受け、Microsoft社は Windows などを開発していく。

これ以前のOSは、シングルタスク・シングルユーザが普通であった。 しかしWindows などのGUI環境では、ウィンドウ毎に別プログラムを動かすことから、 マルチタスク機能が重要となってきた。そしてこれらの機能を安定して動かすために、 i80286,i80386のような32bitコンピュータの開発時に、 プログラム保護機能が実装された。これにより、 不当な動きのプログラムを強制的に止めたりすることができるようになり、 マルチユーザ・マルチタスク機能が普及する。

ファイルとPATH

unixやMS-DOSでは、木構造ファイルが採用され、ディレクトリを使って ファイルを分類して保存ができるようになった。この中でファイルの場所を 指定するために、ディレクトリの名前を根幹から書き連ねる絶対PATHが 使われる。一方で、巨大なファイルであれば、PATH表現は長くて不便となる。 このため注目している場所を起点としてファイルの場所を表現する相対PATHも 使われる。

http://www.itsenka.com/contents/development/uml/communication.html 振る舞い図と相互作用図について説明を行う。

相互作用図

• アクティビティ図

  フローチャートを起源とする図で、状態変化と制御の流れ・データの流れを表現する。

  rarestyleの記事の図を引用
• ユースケース図
  Think ITの記事の図を引用
• ステートチャート図(状態遷移図)
  慶応・藤原氏の記事の図を引用

相互作用図

• シーケンス図
  IT専科の記事より図を引用
• コミュニケーション図
  IT専科の記事より図を引用

eポートフォリオのMaharaを使ったネタをやりませんかとのお誘いで、 自分の環境にひとまずMaharaを入れてみることからやってみよう。

# aptitude install mahara
色々と競合とかでてきたので、競合相手も追加してinstallをかける...
# dpkg-reconfigure -plow mahara
データベースの種類: mysql5
データベースのホスト名: なし
データベースのポート番号: なし
データベース名: mahara
データベースのユーザ名: mahara
データベースのパスワード: パスワード
SMTPホスト名: なし
## /usr/share/doc/mahara/README.Debian に書いてある通り
# mysql -u root -p
Enter password: MYSQLの管理者パスワード
> CREATE DATABASE mahara CHARACTER SET utf8;
Query OK, 1 row affected (0.00 sec)
> GRANT ALL ON mahara.* to mahara IDENTIFIED BY 'パスワード';
Query OK, 0 rows affected (0.00 sec)
> FLUSH PRIVILEGES;
Query OK, 0 rows affected (0.00 sec)
> exit
(( /etc/mahara/apache.conf ))
# http://ホスト名/mahara/ で使えるように、先頭の以下のコメントをはずす。
Alias /mahara /usr/share/mahara

このあと、http://ホスト名/mahara/にアクセス。いろいろチェックがかかって インストール作業がおこわなわれて、最後に Admin User のパスワードとメールアドレスを登録して終了。

参考サイトの情報を元に、https://wiki.mahara.org/index.php/Language_Packs より、 ja-1.3_STABLE_tar.gz をダウンロードし….

# cd /usr/share/mahara/lang
# tar zxvf ...PATH.../ja-1.3_STABLE.tar.gz

あ、日本語化の途中で何か壊しちゃった….site settings が表示できなくなった…

先週のUMLの全体像の話に続いて、UMLの中の構造図を中心に説明を行う。

• クラス図
• オブジェクト図
• コンポーネント図
• パッケージ図
• 配置図

いかのサイトが、必要最小限かつ細かい表現方法が記載されていて便利。 (具体例は他のサイトを参照したほうがいい…)

• UML入門

クラス図とオブジェクト図

四角の枠の中に、クラス名、属性、メソッドを記載。 属性・メソッドの前には、可視性の+:public,-:private,#:protectedの記号を書く。 クラス間に何らかのつながりがあれば、関連ということで直線で結ぶ。 線上には、役割や多重度(例:1..*)を記載。

関連で、包含関係にあるものは集約(あるいは単に包含)と呼ばれ、 ◇ーの矢印で接続する。集約の中で特にライフサイクル依存が強いものは、 コンポジションと呼ばれ、一般的に"has-a"関係となる。 この場合は、[本体] ◆ー [パーツ]の矢印で接続する。 C++あたりであれば、大抵の場合は、集約ならポインタで実装され、コンポジションなら実体で実装されるだろう。

class Tire {     | class Engine {
:             |  :
} ;              | } ;
-----------------+---------+-------------------
class Car { // Composition | class Car {
private:                   | private:
Tire   wheel[ 4 ] ;    |     Tire*   wheel[ 4 ] ;
Engine engine ;        |     Engine* engine ;
} ;                        | } ;

汎化や派生(継承)といった関係の例えば、"Person is-a Animal" といった関係は、 派生クラスから親クラスへの△矢印で接続を行う。

オブジェクト図は、クラス図を具体的な実例で書く。クラス名には下線を書く。

コンポーネント図、パッケージ図

コンポーネント図は、物理的な構成要素からシステム構造を記述する。 大きなプロジェクトの全体像を広い視点で見渡すような場合に有効。 他のコンポーネントとのインタフェースを、ロリポップで表現。
[コンポーネント]—(◯—[コンポーネント]—(◯—[…]

パッケージ図は、パッケージ同士の依存関係を論理的なグルーピングで表現。 １つのパッケージは、フォルダの図で表現し、そのパッケージ間の依存関係を、 破線の矢印で結ぶ。

配置図

具体的なデバイスや実行環境を、立方体の絵で表現。 各デバイス間の関係を直線で接続して表す。

4EIのテスト問題の採点中。 プログラムと効率の理解を確認するために、途中へのデータ挿入の 効率理解ということで、リストであればO(1)であるところを、 配列の途中へのデータ挿入がO(N)かかることの実践ということで、 配列へのデータ挿入を出題している。

しかし、過去の試験問題で似た出題があって、どうも過去問をみて勉強しているようで、 過去の回答者の効率の悪いコードを真似ている人が多い。 さらに、模範解答で説明したネタと一緒になって記憶しているだけの人がいて、 ２つのコードを混ぜた回答していて、ハチャメチャ。
# 頭の中で自分のコードをシミュレートしろよ…

途中挿入だから、移動領域の重なったmoveだし、後ろ側からコピーする典型。 データ検索部を抜いて、後ろにシフトする部分のコードは、

// 普通の後方シフト
int idx ; // 挿入場所
int data ;
for( int i = size - 1 ; i >= idx ; i-- )
array[ i + 1 ] = array[ i ] ;
array[ idx ] = data ;
// 効率の悪い後方シフト
for( int i = idx ; i < size ; i++ ) {
int temp = array[ i ] ;
array[ i ] = data ;
data = array[ i ] ;
}
array[ i ] = data ;

確認として、配列サイズ10000件で同一処理を10000回ループで時間を計測。 通常後方シフト=0.281秒、効率の悪いシフト=0.534秒で、1.9倍遅い。 まあ、速度比較の結果としてはそんなもんだろう…

• 06/10 試したいけど、Android 3.1な端末が必要なのか… "Android Open AccessoryとArduinoベースの開発キット" http://arms22.blog91.fc2.com/blog-entry-… #fnct
• 06/10 Arduinoで動いてるんだってさ。"自動追尾台車「カルガモちゃん」" http://arms22.blog91.fc2.com/blog-entry-… #fnct

この記事は、 の @TohruSaitohに掲載した #fnct タグ付き記事を、まとめたものです。