トップC言語入門 > 配列をポインタで走査する
配列をポインタで走査する

1.配列をポインタで走査する

配列要素の参照は、例えば、data[n] のように、添え字を使うのが普通である。 C言語ではポインタを使う方法もある。添え字よりもポインタを使う方が実行時間が短縮されることがある。 どの程度の高速化が見込めるかは、プログラムによって大きく異なり、また、 コンパイラおよび実行マシンによっても大きく異なる。

また、コンパイラは標準的な筋の通ったプログラムを基準として、種々の最適化を行う。 このため、コンパイラによっては、ポインタを使うと遅くなる場合がある。 また、素直にポインタを使える場合はいいが、無理にポインタを使うと実行が遅くなる可能性が高くなるので注意がいる。 実際にプログラムを書いて、実行時間を比較して決定するべきである。

ここでは具体例を挙げて説明する。

1.1 配列の中身を反転する

巡回セールスマン問題(TSP. Traveling Salesman Problem)では最適経路を求めるために、 しばしば、部分経路の反転が行われる。経路を配列 Tour で表現した場合、 Tour[bgn] から Tour[end] までの部分経路(bgn < end)を反転するということは、 Tour[bgn] と Tour[end] を交換、Tour[bgn+1] と Tour[end-1] を交換、中間点まで繰り返せばよい。

添え字を使う場合には、Reverse関数を次のように記述する。

void Reverse(int Tour[], int b, int e) {
    while (b < e) {
        int tmp = Tour[b];
        Tour[b++] = Tour[e];
        Tour[e--] = tmp;
    }
}

関数の呼び出しは Reverse(Tour, bgn, end) とする。

一方、ポインタを使う場合には次のように記述する。

void Reverse(int *b, int *e) {
    while (b < e) {
        int tmp = *b;
        *b++ = *e;
        *e-- = tmp;
    }
}

関数の呼び出しは Reverse(&Tour[bgn], &Tour[end]) とする。

両者の実行時間を次のプログラムで比較する。

#include <stdio.h>
#include <time.h>                           // clock()

#define NUM    1000
int     Tour[NUM];  

void ReverseI(int Tour[], int b, int e) {
    while (b < e) {
        int tmp = Tour[b];
        Tour[b++] = Tour[e];
        Tour[e--] = tmp;
    }
}

void ReverseP(int *b, int *e) {
    while (b < e) {
        int tmp = *b;
        *b++ = *e;
        *e-- = tmp;
    }
}

int main() {
    clock_t bgn, end, time;

    for (int n = 0; n < NUM; n++) {
        Tour[n] = n;
    }

    bgn = clock();
    for (int k = 0; k < 1000000; k++) {
        ReverseI(Tour, NUM/3, NUM*2/3);
    }
    end = clock();
    printf("添 え 字 %.3f秒\n", (double)(end-bgn)/CLOCKS_PER_SEC);

    bgn = clock();
    for (int k = 0; k < 1000000; k++) {
        ReverseP(&Tour[NUM/3], &Tour[NUM*2/3]);
    }
    end = clock();
    printf("ポインタ %.3f秒\n", (double)(end-bgn)/CLOCKS_PER_SEC);
}

GCC および MS VC(cl.exe) でコンパイル・実行した結果を下に示す。

c:\sys>gcc  -std=c99 reverse.c

c:\sys>a
添 え 字 2.035秒
ポインタ 1.926秒

c:\sys>cl reverse.c /nologo
reverse.c

c:\sys>reverse
添 え 字 2.277秒
ポインタ 1.939秒

VC では、添え字よりポインタを使う方が 17% 高速であるが、GCC での高速化効果は小さい。

VC では register 宣言をしても無視され、変数のレジスタ割り当てはないため、実行速度は変わらないが、 GCCの場合、tmpおよび全引数に register指定子を付けてコンパイル・実行すると、 下に示すように大幅な高速化が図れた。特にポインタを使った場合には約3倍もの高速化が図れた。

c:\sys>a
添 え 字 1.320秒
ポインタ 0.668秒

cl.exeは Microsoft Visual Studio 12.0 に含まれるC・C++コマンドライン・コンパイラ Version 18.00.31101 for x86 であり、 GCCは MinGWに含まれるものでバージョン 4.8.1 を用いた。

また、プロセッサは Intel Core i5-3337U CPU 1.80 GHz、 実装メモリは 4.00 GB である。

Reference

[1] アセンブリ言語:最適化
[2] インライン・アセンブラ