ある文字が文字列で指定された文字種の中に含まれているかどうかという目的であれば、strchr()
は使うべきではないでしょう。というか、
標準Cライブラリに strchr() という関数があります。文字列の先頭から指定した文字を探すという単純な関数なのですが、先日、意外な仕様を知りました。
strchr()
は線形探索なので、文字種が増えれば増えるほど遅くなります。こういう場合は、素直にtable lookupを使うべきでしょう。
実際どれくらい差が出るのか調べてみました。念のために過剰最適化がなされていないことを、gperfで確認してあります。MacBook Pro 2.33GHz, OS X v10.4.11 にて、1億回の繰り返し。
-O0isanychar :0.716349 s (0) isanychar_c :0.790963 s (0) strchr :1.520194 s (0)-O2
isanychar :0.404274 s (0) isanychar_c :0.435982 s (0) strchr :1.494170 s (0)
第二引数で参照文字列を指定すると、strchr()
がO(n)であることを体感できます。
table lookupをcharでやるかbitでやるかは微妙なところで、確かに素直にcharでやった方が高速なのですが、メモリーは8倍。正規表現のcharacter classなど、tableを多用するシーンではbitで、そうでなければcharでやるのがよさそうです。
それにしても、strchr()
って使ったことありませんね。scanf()
とか、結構libcは実地で使えないのも混じってます。最近ではstrfoo()
もbuffer overflowの絡みで使用が戒められていて、strnfoo
、さらにstrlfoo
置き換えるよう推奨されていたり....
誰かlibcの地雷原リスト、作ってくれないかなあ....
Dan the Occasional C Programmer
追記:コメント欄を反映して、strlfoo
を追加。しかし、snprintf()
があるのにslprintf()
はないのね....
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <sys/time.h> double time_hires(){ struct timeval now; gettimeofday(&now, NULL); return now.tv_sec + now.tv_usec/1e6; } typedef char charmask_c[32]; void mkcharmask_c(charmask_c mask, char *chars){ int i, l; for (i = 0, l = sizeof(charmask_c); i < l; i++) mask[i] = '\0'; for (i = 0, l = strlen((char *)chars); i < l; i++) mask[chars[i] >> 3] |= 1 << (chars[i] & 0x7); } int isanychar_c(charmask_c mask, int c){ return mask[c >> 3] & (1 << (c & 0x7)); } typedef char charmask[256]; void mkcharmask(charmask mask, char *chars){ int i, l; for (i = 0, l = sizeof(charmask); i < l; i++) mask[i] = '\0'; for (i = 0, l = strlen((char *)chars); i < l; i++){ mask[(int)chars[i]] = 1; } } int isanychar(charmask mask, int c){ return mask[c]; } int isanychar_s(char *s, int c){ return c != '\0' && strchr(s, c) != NULL; } #define REPEAT 100e6 int main(int argc, char **argv){ int i, bool = 0, repeat = REPEAT; char *chars = "+-*/"; charmask mask; charmask mask_c; double tm, tc, ts; if (argc > 1) repeat = atoi(argv[1]); if (argc > 2) chars = argv[2]; tm = time_hires(); mkcharmask(mask, chars); for (i = 0; i < repeat; i++) bool = isanychar(mask, i & 0xff); tm = time_hires() - tm; printf("isanychar :%.6f s (%d)\n", tm, bool); tc = time_hires(); mkcharmask_c(mask_c, chars); for (i = 0; i < repeat; i++) bool = isanychar_c(mask_c, i & 0xff); tc = time_hires() - tc; printf("isanychar_c :%.6f s (%d)\n", tc, bool); ts = time_hires(); for (i = 0; i < repeat; i++) bool = isanychar_s(chars, i & 0xff); ts = time_hires() - ts; printf("strchr :%.6f s (%d)\n", ts, bool); return 0; }
このブログにコメントするにはログインが必要です。
さんログアウト
この記事には許可ユーザしかコメントができません。