C/C++ - 構造的プログラミング編 第2回 〜配列〜

C 配列

配列とは、連続した記憶領域を指す。先頭要素の記憶領域に対応するポインタがわかると、 そこからの相対位置にあるポインタを O(1) で定められる。

配列の宣言と初期化

C 配列は、その記憶領域の違いから、3つの宣言がある。 整数リテラル N 長の int 型配列は、それぞれ、

int array1[N]={0};
int *array2=(int *)calloc(N,sizeof(int));
static int array3[N];

と初期化され、それぞれ、スタック領域・ヒープ領域・静的領域に生成される。 もちろん、ヒープ領域に生成した場合は、

free(array2);

として解放する必要がある。スタック領域に確保した場合には、任意の値に初期化を行うことが出来、 int 型の値 n_1,...,n_N がある場合、

int array1[N]={n_1, ... , n_N};

とすることで初期化が可能である。また、このような場合、

int array1[]={n_1,...,n_N};

とすることで、コンパイラによって配列長が自動的に決定される。一方、 長さ N を定めている場合、N よりも小さい個数の値で 初期化しようとする場合は、それ以降が 0 として初期化される。

特に、静的領域に確保した場合には、自動的に array3 は、 全て 0 で初期化される。それ以外の全ての場合において、 通常の変数と同様に、初期化を明示的に行わない場合、未定義となる。

C++ の場合、さらに、配列インスタンスとして、

int* array4=new int[N];

をとることが出来る。解体する場合には、

delete [] array4;

とする。配列 new は、コンストラクタとしてデフォルトコンストラクタを 要求するため、これが public に存在しない場合にはコンパイルエラーとなる。 また、オーバーロードしたコンストラクタを呼び出すことも出来ない。

配列への代入

間違っても代入演算子 = を用いることなど出来ないし、むしろ使用禁止にすべきである。

#include <string.h>

として、メモリ操作用の関数宣言をインクルードしておく必要がある。

ある値 c で配列全体を初期化してしまう場合、

void *memset(void *s, int c, size_t n);

関数を用いる。s は、C 配列を表す参照子、n がバイト長となる。

一方、配列から配列への代入は、

void *memmove(void *buf1, const void *buf2, size_t n);

関数を用いる。 buf1 が代入先の C 配列の参照子、buf2 が参照元の C 配列の参照子、 n がコピーするバイト長となる。

気をつけるべき点として、どちらの関数も n は「配列長」ではない。 n は「バイト長」であるため、配列長 * sizeof(int) がその長さとなる。 このことからも言えることだが、初期化で用いる c は、1バイトのビットパターンとなり、 決して、配列の各要素というわけではない。

ポインタ配列

当然、変数のポインタを値として持つ配列を考える事も出来、int型ポインタを持つ N 長の配列は、

int *ptr[N];

として宣言する事が出来る。代入する値が、int 型ポインタであること以外は、 これまでの説明と全く同様である。

例えば、int 型ではなく char 型で同様に宣言した場合には、 特に、文字列リテラルを用いて初期化をすることが出来る。 この事から、char *[N] は、文字列配列ととらえることも可能である。

当然ではあるが、動的にヒープ領域から取ることも可能であり、

int **p=(int **)calloc(N,sizeof(int *));

として取る事になる。

多次元配列

整数リテラル M と N を用いて、

int mat[M][N]; 

などと宣言すると、長さ M の、N 長の配列の配列となる。初期化は、

int mat[M][N]={{n_11, ... ,n_1N},...,{n_M1,...,n_MN}};

などとして行うことが可能である。

一般に、配列のポインタ変数 p は、

int (*p)[M][N]; 

などと宣言される。多次元配列の場合、配列の宣言の場合と異なり、 仮に初期化を完全に行ったとしても、その全てのサイズを コンパイルタイムに自動的に決定させる事が出来ない。 すなわち、M は決定できるが、N は決定できないため、 決定できない N は必ず明示的に指定しなければならないという制約を持つ。

さて、int 型ポインタ配列 ptr と、int 型の2次元配列 ptr は、 ともに、int 型変数 i, j を用いて、

ptr[i][j];

とすることで、int 型変数となるという意味で、表面的な挙動は同じであるが、 前者は、必ずしも連続しないメモリ領域へのポインタを配列の値とするものである一方、 後者は、連続することが保障される。

配列への参照子と配列要素の参照子

配列のシンボル自身が参照子の機能をもつため、ここでは、配列要素の参照子という意味での 参照子についてを考える。参照子である以上、int 型配列要素の参照子の型は、 int * である。

関数の引数として使用する場合、配列であることを形式的に示すという意味で、 これと全く同じ挙動を示す型として、int [] 型や int [N] 型を指定することが可能である。 繰り返すようであるが、挙動は同じで、見栄えが違うだけである。

もし、配列への参照子を & 演算子をつけたものとして考える場合、 まず、次の7つの型の違いを考える必要がある。

(1) int **
(2) int *[]
(3) int *[N]
(4) int (*)[]
(5) int (*)[N]
(6) int [][N]
(7) int [M][N]

どれも同じような意味を表しているように思えるが、 実際には、(1)(2)(3) と (5)(6)(7) で意味が異なる。

もし、配列が、int [M][N] 型として初期化されているなら、 参照子としての機能を持つものは、(5)(6)(7) の3つである。 型の本質的な意味は (5) であり、int [N] 配列への参照子を表している。 大事なことは、いずれにせよ、N を整数リテラルで 指定することが必須条件となるということである。 したがって、N が決定できない (4) では初期化の場合と同様に、 コンパイラがその配列長を決定できない。

一方で、配列の配列ではなく、「ポインタ変数の配列」である場合は、 その参照子の型は、(1)(2)(3) となり、その本質は (1) である。 こちらは、N が決定している必要はなく、コンパイラにより決定可能である。

改めて、int [N] 配列 a に対して、&a の型を考えると、これは、 配列のポインタ変数であり、int (*)[N] 型となる。

C 文字列処理

C 文字列は、'\0' を終端とする char 型配列として記録され、必然的に 配列操作を必要とする。大別すると、参照子からの相対位置指定で処理する場合と、 反復子による絶対位置指定で処理する場合の2つがあると言える。

文字列の代入

文字列の代入は、反復子 str1 と str2 を用いて、

while(*++str1=*++str2);

などと実装できる。実際のところは、これは非常に危険な実装で、 バッファオーバーランを避ける意味で、int 型変数 n を用いるなどして、 str1 側が代入可能な最大長を指定するなどの方法を取るべきである。

文字の探索

ある文字リテラルで初期化された char 型変数 c と一致する文字を C 文字列 str から探索することを考える。

int 型整数 i と文字列長 n を用いると、これは、

for(i=0; i<n&&str[i]!=c; ++i);

などと実装できる。ほとんど、終端条件で完結しており、 インデックス i が文字列長より小さく、かつそのインデックス位置の文字が c と等しくないならば探索を継続する。

したがって、もし文字が見つかったならば、i はその文字列の位置となる。

一方、char * 型反復子 itr を用いれば、

for(itr=str; *itr&&*itr!=c; ++itr);

などと実装できる。str が C 文字列である限りにおいて、itr もまた C 文字列となる。

反復子を利用する場合の代表的なバグである、バッファオーバーランを撲滅するために 非常に重要なものは、* 演算子の使い方である。たとえば終端条件において、 * を用いることなく、反復子をそのまま用いることは、ほぼ確実にありえない。

終端条件である、

*itr&&*itr!=c;

を分解すれば、*itr は、その位置が終端文字である '\0' であるかを判定しているものであり、 決して、NULL であるかを調べているわけではない。そもそも、反復子が明示的な代入なしに、 インクリメント操作のみで NULL を指すことはありえない。

アルゴリズムという立場で見るならば、これは、線形探索であり、 計算時間は、O(n) となる。

整列アルゴリズム

整列とは、長さ N の配列上に記録される < 演算子が定義される 比較可能な型 T に対して、昇順、または降順にデータを並べ替える操作をいう。

交換アルゴリズム

例えば、配列長 2 の配列を昇順に並べ替えることを考える。 この場合は、例えば、

T a, b;

の2つのデータがあるならば、a<b; が真ならば既に整列が終了しているが、 偽である場合は、これを交換しなければならない。

もっとも単純な方法は、次のように T 型の一次変数 temp を用いるものである。

T temp=a;
a=b;
b=temp;

整列アルゴリズムの概要

ここでは、この交換アルゴリズムを基礎におく代表的な整列アルゴリズム3種を概説する。

これらを、プロシージャとして実装する場合、最低でも引数として、 並べ替える配列とその長さが少なくとも必要であり、

void sortProc(int N, T x[], int (*f)(T *lhs, T *rhs));

などとする必要がある。ここで、第3引数は、昇順か降順かを定めるための適当な比較関数として、例えば、

int compareFunc(T *lhs, T *rhs){
 return (*lhs<*rhs)?1:0;
}

などと定義されるものを指定すると、sortProc()内において、T 型変数 l, r に対して、

f(&l,&r);

は、l<r; と等価となる。

マージソート

常に O(NlogN) でソートが完了するもので、特に安定ソートであるという性質を持つ。 アルゴリズムとしては典型的な分割統治法であり、まず、繰り返しデータを二分割していき、 最終的に書くデータ列の要素が2以下となるようにした後に、それぞれのデータ列内でソートを行い、 その後分割した場合の要領で統合を行い、再び統合したデータ列内でソートを行う作業を繰り返す。

等号が成立する2つのデータの前後関係が崩れない、データが必ずしも連続して並ぶ必要がないという 2つの大きな特徴があり、並列化可能、データによって処理時間が左右されないという利点もあるのだが、 欠点として、実装において、どうしても O(N) の一時作業領域が必要となる。

ヒープソート

大規模な一時作業領域を必要としないソートである。未整列状態の配列から、 ヒープ構造と呼ばれるものに変換した後、最大値を取り出すことを繰り返し行い整列を完成する。

ヒープ構造は、配列で表現される代表的なデータ構造であり、配列 array に対して、 array[0] が最大値であるならば、i<N に対して、array[i] が array[2*i], array[2*i+1] のいずれよりも 大きい値となるようにデータを並べ替えたものである。

最大値をヒープ構造の末端と交換し、改めて、1つ小さな長さの配列をヒープ構造に変換するという作業を 繰り返すことで最終的に配列は昇順となる。

アルゴリズムの性質上、ソートする範囲をヒープ構造に変換していくため、安定ソートとならないが、 部分的に未整列となっているところのみを局所的にソートするような用途に向き、O(NlogN) で整列が完了する。

クイックソート

安定ソートでなく、常に処理時間が O(NlogN) であることも保障されないが、 実用上、平均的にみて、最も高速にソートを完了させる事が出来る方法である。

ピボットと呼ばれる要素を基準に、ピボットよりも小さい値と大きい値の集合に分割する作業を 繰り返すことでソートを行う。より、確実に処理時間を O(NlogN) に近づけるため、 このピボットの選び方を工夫し、また、ソート終了前段階で、ほとんど整列済みの配列をソートさせる場合に 高速であるという特徴を持つ、O(N^2) の処理時間の挿入ソートに切り替える事などが行われる。

double 型配列と数値計算

全ての要素に等しく O(1) でアクセス可能であるという配列を使う最も重要な応用が、 数値計算である。非常におおざっぱに大別すると、ある値を関数の引数とした時に返す値を求める数値演算と、 関数がある条件を満たす値を返すような引数を求める最適化問題に分けられる。

浮動小数点数演算と誤差

数値計算では、浮動小数点数 double 型を用いると決めた瞬間から、演算結果には常に、 打ち切り誤差、桁あふれ、丸め誤差、情報落ち、桁落ちという誤差が発生する。

誤差は演算を繰り返すことで蓄積され、代数的に厳密に確かな値と数値計算結果が == 演算子の意味で 真になることは絶望的である。

double 型の値域は、絶対値が DBL_MIN から DBL_MAX の間の数値、または、0., NaN, +Inf, -Inf のいずれかである。 定義上、DBL_MIN = 2.225074e-308, DBL_MAX = 1.797693e+308 となるが、丸め誤差の意味で、 この間の全ての実数が扱えるわけでは決してなく、0. を除けば、 DBL_EPSILON という値がおおよその絶対値の最小値となる。これは、double 型で表現可能な 1. より大きい最小値と 1. との差 であり、簡単に言えば、絶対値が DBL_MIN より大きく、 DBL_EPSILON より小さい値は、1. に足しても 1. から変化しない。

その値は、2.220446e-016 という値であり、数値演算という立場から見れば、この値の平方根を基準として、 これよりも小さい値は、浮動小数点演算に伴う様々な誤差に埋もれる意味のない数値と考えてよい。

反復法と収束判定

数値計算の基本は、浮動小数点数で与えられる初期値から始めて、 浮動小数点数を返す関数の値と引数の2つの値から導かれる収束条件と呼ばれるものを満たすまで 得られた関数の値で初期値を書き換えることで最終的な演算結果を得る手法である。

ファンクションとして反復法を実装するならば、引数に少なくとも、初期値、収束関数、収束条件の3つが必要となる。 初期値 double x0, 収束関数 double (*f)(double x); 収束判定 bool (*r)(double xNew, double xOld); とすれば、

double iterativeMethodFunc(
    double x0, double (*f)(double x),
    bool (*r)(double xNew, double xOld)){
	double x=f(x0);
	while(!r(x, x0)){
		x0=x;
		x=f(x0);
	}
	return x;
}

などと定義できる。

収束判定をする関数である r について考える。

r は、2つの引数をとり、収束条件を満たすと true を返す関数である。 たとえば収束関数の返り値と引数が一致すれば、それ以降どれだけ収束関数を繰り返しても値が変わらない、 すなわち、収束したと判定できる。従って、

bool conversion(double xNew, double xOld){
	return fabs(xNew-xOld)<sqrt(DBL_EPSILON);
}

などとすれば、おおよそ2つの値が非常に近いということが判定できる。

一方、配列を取り扱うならば、ファンクションではなくプロシージャとして定義することになる。

void iterativeMethodProc(
	double x[], double x0[], int n,
	void (*p)(double xNew[], double xOld[], int n),
	bool (*r)(double xNew[], double xOld[], int n){
	p(x,x0,n);
	while(!r(x,x0,n)){
		memmove(x0,x,n*sizeof(double));
		p(x,x0,n);
	}
}

配列長を表す n と、結果を代入するための n の長さを持つ配列 x が追加され、 収束関数もそれに伴ってプロシージャ p として定義される。

当然、f や p を変えることで様々なアルゴリズムに切り替えることが出来る。

配列の欠点と限界

C 文字列処理、整列、数値計算という配列を用いる代表的なアルゴリズムを紹介したが、 ここでは、データ構造として配列を用いることの弊害を考える。

大別すると、時間の意味での限界と空間の意味での限界の2つがある。

例えば文字を探索するアルゴリズムを C 文字列処理で考えたが、もし探索しようとする文字が存在しなければ、 配列で表現する以上、文字列をすべてなぞらなければ処理を完了できない。 確かに、配列の値へのアクセスは O(1) であるが、全ての文字を1つずつ見るような作業の場合、 O(1) であるという利点は、全く活用できない。O(N) である以上、N が大きくなればそれに比例して 処理時間も長くなり、全体的に処理が重くなることの原因となる。

さらに、N が大きくなることで、連続性という配列の特性を実現することに無理が生じるようになる。 連続な記憶領域のどこか一部分でも断絶しては配列とは言えないのである。

配列というデータ構造自体にそのような問題点がある上に、さらに、C 配列そのものが扱い辛さに拍車をかける。 数え上げれば、自動配列の配列長がコンパイル時に決定しなければならない、それを是正するための 動的配列には、メモリリークや二重解放の危険性が伴い、また、代入や初期化、値コピーの方法が限られる、 さらには、言語が配列を管理しない事によるバッファオーバーランの危険性など、 効率よりも安全性や柔軟性が必要となる状況下で、決定的に取り扱いに難がある。


文章作成 : yukki-ts (-+-twilight serenade-+- [stage])