講義第10回:Pascal の基礎 --- 配列

今日は、たくさんのデータをまとめて扱うための道具である配列と、それに対 するいくつかの処理について学ぶ。

配列

program calculate_sum(input, output);
var n : integer;
  data: array[1..100] of integer;
 i,sum: integer;
begin
    write('How many numbers you want to input?');
    readln(n);
    for i := 1 to n do readln(data[i]);
    sum := 0;
    for i := 1 to n do begin
        sum := sum + data[i];
        writeln('data[', i:2, ']=', data[i]:5, ', sum = ', sum);
    end;
    readln;
end.
このプログラムでは、配列というものを使う。

var  data: array[1..100] of integer;
と変数宣言のところに書くと、100個の整数型変数ができ、それぞれが data[1] から data[100] までといった風に、番号で指定して操作 できる。この番号のことを、「専門用語」で「添字」(index)という。

配列の便利なところは、まず、変数宣言で var data1,data2,data3, .... data100:integer と書くよりずっと短くて済む(100万個変数が欲しかったら 大きな違いである)ということ、それから実行部も簡潔な繰り返しで書けると いうことである。特に大事なのは、番号(添字)に変数が使えるということで ある。このことのために、上のように、ループの中で配列の要素を順番に見る とか値をいれるとかいったことができる。

実行例

How many numbers you want to input?5
2
3
4
5
6
data[ 1]=    2, sum =          2
data[ 2]=    3, sum =          5
data[ 3]=    4, sum =          9
data[ 4]=    5, sum =         14
data[ 5]=    6, sum =         20

ソート

上の例では、配列を使うとどんないいことがあるかというのがそんなによくは わからないと思う。これまでの講義内容がわかっていれば、配列を使わなくて もおおむね同じ実行結果を得ることはできるはずである。もう少し、配列を使 わないとできないようなことをしてみよう。

program sort_data_from_file(input, output);
var n : integer;
  data: array[1..100] of real;
  i,j : integer;
  work: real;
begin
    n := 0;
    while not eof(input) do begin
        n := n +1;
         readln(input, data[n]);
    end;
    writeln('Input data');
    for i := 1 to n do write(' ',data[i]:5:2); writeln;
    for i := 1 to n - 1 do begin
        for j := i + 1 to n do begin
            if data[i] > data[j] then begin
                work := data[i];
                data[i]:= data[j];
                data[j]:= work;
            end;
        end;
    end;
    writeln('Sorted data');
    for i := 1 to n do write(' ',data[i]:5:2); writeln;
end.
このプログラムは、入力した数を小さい順に並べ変えて出力する。並べ変える 原理は、以下のようなものである。
  1. まず、一番小さい数を先頭に持ってくる。そのために、配列の2番 目の要素から最後の要素までを順に見て、それが先頭の値よりも小さければ2 つを入れ換える。

  2. これで先頭にもっとも小さい数が来た。次に、2番目の位置に残りの 数の中で最小のものを持ってくる。これには、配列の3番 目の要素から最後の要素までを順に見て、それが2番目の値よりも小さければ2 つを入れ換える。

  3. 以下、同様に、 N-1 番目まで順にやっていく。
このプログラムを実行するには、まずデータファイルを別にエディタで作って おく。これは一行に一つ数字を書いておけばいい。このデータファイルの名前 を sample.dat、コンパイルしてできた実行ファイルの名前を simple_sort とすれば、

simple_sort < sample.dat
とシェルウインドウで入力すれば結果が得られるはずである。

注意 コンパイルして作るプログラムの名前には sort は使わな いこと。これは、この名前の別のプログラムがあらかじめ準備されていて、そ ちらが実行されてしまうからである。

ソート(2)

ここでは再帰を使って効率良く ソートを行なう方法を考える。再帰とは、「ある手続きが、自分自身を呼び出 す」ことである。

こういうとむつかしげに聞こえるが、実際にやっていることは大したことでは ない。例えば、上にあげたソーティングについて考えてみる。

上の方法では、人間がやるとしたらとてもばかばかしくてできないような、手 際の悪い方法をつかっている。このために、手間がデータの数の2乗に比例し て増える。これを、もう少しなんとかできないものだろうか。

例えばトランプのカードを人が揃えるとすれば、一つの方法は、まずハート、 スペードといった種類ごとに分け、それからその中を揃えることである。こう すれば、枚数が減って扱いやすい。

もう一つの考え方は、まず揃ってない山を2つに分け、それぞれを揃える。そ れからその2つを合体させるというものである。合体させるのは、両方の山を みて順番が先なものをとっていけばいい。

どちらの方法でも、カードの山をいくつかに分けることで、手間を減らしてい ることがわかる。ここで、よく考えてみると、例えば下の方法では、初めに2 つに分けた山のそれぞれを揃えるのに、さらにそれらを2つに分けるという方 法が使えることが分かる。上の方法でもおなじようなことができる。

この、同じ方法を繰り返し使うというのが、「再帰」の考え方である。具体例 を見てみよう。

program mergesort(input, output);
var n   : integer;
    data: array[1..100] of real;
    wa  : array[1..100] of real;
    i,j : integer;
    infile:text;
    procedure merge(if1, ie1, if2, ie2:integer);
    var i, j, k : integer;
    begin
        i := if1;
        j := if1;
        k := if2;
        while (j <= ie1) or ( k <= ie2) do begin
            if (j > ie1) or ((k <= ie2) and (data[k] < data[j])) then begin
               wa[i] := data[k];
               k := k + 1;
            end else begin
               wa[i] := data[j];
               j := j + 1;
            end;
            i := i + 1;
        end;
        for i := if1 to ie2 do data[i] := wa[i];
    end;
    procedure msort(ifirst, iend:integer);
    var i : integer;
    begin
        i := (ifirst + iend) div 2;
        if ifirst < i then msort(ifirst, i);
        if i+1 < iend then msort(i+1, iend);
        merge(ifirst, i, i+1, iend);
    end;
procedure print(n:integer);
    var i : integer;
    begin
        for i:= 1 to n do begin
            write(' ', data[i]:9:2);
            if i mod 8 = 0 then writeln;
        end;
        if n mod 8 <> 0 then writeln;
    end;
begin
    n := 0;
    while not eof(input) do begin
        n := n +1;
         readln(input, data[n]);
    end;
    writeln('Input data'); print(n);
    msort(1,n);
    writeln('Sorted data');print(n);
    readln;
end.
このプログラムはかなり長いが、原理は比較的単純である。つまり、
  1. まず、データを前半分と後ろ半分にわけ、それぞれソートしておく。

  2. その2つを、それぞれ先頭からみて小さい方をとって並べていく。

つまり、上に述べた方法をそのままプログラムにしている。 教科書のマージソートのプログラムは、ちょっと高度でわかりにくいので、も うすこしわかりやすくした(つもりの)ものを例にしてみた。

1. のところを行なうのが、手続き msort の前半部である。これは、 前半分と後ろ半分について、それぞれ msort 自身を呼ぶ。

2. のところは、手続き merge で行なわれる。ここでは、 data if1 から ie1 までと、 if2 か ら ie2 までに入っている2つの部分列を、1つの列にまとめる。 この時、いったん wa という配列に書いておいて、終ったところで 書き戻す。

merge の動く様子

列a 1 3 4 8 9 列b 2 4 6 7 8 合併列 (空)
列a 3 4 8 9   列b 2 4 6 7 8 合併列 1
列a 3 4 8 9   列b 4 6 7 8   合併列 1 2
列a 4 8 9     列b 4 6 7 8   合併列 1 2 3
もちろん、「再帰」を使わずに、これまでに学んだ繰り返し文だけを使っ て同じ処理をすることもできる。しかし、プログラムがかなり面倒でわ かりにくいものになる。

再帰という形に書くことで、高度な処理を単純な形に表現することがで きる。これについては次週にもう少し詳しく学ぶことにする。

練習

  1. 最初の、合計を求めるプログラムを配列を使わないで書き直して みよ。また、合計だけでなく平均と標準偏差をもとめるように拡 張せよ。配列を使わないで標準偏差を求めることはできるだろう か。

  2. 単純ソートのプログラムを手続きを使う形に書き直してみよ。メ インプログラムはマージソートの場合と同じように、手続きを呼 ぶだけの形になるようにすること。

  3. 教科書のクイックソートのプログラムを実行してみて、うまく動くこ とを確認してみよ。また、なぜこれでうまくいくかを考えよ。

  4. データの数を非常に大きくした時、実行時間がどうなるかを単純ソート プログラムと再帰を使うものの両方について測定せよ。配列宣言の数字を大き くするのを忘れないこと。また理論上どうなるはずか考えてみよ。

なお、あるプログラムの実行時間を計るには time コマンドが使える。

time simple_sort < sample.dat
という風に入力すると、実行結果のあとにもう一行
0.040u 0.080s 0:00.56 21.4% 0+135k 2+0io 21pf+0w
というような出力が出てくる。この最初の数字が秒単位の実行時間である。な お、実際にかかった時間はもっと長いことがあり得る。これは、ファイルの読 み書きの時間は正確には入らないこと、また何人かで1台の計算機を使ってい るのでその分余計に時間がかかることによる。

レポート

前回と今回の「練習」の中から、2つ以上を選んで解き、 をまとめて提出すること。ただし、前回の2番は、それだけでは1問と認めな い。なお、提出は、メイルで
makino-1@chianti.c.u-tokyo.ac.jp
あてに、 Subject を kadai-3 として提出すること。グラフィックスの出力結 果は、以下のようにして提出すること。
  1. 出力結果が画面に出たところで、 ~makino/bin/gfile というコマンド を実行する。これは、実行したウインドウとはべつのところで行 なうこと。
  2. Enter file name: と聞いてくるので、名前をいれる。これは別にどん な名前でもいいが、例えば課題3の1 枚目ならkadai3-1 というように つけるのがいい。
  3. しばらくすると、上の場合なら kadai3-1.uu というファイルができる ので、この中身をメイルにして送る。ただし、上に書いたように、こ れとプログラム、考察はまとめて1つのメイルで送ること。絵が何枚か ある場合も同じで、全体を1つのメイルでおくること。このためには mule の Insert-file (Ctrl-x i) などの機能を使う。
なお、今回のレポートは、適当な時期に WWW 上で公開するので、公開さ れても構わないような内容にして下さい。締切は7/11とする。

次回予告

次回は、再帰処理についていくつかの例で学び、そのあと方程式を解く など多少高度なプログラミングに入っていくことにしたい。