C言語 - 文字列を高速に連結する

C言語 - 文字列を高速に連結する

ことりと /

2023/10/7 02:40 | 1275 文字

strcat 関数で文字列を連結するとき、連結先の文字列が長いと性能が落ちてしまう。

それは連結先のNULL文字の位置から文字列を連結するという strcat 関数の動きが原因となっている。

要はNULL文字を探す時間がボトルネックとなるわけだ。

まずは連結先の文字列が長くなると、本当に処理時間がかかるのか確かめてみたい。

以下は変数 buf が 1MB になるまで10バイトずつ文字列を連結していくプログラム。

char buf[1000000 + 1];

start_clock = clock();

for (i = 0; i < 100000; i++) {
    strcat(buf, "ABCDEFGHIJ");

    // 100KB連結する毎にかかった時間を計測
    if ((i + 1) % 10000 == 0) {
        end_clock = clock();
        printf("time=%f, buf_length=%i\n", (double)(end_clock - start_clock) / CLOCKS_PER_SEC, strlen(buf));
        start_clock = end_clock;
    }
}

全体の処理時間は約9秒だった。

そして想定したとおり、変数 buf の文字数に比例して連結時間が増えている。

変数 buf の文字数	100KB毎の連結時間（秒）
～ 100000	0.163
～ 200000	0.450
～ 300000	0.575
～ 400000	0.636
～ 500000	0.827
～ 600000	0.946
～ 700000	1.125
～ 800000	1.432
～ 900000	1.472
～ 1000000	1.649

文字列を高速に連結するには strcat 関数の代わりに、ポインタと strcpy 関数を使う。

時間がかかる原因は、 strcat 関数が毎回NULL文字を探すからだった。

なので、NULL文字を探さなくて済むよう、ポインターの指す位置に文字列をコピーしたあと、その文字数分ポインターを進める手を取る。

char buf[1000000 + 1];

// ポインターに buf の先頭アドレスを入れる
char *p = buf;

start_clock = clock();

for (i = 0; i < 100000; i++) {
    // ポインターの指す位置に文字列をコピー
    strcpy(p, "ABCDEFGHIJ");
    // コピーした文字数分、ポインターを進める
    p += strlen("ABCDEFGHIJ");

    // 100KB連結する毎にかかった時間を計測
    if ((i + 1) % 10000 == 0) {
        end_clock = clock();
        printf("time=%f, buf_length=%i\n", (double)(end_clock - start_clock) / CLOCKS_PER_SEC, strlen(buf));
        start_clock = end_clock;
    }
}

ポインタと strcpy 関数を使うようにしたプログラムは0.008秒で済んだ。

なお、100KB毎の連結にかかった時間は1ミリ秒や2ミリ秒だったので掲載省略。

strcat 関数は使いどころを考えて。