文字の比較速度

例えば文字列中からスペースを削除したい場合、スペースとみなす文字は ' ' や '\t'、'\n' 等、数種類の文字になることが多い。これら全てについて順番に比較していくと、マッチさせたい文字の種類が増えた時に時間がかかりそうである。
一方、テーブルを用いたアルゴリズムが知られており、文字テスト用の関数で使われている。
試しにどのくらい速度が違うのかテストしてみた。

アルゴリズム

テーブル

char 型は 8 bit であり、256 通りしかない。そこで、要素数 256 の配列を作り、テストにパスするかしないかを格納する。

配列 char flags[256] を作る。入力文字を unsigned char にキャストし、その値を要素番号としてアクセスする。
配列の各要素は 0 または 1 とし、目的の文字がテストにパスするなら 1 を入れた。
複数種類の属性をテストしたいなら、0x01, 0x02, 0x04 などビットマスクにして OR 演算すればよい。

switch()

case ' ': 等でテストにパスする文字用の処理を書く。パスしなかったら default: に飛ぶ。

OR で地道に比較

テストしたい文字を一個ずつ == で比較し、論理 OR で繋ぐ。この方法が遅いことを確認するために、マッチさせたい文字が一個の場合と数個の場合を試した。

実験方法

下に示すコードを書いてビルドし実行した。
stopwatch() は呼び出されるたびに高精度タイマの値を取得し、前回呼び出しとの差を ms 単位で返す。
(UNIX の gettimeofday() 的なもの)

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include "stopwatch.h"

char flags[256] = { 0 };

#define isspace(c) (flags[(unsigned char)(c)])
#define MAXFSIZE 4000000
#define FNAME "test.res"
#define MAXLOOP 10000000

#define MODE   OR2
#define TABLE  1
#define SWITCH 2
#define OR1    3
#define OR2    4

size_t filetostr(const char *fname, char *buf);

size_t filetostr(const char *fname, char *buf)
{
    FILE *fp;
    size_t retval;

    if (fopen_s(&fp, fname, "rt")) {
        printf("Cannot open file %s.\n", fname);
        return 0;
    }
    retval = fread(buf, 1, MAXFSIZE, fp);
    fclose(fp);
    return retval;
}

void main()
{
    char *pos, *end;
    char *str;
    int skip;
    int cnt;
    stopwatch_t timer;
    double d;

    if (!(str = malloc(MAXFSIZE))) exit(0);
    end = str + filetostr(FNAME, str);

    flags[' '] = 1;
    flags['\t'] = 1;
    flags['\n'] = 1;
    flags['#'] = 1;
    flags['0'] = 1;

    stopwatchInit(&timer);
    stopwatch(&timer);

    for (cnt = 0; cnt < MAXLOOP; cnt++) {
        for (skip = 0, pos = str; pos < end; pos++) {

#if MODE == TABLE

            skip = (isspace(*pos));

#elif MODE == SWITCH

            switch (*pos) {
            case ' ':
            case '\t':
            case '\n':
            case '#':
            case '0':
                skip = 1;
                break;
            default:
                skip = 0;
            }

#elif MODE == OR1

            skip = ((*pos == ' ') || (*pos == '\t') || (*pos == '\n') || (*pos == '#') || (*pos == '0'));

#elif MODE == OR2

            skip = (*pos == ' ');

#endif //MODE

        }
    }

    d = stopwatch(&timer);
    putc(skip, stdout);
    printf("Compare done. Mode = %d. Took %f ms.\n", MODE, d);
}

変数 skip の値を putc() で無理矢理出力しているのは、出力しないとコンパイラの最適化により比較ルーチン自体が実行されないため。
MODE 部分を書き換えることでアルゴリズムを選択した。

環境:
CPU: Core i5 2500K (3.3 GHz)
OS: Windows 8.1 JA Pro
コンパイラ: Visual Studio 2014 Express
最適化: /O2 /Oi /GL /Oy- (Release ビルド)

実行時には CPU の SpeedStep を off にしてクロックを固定した。

結果

テーブル
Compare done. Mode = 1. Took 5336.239708 ms.
switch
Compare done. Mode = 2. Took 16526.444090 ms.
OR (いっぱい比較)
Compare done. Mode = 3. Took 17187.036218 ms.
OR (一個だけ比較)
Compare done. Mode = 4. Took 5345.957999 ms.

というわけで、テーブルを用いるとマッチさせたい文字種が増えても速度低下なく比較することができた。