Lecture on Programming I 6/2
Menu Menu
先週の復習
酔っ払いのシミュレーション
2次元配列の実装
無名配列
typist のデータ処理
Mule に関する演習
Buffer と Frame の制御
Emacs は落すな!
New Frame
Emacs Lisp について
xx.pl ファイルの場合に Perl-mode に自動的にするためには?
(setq auto-mode-alist (cons '("\\.pl" . perl-mode) auto-mode-alist))
(setq auto-mode-alist (cons '("\\.pm" . perl-mode) auto-mode-alist))
を ~/.emacs に付け加える。
shell-mode
良いプログラミングスタイルとは?
プログラミングスタイルとは、単にプログラムの書き方ではなく、プログラムを書くときの心構えをさす。プログラムに使う名前には、プログラムを読みやすくする名前を付ける
参考文献
プログラム書法 ISBN4-320-0285-5 C4041
コードコンプリート
The Practical Programming ISBN 0-201-61586-X
push/pop と shift/unshift
push/pop は、スタックという構造を作る。First-in, Last-out で、FILO とも呼ばれる。
push(@a,$d) は、@a = (@a,$d)と同じ
$d = pop(@a) は、$d = $a[$#a]; $#a --; と同じ
push/pop を使って、配列を逆順に表示するプログラムを作れ。
shift/unshift は、キュー(またはバッファ)という構造を作る。First-in, First-out で、FIFO とも呼ばれる。
shift/unshift に相当する操作を配列を使って書いてみよ。
shift/unshift を使って、コマンドラインから、- で始まる引数を削除するプログラムを書け。
splice
配列を変更する一般的な操作
ランダムな配列を作る
1..100 を使うと、1から100まで整列した配列を作ることができる。
@old = 1..100;これによって配列を作成し、どのような配列が作られるかを観察せよ。
ランダムな順序に並べられた任意の長さの配列を作るには、以下の文を使うことが出来る。これを用いて、
while(@old) { push(@new,splice(@old,rand(@old),1)); }
ソートのためのテストデータを作ることができる。
問
splice, randなどを調べて、何故、これがランダムな配列を作るのか説明せよ。(ヒント: ひとつひとつの関数の結果を表示させてみると良い)
Sort
ソート(Sort)とは、配列に格納されたデータを特定の順序に並べる手続きである。整列とも言う。
Bubble Sort
隣同士のデータを順序にしたがって交換することを繰り返すことにより、データは、いつかは、すべて整列される。
@a = (10,20,40,100,200,25,1,7,90,99,102);のデータをこの方法によって整列するプログラムを作成しよう。
作成したプログラムが、長さによってソートに対してどれくらい時間がかかるか測定せよ。時間の測定には、POSIX module のclock() というコマンドを使うと良い。これは、CPU clock を返す。UNIX では、1/60 秒ということになっている。
use POSIX; # POSIX module を使う
$debug = 1;
$time = clock();
# 整列されたデータを生成する
@data = 0..$ARGV[0];
print "create $#data ",clock()-$time,"\n";
$time = clock();
# ランダムなデータを生成する
while(@data) { push(@new,splice(@data,rand(@data),1)); }
print "random $#new ",clock()-$time,"\n";
print "@new\n" if ($debug);
$time = clock();
# ソートする
@data = buble_sort(@new);
print "sort $#data ",clock()-$time,"\n";
print "@data\n" if ($debug);
sub buble_sort
{
# copy したくないので、@_ をそのまま使う
for(my $i=0;$i<=$#_;$i++) { # こんな風に my を使うことも出来る
if ($_[$i-1] > $_[$i]) {
# 隣同士を交換する
$tmp = $_[$i];
$_[$i] = $_[$i-1];
$_[$i-1] = $tmp;
}
}
print "@_\n" if ($debug);
return @_;
}
問
残念ながら、このプログラムは正しく動かない。このプログラムをデバッグして、完成させよ。
プログラムの時間と大きさの関係を plot するには、以下のプログラムを使うと良い。perl5 buble.pl 10 の 10 を例えば、10-500刻みで10づつ 実行した結果に、以下のプログラムを使うと、時間が、それぞれ別なファイルにgnuplotに適した形で出力される。
open(CR,">create.data");
open(SORT,">sort.data");
open(RAND,">random.data");
while(<>) {
if (/create (.*)/) {
print CR $1,"\n" ;
} elsif (/sort (.*)/) {
print SORT $1,"\n";
} elsif (/random (.*)/) {
print RAND $1,"\n";
}
}
Binary Tree
整列したデータ構造を漸時的に(incremental)作成したい場合、データ構造を柔軟に変更したい場合は、木構造を用いると良い。
ここでは木構造のうち、特に、二分木を扱う。木の一つの要素は、
その場所の値 右の木 左の木の三つの属性を持つ。これを配列、
[値、左、右」で表そう。
根 二分木の基(root)
葉 リーフ(leaf)ともいう。木の一番端
幹 ノード(node)ともいう。木の構成要素
sub insert
{
my ($current,$d)=@_;
while($current) {
if ($d == $current->[0]) {
return;
} elsif ($d < $current->[0]) {
if ($current->[1]) {
$current = $current->[1];
} else {
$current->[1] = [$d];
return;
}
} elsif ($d > $current->[0]) {
if ($current->[2]) {
$current = $current->[2];
} else {
$current->[2] = [$d];
return;
}
}
}
}
ランダムな数値を持つ要素を順次付け加えて、二分木構造を作成せよ。
Depth First Walk
この木構造から、整列された要素を取り出すには以下のようにする。
sub walk
{
my ($root)=@_;
return if (! $root);
walk($root->[1]);
print $root->[0]," ";
walk($root->[2]);
}
以下のようにすると、どのような出力が得られるか? それは何故か?
sub walk0
{
my ($root)=@_;
return if (! $root);
print $root->[0]," ";
walk($root->[1]);
walk($root->[2]);
}
この木のたどり方は、まず、どんどん深い方向にいくので、深さ優先(Depth First)と呼ばれる。
深さ優先アルゴリズムを使って、木構造を、Perl のプログラムの形に表示するプログラムを作成せよ。
Breadth First Walk
これに対して、浅いところから順にたどる方法を幅優先(Breadth First)という。一つの実装法は、
一つのレベルのノードのリスト(配列)を作ることである。これから、
次のレベルのノードのリストを作ることは容易だ。これを繰り返すことにより、幅優先アルゴリズムを作ることができる。
Breadth First Walk を、push を使って実装せよ。また、それを使って、木構造を文字的に表現するプログラムを記述せよ。
1
2 3 4
5 6 7 8
9 10
Turtle Graphics を使って、木構造を表示するためには、ノードの値を記述する必要がある。Turtle.pm を改良して、木構造をPerl/Tk
で記述するプログラムを作成せよ。(*)
Built-in sort
Perl には、既に sort をおこなう機能がある。その使い方を調べて、上のプログラムを用いて、速度を測定してみよ。Built-in sort が高速な理由は、二つある。
C を使って記述されている 高速なアルゴリズムを使っているそれでも、手動のソートを使うのは何故だろうか?
sort のシュワルツ変換とは何か? Perl のマニュアルを参考にして解説せよ。また、その速度向上の効果を実測せよ。(*)
typist データの解析
typsit データを解析して、タイピングの順位表を作成したい。以下のことを考慮して順位表作成プログラムを作れ
基本的には平均値を用いる 極端なデータは、除いた方が良い (何故か?) 順位の時間的変化を見れることが望ましい
宿題
以上の問題を
Subject: Report on Programming I 6/8というサブジェクトで、kono@ie.u-ryukyu.ac.jp までメールを出すこと。
(*) がついている問題は option とします。