お題にそってプログラミング
最近、何となくですが、お題にそってプログラミングなんていうのが面白いかな、とか思ってます。
色々な人が居るんだなー、とか色々思ったり。
という事で、色々なパターンで書いてみました。
16進文字列から数値を取り出す関数を作りなさい。
ただし、標準ライブラリは使用してはいけないこととする。strlenも駄目
その代わり、[0-9a-fA-F]以外の不正な文字は入力されないこととする。
では回答編は続きを。
1.馬鹿正直法。
int parsehex1 (char *src) { int res = 0; int buf = 0; char *p; for (p = src; *p != 0; p++){ buf = 0; switch (*p){ case '0': buf = 0; break; case '1': buf = 1; break; case '2': buf = 2; break; case '3': buf = 3; break; case '4': buf = 4; break; ....... case 'E': case 'e': buf = 14; break; case 'f': case 'F': buf = 15; break; } res = res * 16 + buf; } return res; }
あり得ない、と思う人も居るかもしれませんが、たまに見ます。
それも中堅ぐらいの人のソースで。
速度重視なのかもしれませんが、どうでしょう。
2.アプリ屋さんにありがちな普通の書き方
int parsehex2 (char *src){ int res = 0; int buf = 0; char *p; for (p = src; *p != 0; p++){ buf = 0; if (*p <= '9' && *p >= '0'){ buf = (int) *p - (int) '0'; }else if (*p <= 'f' && *p >= 'a'){ buf = (int) *p - (int) 'a' + 10; }else if (*p <= 'F' && *p >= 'A'){ buf = (int) *p - (int) 'A' + 10; } res = (res << 4) + buf; } return res; }
規範的ですね。コレは無難です。
可読性もいいし。
3.メモリ富豪 組み込み屋さん 速度がシビアな人。
char table[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*00..0F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*10..1F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*20..3F */ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0, /*30..4F */ 0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*40..5F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*50..6F */ 0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*60..7F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*80..8F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*90..9F */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*A0..AF */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*B0..BF */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*C0..CF */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*D0..DF */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, /*E0..EF */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; /*F0..FF なぜ全部用意するかと言うとはみ出さぬ様に。 */ int parsehex3 (char *src){ int res = 0; char *p; for (p = src; *p != 0; p++){ res = (res << 4) + table[(unsigned char) *p]; } return res; }
昔よく見た手法です。
僕もシビアなときにはたまに使う手法。とにかく早いです。
ただし256バイトのメモリが必要です。
4.解りやすさ派
int parsehex4 (char *src){ int res = 0; int v = 0; char *p; for (p = src; *p != 0; p++){ v = (int) *p; v -= 0x30; //0x30=0なので。 if (v >= 0x10) v -= 7; /*0x41=A なので、41-30-7 */ if (v >= 0x10) v -= 0x20; /*0x61=a なので、41-30-7-20 */ res = (res << 4) + v; } return res; }
これもシンプルですね。
ただ、絶対にifを2回通るので、パフォーマンスが心配です。
5.ifが嫌いすぎて速さを求めてるつもりが逆効果な派
int parsehex5 (char *src){ int res = 0; char *p; for (p = src; *p != 0; p++) res = (res << 4) + (int) *p - 0x30 - (*p >= 0x41) * 7 - ((int) *p >=0x61) * 0x20; return res; }
やり過ぎです。
それに掛け算はよろしくない。ifが悪いと思いすぎてて掛け算のコストを全然考えてないです。
MSX-BASICでは速かったんですけどねぇ
6.ちょっと進化したifが嫌いな人
int parsehex6 (char *src) { int res = 0; char *p; for (p = src; *p != 0; p++) res = (res << 4) + (int) *p - 0x30 - ((*p >= 0x41) ? 7 : 0) - (((int) *p >= 0x61) ? 0x20 : 0); return res; }
三項演算子使ってるだけ酷い。
7.コンパイラが信じられない派
int parsehexa (char *src){ int res = 0; asm (" movl 8(%ebp),%ecx \n\t" " movl $0, %edx \n\t" " movl $0, %eax \n\t" " calc_len: \n\t" " movl $0,%ebx \n\t" " movb (%ecx,%edx),%bl \n\t" " cmpb $0, %bl \n\t" " je exit \n\t" " subb $0x30, %bl \n\t" " cmpb $0x10, %bl \n\t" " jbe calc \n\t" " \n\t" " subb $0x07, %bl \n\t" " cmpb $0x10, %bl \n\t" " jb calc \n\t" " \n\t" " subb $0x20, %bl \n\t" " calc: \n\t" " sall $4, %eax \n\t" " add %ebx,%eax \n\t" " inc %edx \n\t" " jmp calc_len \n\t" " exit: \n\t" " movl %eax,-4(%ebp) "); return res; }
コレはやって良い時と悪い時があります。
百万回ぐらい呼ばれるならやってもいいかもです。
ちなみに、動きますが、久々に書いたので怪しいです。
さて、こんな風に色々組んでみましたが、実際の動きはどうでしょう。
テスト用ルーチンはこちら。
sys/timesとか一通りincludeしてください。
/*テスト用 時間計測*/ double getsec () { struct timeval tv; gettimeofday (&tv, NULL); return tv.tv_sec + (double) tv.tv_usec * 1e-6; } /*テストのメイン*/ int main (char *argc, char **argv) { char *test = "A2cdEfbc"; int (*p[7]) (char *src) = { parsehex1, parsehex2, parsehex3, parsehex4, parsehex5, parsehex6, parsehexa}; char n[7][10] = { "parsehex1", "parsehex2", "parsehex3", "parsehex4", "parsehex5", "parsehex6", "parsehexa" }; int i = 0; long j = 0; unsigned int tmp = 0; int max = 10000000; printf ("test char ->%s\n", test); for (i = 0; i < 7; i++) { printf ("output test...%d (%s)", i, &n[i]); tmp = (*p[i]) (test); printf ("%u \n", tmp); } for (i = 0; i < 7; i++) { double start = getsec (); printf ("loop %d start time (%s)...", i, &n[i]); for (j = 0; j < max; j++) { tmp = (*p[i]) (test); } double sec = getsec () - start; printf ("%f sec )\n", sec); } return 0; }
結果がこちら。
test char ->A2cdEfbc output test...0 (parsehex1)2731405244 output test...1 (parsehex2)2731405244 output test...2 (parsehex3)2731405244 output test...3 (parsehex4)2731405244 output test...4 (parsehex5)2731405244 output test...5 (parsehex6)2731405244 output test...6 (parsehexa)2731405244 loop 0 start time (parsehex1)...1.319381 sec ) loop 1 start time (parsehex2)...0.748295 sec ) loop 2 start time (parsehex3)...0.464418 sec ) loop 3 start time (parsehex4)...0.918671 sec ) loop 4 start time (parsehex5)...0.831350 sec ) loop 5 start time (parsehex6)...0.829392 sec ) loop 6 start time (parsehexa)...0.433116 sec )
非力なマシンでやりましたが、やっぱりベタなswitchは遅い。
次は案外、parsehex4が遅いですね。
if嫌い派も遅い。
やっぱりテーブル作って参照するだけ、parsehex3とかはやたら速い。
無難なparsehex2は無難でいいですね。
そしてアセンブラは異常に速い。
ここで問題です。
parsehex4には遅くなる原因が一つあって、少し改造すればもっと速くなります。
さて、どう修正するでしょう。
