計算機言語 I 第 6 回 配列
この資料: http://www.math.u-ryukyu.ac.jp/~suga/gengo/2021/06.pdf
1 レポートへのツッコミ: チリも少し積る
前回のレポートの意図は,沢山の数を絶対値の大きい方から足すのと小さい方から足すのの違いを見ること でした.
double 型の桁数は, 16桁程度です. それ以上の桁数部分は, 切り捨てられたり四捨五入されたりします.
1
1000002+ 1
999992+· · · のように小さい方から足すと,小さい部分の切り捨て, 四捨五入が,割と生き残りま
すが, 1 + 1
22 +· · · と足していくと,最後の方の和では, 6桁程度の値しか加えられません. その差が少し出る わけです.
上の解説から分かるように, double型の多数の和の計算では,小さい方から和をとる方が,多くの場合誤差 が少なくなります. 情報処理センターの計算機では,逆に1 から足した方が良い近似値になっていますが,そ の理由は不明です.
なお, 教科書にある
∑∞ n=1
1 n2 = π2
6 を用いたπ2の近似値を計算は, あまり効率の良い方法ではありません. 実際5桁程度の精度しか出ていません.
もうひとつの, log 2の計算ですが, logという関数は当然のごとく数学関数ライブラリにあります. それを 使えという問題ではなく, 4則演算だけを使って,近似値を計算して下さいという問題です.
• コンピュータ(のCPU)は,本来は, 4則演算くらいしか計算はできない.
• 4則演算をうまく利用することにより,複雑な関数の近似値が計算可能になるという数学の威力.
• ただし,うまく利用しないと誤差が大きくなってしまうという現実. を理解して頂きたいのです.
2 教科書 5章の補足
配列型変数
配列型とは,同じ型の変数をいくつか順に並べたもので, awkでもこれは現れました.
なお,「配列の要素数を変数にして可変サイズの配列を利用する」は, 最新のCの仕様ではOK になりまし た. ただし,その使用は限られた方法でしかなく,また, Cの言語としての特性からすると, そのようなものは 邪道ではないかと思います.
教科書にあるように,「配列変数はメモリ上に連続して配置される」というのは, Cの仕様です. テキストで はあまり扱いませんが, Cでの文字列はchar 型の配列として実現されており,上のメモリ上の連続して配置 されるという仕様を利用した文字列処理プログラムが,たくさん書かれています.
整列アルゴリズムと計算量
p. 73に基本的な整列アルゴリズムのバブルソートについて述べてあります. バブルソートは,「対称群は隣
接互換から生成される」という事実の素朴な実装です.
n個の要素a[0], a[1], ..., a[n-1]を小さい順に並べ替えるのを, 教科書のアルゴリズムをそのまま 実装すると,次のようになります. この実装では,「軽いものが浮き上がってくる」(バブルソートの語源)では なく,むしろ,「重いものが沈んで行く」となります.(浮き上がる実装も簡単だけど,多分こちらの方が説明が やさしい).
i=n−1からi= 0まで次を繰り返す. j= 0からj=i−1まで,次を繰り返す.
a[j] > a[j+1]なら入れ替え,そうでなければそのままにする.
内側のループで,i番目,すなわちa[i-1]が確定し,それを外側のループで,n−1から大きい順に0まで実 行します. すなわち,上のアルゴリズムでは,大きい順に場所が確定していきます.
外側のループで,i=n−1 からi= 0まで,内側のループでj= 0 からi−1までの合計n(n−1)/2回の 比較演算と大小関係が異なる時の交換演算が行われます. つまり,この整列法の計算量は,元の要素の形態にか かわらず,およそn2の定数倍です.
データの整列をコンピュータで行うというのは,コンピュータが生まれた時から実行され続けています. バ ブルソートはプログラムとして最も古くからあり, 素朴でわかりやすいものです. しかし, 整列処理は, コン ピュータの中で頻繁に実行されるため,これよりも計算量の少ない整列アルゴリズムが多く発見されています. プログラミングでバブルソートを使うことは稀です.
知られている整列アルゴリズムは10種を超え,それらのアルゴリズムとその特徴を述べる時間はありませ ん. 元データの形に従って,異なるソートアルゴリズムを用いることも普通です. すなわち,どのようなデータ に対しても効率的かつ速く整列するアルゴリズムは, 今のところ見つかっていませんし,おそらく存在しない と思います. 整列アルゴリズムは次の基準で比較されます.
• 計算量はどれくらいか?
• メモリ消費量はどれくらいか?
• 安定か?(同じ値のデータが複数個あった場合に,元の順を保持するか否か)
整列アルゴリズムの中で,メモリの消費量も少なく, どのようなデータに対しても比較的高速に整列するこ とができるアルゴリズムとして, Hoare(ホア)が1960年に発表したクイックソート(quick sort)というもの があります(残念ながら,安定なアルゴリズムではありません). quick sort は, n個のデータをソートする平 均的計算量はO(nlogn) (g(n) =O(f(n))の意味は,定数Cが存在して, lim
n→∞
g(n)
f(n)≤C)になることが知ら れています(データの並び方が悪いときの最悪計算量は, O(n2)). ちなみに, 現在のコンピュータの計算能力 は, PCだと, n= 10000として,かなり頑張ってn5からn6のオーダーで,n7は絶望的です.
比較的汎用的に使える整列アルゴリズムなので, C ではライブラリ関数として, quick sort(の改良版)が
man 3 qsort
データの形がある程度決まっているなら,「並び替えによる整列以外」のアルゴリズムもあり,そちらはかな り高速に動作します.「データを整列させる」と言うのは,以外に難しい問題なのです.
プログラム 5.3
上に述べたことからすると, 教科書p. 75,プログラム5.3のバブルソートの実装とは少し違います. 教科書 の実装は, ほとんど整列済みのデータに対する計算量を減らした実装です. 教科書の実装では, 最悪の計算量 が,通常のバブルソートの実装より 2倍程度増えます. また,ほとんど整列済みデータを簡単に手早く整列さ せるには「シェイカーソート」と呼ばれるバブルソートの派生を実装するのが通常です.
ここでは,バブルソートの素朴な実装を書いておきます.(コメントは略しました)
#include <stdio.h>
#define N 10
int main(void) {
int a[N] ={9, 23, 5, 7, 43, 51, 47, 3, 24, 8};
int i, j, temp;
for (i=N-1; i >= 0; i--){
for (j=0; j <= i-1; j++){
if ( a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
} } }
for (i=0; i < N; i++){
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
2次元配列
行列の様な対象も, 2次元配列を利用してプログラムができます. さらに多次元の配列も使えます.
教科書p. 76の「2次元配列のイメージ」の図を見てください. 実際の Cの実装では, 2次元配列も 通常の
1次元配列を途中で区切って実現しています. p. 76のイメージ図で,a[0][2]の次にa[1][0]のデータが連 続してメモリに配置されます.
マクロ
教科書にマクロという言葉が出てきますが,正確には「マクロ置換」です.
以前にも述べましたが, #define HOGE 10は, cpp がHOGEという文字列を10という文字列に置換して, そのデータをCコンパイラに渡すという仕組みです. HOGE という値(数値)があるわけではありません.
レポート問題
締切は, 5月31日10:00 (JST)
• 3×3の行列(成分はdouble型)を読み込んで, その逆行列を出力するプログラムを書け. 逆行列の計 算は,「逆行列の公式」を利用し,逆行列を持たないときには,そのことを出力する.
重要な注意: 逆行列を「逆行列の公式」を用いてプログラムを実装することはない. 通常は, 掃き 出し法の方が計算量がはるかに少ない
件名: gengo2021 report 6-1
• 上に述べたプログラム 5.3で, a[N]={5, 3, 7, 9, 10, 1, 8, 2, 6, 4} と初期化する. プログラ ム5.3 を応用して, 10個の置換σ=
(1 2 3 4 5 6 7 8 9 10
5 3 7 9 10 1 8 2 6 4
)
∈S10(10次対称群)の符 号を出力する様にせよ.
件名: gengo2021 report 6-2
• 上のσに対してσ−1を隣接互換(1,2), (2,3), . . . ,(9,10)の積で表した式を出力するプログラムを,プ ログラム 5.3を改変することにより書け. ここで, 置換群(対称群)の積は写像の合成とする. 例えば, S4において,
(1 2 3 4
4 1 3 2
)
= (2,3)(3,4)(2,3)(1,2) (1 2 3 4
4 1 3 2
)−1
=
(4 1 3 2
1 2 3 4
)
= (1,2)(2,3)(3,4)(2,3)
