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

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

この章の概要

この章の概要です。


多次元配列

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

次元の数は、添字の個数と一致すると考えます。そのため、通常の配列は一次元配列であるといえます。

多次元配列という場合、厳密にどういう配列のことを指すのかは場合によりけりです。たとえば、C言語においては、次のように宣言された配列は多次元配列と呼ばずに「配列の配列」と呼ぶこともありますが、これも多次元配列と呼ぶことにします。

int array[3][5];

この場合、二次元配列ということになります。一次元配列が、横方向(縦でもいいですが)だけに並んでいるとすると、二次元配列は縦横に並んでいるとイメージできます。

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

array[2][1] = 10;

前章で、メモリ上では、配列の要素が隙間なく連続的に並ぶことを説明しました。多次元配列の場合にも、こうなっているかどうかは重要なポイントです。

結論としては、さきほどのサンプルコードのような方法で宣言した多次元配列は、要素は隙間なく連続的に並びます。

実際に、次のようにしてメモリアドレスを出力してみれば、状況が分かります。

#include <stdio.h>

int main(void)
{
    int array[3][5];

    // 各要素のメモリアドレスを出力
    for( int i = 0; i < 3; ++i ){
        for( int j = 0; j < 5; ++j ){
            printf( "%p\n", &array[i][j] );
        }
        printf( "\n" );
    }

    return 0;
}

実行結果:

000000A0D67DF7D8
000000A0D67DF7DC
000000A0D67DF7E0
000000A0D67DF7E4
000000A0D67DF7E8

000000A0D67DF7EC
000000A0D67DF7F0
000000A0D67DF7F4
000000A0D67DF7F8
000000A0D67DF7FC

000000A0D67DF800
000000A0D67DF804
000000A0D67DF808
000000A0D67DF80C
000000A0D67DF810

連続している要素間が 4Byte ずつ空いているのは、int型が 4Byte の環境で確かめているからです。

動的メモリ割り当てによる方法

多次元配列を実現する方法として、動的メモリ割り当てを使ったものがあります。動的メモリ割り当てを使うと、はじめから要素数を固定しなくて済むため、データの個数が毎回変わってしまうような場面で活用できます。

int* array[3];

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

array は要素数 3 の一次元配列ですが、その要素がポインタになっています。ポインタには、calloc関数で動的確保したメモリ領域が代入されます。

もちろん、malloc関数を使っても問題ありません。

このような方法でも、結果的に二次元配列になっていることがわかるでしょうか。次のように使えます。

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

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

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

    int num = 0;
    for( int i = 0; i < 3; ++i ){
        for( int j = 0; j < 5; ++j ){
            array[i][j] = num;
            ++num;
        }
    }

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

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

    return 0;
}

実行結果:

0 1 2 3 4
5 6 7 8 9
10 11 12 13 14

この方法では、3つのポインタ(最初に宣言した配列の3つの要素)に代入されるのは、3回の calloc関数の呼び出しで得られたメモリアドレスです。calloc関数が返すメモリアドレスは、毎回異なるので、それぞれが連続的なメモリに並ぶ保証がありません。

しかし、calloc関数は連続的に並んだメモリ領域を確保するので、array[0][0]~array[0][4] であるとか、array[1][0]~array[1][4] といった範囲については、連続的に隙間なく並んでいます。

実際に、メモリアドレスを出力してみます。

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

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

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

    // 各要素のメモリアドレスを出力
    for( int i = 0; i < 3; ++i ){
        for( int j = 0; j < 5; ++j ){
            printf( "%p\n", &array[i][j] );
        }
        printf( "\n" );
    }

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

    return 0;
}

実行結果:

000001F4E9804E80
000001F4E9804E84
000001F4E9804E88
000001F4E9804E8C
000001F4E9804E90

000001F4E9804ED0
000001F4E9804ED4
000001F4E9804ED8
000001F4E9804EDC
000001F4E9804EE0

000001F4E980F890
000001F4E980F894
000001F4E980F898
000001F4E980F89C
000001F4E980F8A0

calloc関数で確保された 5個分の要素は連続的なメモリアドレスにありますが、それぞれの組は離れた場所にあることが分かります。

ところで、わざわざこのような方法を採る意味があるのでしょうか?

今回のサンプルプログラムではあまり意味がありませんが、calloc関数の呼び出しのたびに、要求する要素数を変えられることに気付くと、価値がうまれてきます。この話題は、あとであらためて取り上げます

もし、すべての要素が連続的に並んでほしいのであれば、もう1つの方法が使えます。

さきほどのサンプルプログラムと違い、縦横(列と行)の要素を全部まとめて動的に確保します。

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

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

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

    // 各要素のメモリアドレスを出力
    for( int i = 0; i < ARRAY_ROW_NUM; ++i ){
        for( int j = 0; j < ARRAY_COL_NUM; ++j ){
            printf( "%p\n", &array[i * ARRAY_COL_NUM + j] );
        }
        printf( "\n" );
    }

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

    return 0;
}

実行結果:

000001B622E14E80
000001B622E14E84
000001B622E14E88
000001B622E14E8C
000001B622E14E90
000001B622E14E94

000001B622E14E98
000001B622E14E9C
000001B622E14EA0
000001B622E14EA4
000001B622E14EA8
000001B622E14EAC

000001B622E14EB0
000001B622E14EB4
000001B622E14EB8
000001B622E14EBC
000001B622E14EC0
000001B622E14EC4

000001B622E14EC8
000001B622E14ECC
000001B622E14ED0
000001B622E14ED4
000001B622E14ED8
000001B622E14EDC

000001B622E14EE0
000001B622E14EE4
000001B622E14EE8
000001B622E14EEC
000001B622E14EF0
000001B622E14EF4

すべての要素が連続的に並びました。calloc関数の呼び出しが1回だけになったので、このような結果になります。

この方法では、要素を参照するときに工夫が必要です。なぜなら、calloc関数の呼び出しが 1回きりだということは、本来これは一次元配列だからです。次元の数が違ってしまうので、array[3][4] のような方法では参照できません。

そこで、添字を「行番号 × 列の個数 + 列番号」という感じで計算します。array[3][4] を参照したいのなら、array[3 * ARRAY_COL_NUM + 4] という指定になります。


ジャグ配列

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

int* array[3];

for( int 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];

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

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

つまり、右側の添字の値が頻繁に書き換わっていくか、左側の方が頻繁かという違いです。言い換えると、参照するメモリアドレスが連続的に移動するか、そうでないかです。

実行速度の面では、通常は前者の方が有利です

これは、現代のコンピュータにはキャッシュという仕組みがあるからです。詳細な仕組みには踏み込みませんが、結果だけを簡単にいえば、最近参照したメモリアドレスの近くを再び参照するときには、その効率が向上します。

そのため、参照位置が連続的に移動すると、前回の参照位置に近いところを参照し続けるので、効率向上が期待できます。

【上級】キャッシュを実現する手法はいくつかありますが、たとえば、メモリ上のデータを参照するときに、その近辺も巻き込んでキャッシュメモリという場所にデータを書き込んでおきます。キャッシュメモリは、通常のメモリよりも高速にアクセスできるようになっています(その代わり、容量がとても小さい)。次回のアクセスでは、キャッシュメモリの方を参照すれば高速化できるというわけです。

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

#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)
{
    // 適当に初期化
    memset( array, 1, sizeof(array) );

    clock_t begin = clock();
    processA();
    clock_t 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 sum = 0;

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

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

void processB(void)
{
    int sum = 0;

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

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

実行結果:

269484032
processA: 0.003000 seconds
269484032
processB: 0.022000 seconds

processA関数は、右側の添字の方が早く変化し、processB関数は、左側の添字の方が早く変化します。

連続したメモリアドレスを順番に参照できるため、processA関数のほうがキャッシュの恩恵を受けて高速になることが期待できます。実行結果を見ると、確かに processA関数の方が遅いことが分かります。

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

まとめ

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

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


練習問題

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

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

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


解答ページはこちら


参考リンク


更新履歴

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

≪さらに古い更新履歴を展開する≫



前の章へ (第1章 配列)

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

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポストフォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る