アルゴリズムとデータ構造編【データ構造】 第2章 多次元配列

先頭へ戻る

この章の概要

この章の概要です。

多次元配列

前章で、配列の基本的な特性について解説しました。 ここでは、配列を二次元以上に拡張した、多次元配列を取り上げます。

通常の配列は、あえて言えば一次元配列であると考えられます。 次元の数が、添字の個数と一致すると考えられます。

多次元配列という場合、厳密にどういう配列のことを指すのかは場合によりけりです。 C言語において、

int array[3][5];

のように宣言された配列は、多次元配列と呼ばずに「配列の配列」と呼ぶこともありますが、 ここではこれも多次元配列と呼ぶことにします。

上記のように宣言された配列の要素を参照するには、次元数と同じ個数の添字を用います。

array[2][1] = 10;


前章で、配列の要素がメモリ上で連続的に並ぶことを説明しました。 多次元配列の場合にも、こうなっているかどうかは重要なポイントです。
結論としては、C言語で上記のような多次元配列を宣言した場合、すべての要素は連続的に並びます。 この辺りの詳細は、C言語編でも解説しています(第36章参照)。


一方、次のように、一次元配列を作り、それぞれの要素に動的な配列を確保する形で、多次元配列を作った場合には、 要素が連続的に並ばなくなります。

int* array[3];
int i;

for( i = 0; i < 3; ++i ){
	array[i] = calloc( 5, sizeof(int) );
}

この方法だと、メモリ上で連続的に並ぶのは、1回の calloc関数で確保された要素だけです。実際に、次のようにしてメモリアドレスを確かめれば分かります。

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int* array[3];
	int i, j;

	for( i = 0; i < 3; ++i ){
		array[i] = calloc( 5, sizeof(int) );
	}

	for( i = 0; i < 3; ++i ){
		for( j = 0; j < 5; ++j ){
			printf( "%p\n", &array[i][j] );
		}
		printf( "\n" );
	}

	for( i = 0; i < 3; ++i ){
		free( array[i] );
	}

	return 0;
}

実行結果:

00581C40
00581C44
00581C48
00581C4C
00581C50

005831A0
005831A4
005831A8
005831AC
005831B0

005831E0
005831E4
005831E8
005831EC
005831F0

出力結果にあるように、5個分の要素は連続的なメモリアドレスにありますが、それぞれの組は離れた場所にあることが分かります。 (連続している要素間が 4Byte ずつ空いているのは、int型が 4Byte の環境で確かめているからです)


静的に配列を作ることはできないけれど、連続したアドレスに並んで欲しい場合、全ての要素を一括で確保し、 要素を参照する際に工夫を加える方法があります。 これは、C言語編第36章でも解説しています。

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_COL_NUM    6		/* 配列の列の数 */
#define ARRAY_ROW_NUM    5		/* 配列の行の数 */

int main(void)
{
    int* array;
    int i, j;


    /* 行と列をまとめた一次元配列を動的に確保 */
    array = calloc( ARRAY_ROW_NUM * ARRAY_COL_NUM, sizeof(int) );

    /* 一次元配列の要素を出力 */
    for( i = 0; i < ARRAY_ROW_NUM; ++i ){
        for( j = 0; j < ARRAY_COL_NUM; ++j ){
            printf( "%p\n", &array[i * ARRAY_COL_NUM + j] );
        }
        printf( "\n" );
    }

    /* メモリ解放 */
    free( array );

    return 0;
}

実行結果:

006131A0
006131A4
006131A8
006131AC
006131B0

006131B4
006131B8
006131BC
006131C0
006131C4

006131C8
006131CC
006131D0
006131D4
006131D8

今度は、全ての要素が連続的に並んでいます。 動的確保された配列は、連続的に並ぶことが保証されているので、列数×行数分の要素を一括で確保すれば、このような結果を生み出せます。

各要素を参照する際には、array[2][3] のように添字を2つ使うのではなく、 array[2 * ARRAY_COL + 3] のように、計算で求める必要があります。
確保した配列は、あくまでも1次元配列の形ですから、array[2][3] のように参照することは間違いです。

ジャグ配列

先ほど、calloc関数を使って多次元配列を定義する例が登場しました。 そのときには、一律で要素数を 5 に指定しましたが、考えてみれば同じ値を使うことは必須ではありません。 例えば、

int* array[3];
int i;

for( i = 0; i < 3; ++i ){
	array[i] = calloc( (i+1)*2, sizeof(int) );
}

この場合だと、array[0] のところには 2個、array[1] のところには 4個、array[2] のところには 6個 というように、 ばらばらの要素数で多次元配列を作り出せます。

実はこのように、要素数が1つの次元の中で固定されていない多次元配列には、 ジャグ配列という特別な名前が付いています(「ジャグ」とは「ぎざぎざ」というような意味です) とはいえこれは、多次元配列の中でやや特徴的であるというだけのことです。

イメージ図は次のようになります。

ジャグ配列

この図から分かるように、形が綺麗な長方形になりません。 そのため、不規則配列と呼ばれることもあります。 (この図だと、階段状なので、ある意味規則的ですが・・・)
これに対し、要素数が一定になっており、イメージ図にすると長方形になる通常の多次元配列は、 規則配列矩形配列と呼ばれます。

なお、最初に固定で一次元配列を作っていますが、もちろん、この部分も動的確保して構いません。


ジャグ配列は、本当に必要な分だけを確保できるという利点があるため、メモリ使用率の面で効率的です。 C言語の場合、幾つかの可変長な文字列を配列で管理するような場合に、このデータ構造が現れます。 それぞれの文字列の長さが極端に異なる場合、メモリ効率が高まります。

処理効率の良いループ

ここまで、メモリ上で要素がどのように並ぶかに注目してきたのは、処理効率へも関係があるからです。

二次元配列の全ての要素をアクセスする際、次の2通りが考えられます。

int array[10][10];
int i, j;

for( i = 0; i < 10; ++i ){
	for( j = 0; j < 10; ++j ){
		printf( "%d\n", array[i][j];
	}
}
int array[10][10];
int i, j;

for( j = 0; j < 10; ++j ){
	for( i = 0; i < 10; ++i ){
		printf( "%d\n", array[i][j];
	}
}

つまり、右側の添字の値が頻繁に書き換わっていくか、左側の方が頻繁かという違いになります。 配列の大きさや、実行する環境によっても異なりますが、通常は前者の方が実行速度は有利です
これは、現代のコンピュータは、前回参照した場所に近いメモリアドレスを参照する場合、キャッシュという仕組みによって処理速度が向上するからです

詳細に説明するとかなり脱線するので割愛しますが、1度参照したアドレスの近辺は、通常よりも高速に参照できる専用のメモリに情報が書き込まれ、 次回からはそちらを参照することによって高速化します。 「近辺」というのがどの程度の範囲を指すのかは、CPU の性能によって大きく異なります。

実際に、非常に大きな配列を用意して実測してみると、差が出てきます。

#include <stdio.h>
#include <string.h>
#include <time.h>

#define X_SIZE 1024
#define Y_SIZE 1024

int array[Y_SIZE][X_SIZE];

static void processA(void);
static void processB(void);

int main(void)
{
	clock_t begin, end;

	memset( array, 1, sizeof(array) );

	begin = clock();
	processA();
	end = clock();
	printf( "processA: %f seconds\n", (double)(end - begin) / CLOCKS_PER_SEC ); 

	begin = clock();
	processB();
	end = clock();
	printf( "processB: %f seconds\n", (double)(end - begin) / CLOCKS_PER_SEC ); 

	return 0;
}

void processA(void)
{
	int x, y;
	int sum = 0;

	for( y = 0; y < Y_SIZE; ++y ){
		for( x = 0; x < X_SIZE; ++x ){
			sum += array[y][x];
		}
	}

	printf( "%d\n", sum );
}

void processB(void)
{
	int x, y;
	int sum = 0;

	for( x = 0; x < X_SIZE; ++x ){
		for( y = 0; y < Y_SIZE; ++y ){
			sum += array[y][x];
		}
	}

	printf( "%d\n", sum );
}

実行結果:

269484032
processA: 0.002000 seconds
269484032
processB: 0.015000 seconds

processA関数の方は、右側の添字の方が早く変化します。 そのため、連続したメモリアドレスを順番に参照するため、キャッシュの効果によって高速になります。

processB関数の方は、左側の添字の方が早く変化します。 実行結果を見ると、確かにこちらの方が遅いことが分かります。

実際には、配列が小さければ、どのみち配列全体がキャッシュできてしまうため、差が出ないかも知れませんが、 大した労力を割かなくても効率を向上できる場面ですから、このような順序でループを書くことをクセにしておくべきです。

まとめ

多次元配列の基本的な性質は、(一次元の)配列と同様です。 これは、結局のところ、一次元配列が組み合わさって実現されているようにみなせるからです。

多次元配列の実現の仕方によって、メモリ上にどのように配置されるかが異なることを意識すべきです。 近い場所を参照している限り、キャッシュの働きによって高い処理効率が実現できます。


練習問題

問題① 多次元配列で、任意の行を削除する方法を考えて下さい。

問題② ジャグ配列では、各行の要素数が異なるため、何らかの手段を用いないと、要素を順番に辿るときに行の終りが分かりません。 解決方法を考えて下さい。

問題③ 3次元以上の多次元配列について、その性質や利用価値を考えてみて下さい。


解答ページはこちら


参考リンク

更新履歴

'2018/3/29 動的に一次元配列を確保する方法のサンプルプログラムを、C言語編に合わせた形に修正。

'2016/8/10 calloc関数の実引数の順序が逆になっていたのを修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2014/4/19 Perl版のサンプルを削除。

'2011/10/8 各サンプルの Perl版を作成。

'2011/8/14 新規作成。





前の章へ(第1章 配列)

次の章へ(第3章 連結リスト①(単方向・線形))

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS