【转帖】谈isdigit(c)函数的实现效率

huangyhg

谈isdigit(c)函数的实现效率

看到CSDN首页一篇blog——判断一个字符串是否全是数字的多种方法及其性能比较（C#实现） 。文中提到的算法暂不议论，单单看回复——一个网友指责楼主使用Char.IsNumber(str,i)的效率不如(r<'0' || str>'9')这种方法高，楼主连声表示认同——真的令我感慨万分，隔行如隔山呀。这话怎么说？C#这种不开源的语言使多少人对其实现产生了误解，我不是说C#程序员对效率算法研究不及C程序员，我是想说开源的ANSI C绝对能使程序员更准确的理解其实现的本质，从而不会错用、误用代码而不自知。

我对C#实现理解不深，因此我来谈谈C中诸如isdigit(c)、isalpha(c)之类函数的实现，借而推断上述讨论的正确性。

很多初学者都认为isalnum(c)是这样写的(我最初也是这么人为的)：

inline int isdigit(char c){ return c>='0'&&c<'9';}我当初甚至认为，这种写法已经是非常高效了。直到某一天我开始学习Linux kernel source，我才真正见识了前辈的高效算法，真的眩的令人膛目结舌。下面这段代码摘自Linux 0.11 kernel，大家看看再说

0 /*
0 * linux/lib/ctype.h
0 *
1 * (C) 1991 Linus Torvalds
2 */
3
4 #define _U 0x01 /* upper */
5 #define _L 0x02 /* lower */
6 #define _D 0x04 /* digit */
7 #define _C 0x08 /* cntrl */
8 #define _P 0x10 /* punct */
9 #define _S 0x20 /* white space (space/lf/tab) */
10 #define _X 0x40 /* hex digit */
11 #define _SP 0x80 /* hard space (0x20) */
12
13 extern unsigned char _ctype[];
14 extern char _ctmp;
15
16 #define isalnum(c) ((_ctype+1)[c]&(_U|_L|_D))
17 #define isalpha(c) ((_ctype+1)[c]&(_U|_L))
18 #define iscntrl(c) ((_ctype+1)[c]&(_C))
19 #define isdigit(c) ((_ctype+1)[c]&(_D))
20 #define isgraph(c) ((_ctype+1)[c]&(_P|_U|_L|_D))
21 #define islower(c) ((_ctype+1)[c]&(_L))
22 #define isprint(c) ((_ctype+1)[c]&(_P|_U|_L|_D|_SP))
23 #define ispunct(c) ((_ctype+1)[c]&(_P))
24 #define isspace(c) ((_ctype+1)[c]&(_S))
25 #define isupper(c) ((_ctype+1)[c]&(_U))
26 #define isxdigit(c) ((_ctype+1)[c]&(_D|_X))
27
28 #define isascii(c) (((unsigned) c)<=0x7f)
29 #define toascii(c) (((unsigned) c)&0x7f)
30
31 #define tolower(c) (_ctmp=c,isupper(_ctmp)?_ctmp-('A'-'a'):_ctmp)
32 #define toupper(c) (_ctmp=c,islower(_ctmp)?_ctmp-('a'-'A'):_ctmp)
33
34 #endif
35

1 /*
2 * linux/lib/ctype.c
3 *
4 * (C) 1991 Linus Torvalds
5 */
6
7 #include <ctype.h>
8
9 char _ctmp;
10 unsigned char _ctype[] = {0x00, /* EOF */
11 _C,_C,_C,_C,_C,_C,_C,_C, /* 0-7 */
12 _C,_C|_S,_C|_S,_C|_S,_C|_S,_C|_S,_C,_C, /* 8-15 */
13 _C,_C,_C,_C,_C,_C,_C,_C, /* 16-23 */
14 _C,_C,_C,_C,_C,_C,_C,_C, /* 24-31 */
15 _S|_SP,_P,_P,_P,_P,_P,_P,_P, /* 32-39 */
16 _P,_P,_P,_P,_P,_P,_P,_P, /* 40-47 */
17 _D,_D,_D,_D,_D,_D,_D,_D, /* 48-55 */
18 _D,_D,_P,_P,_P,_P,_P,_P, /* 56-63 */
19 _P,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U|_X,_U, /* 64-71 */
20 _U,_U,_U,_U,_U,_U,_U,_U, /* 72-79 */
21 _U,_U,_U,_U,_U,_U,_U,_U, /* 80-87 */
22 _U,_U,_U,_P,_P,_P,_P,_P, /* 88-95 */
23 _P,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L|_X,_L, /* 96-103 */
24 _L,_L,_L,_L,_L,_L,_L,_L, /* 104-111 */
25 _L,_L,_L,_L,_L,_L,_L,_L, /* 112-119 */
26 _L,_L,_L,_P,_P,_P,_P,_C, /* 120-127 */
27 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 128-143 */
28 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 144-159 */
29 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 160-175 */
30 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 176-191 */
31 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 192-207 */
32 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 208-223 */
33 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, /* 224-239 */
34 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; /* 240-255 */
35
36


此一段代码一看便知高下。^_^

我不认为C#的构架师是个笨笨，决计做不出来一个用大家反复调用的底层API函数还不及一段用户组合代码效率高的蠢事来，所以我认为“Char.IsNumber(str,i)的效率不如(r<'0' || str>'9')”绝对是个谬论！



-------------
乾坤一笑 写于2005年1月19日 转载请标明出处和原文链接


posted on 2005-01-19 12:58 乾坤一笑 阅读(7107) 评论(21) 编辑 收藏


Comments
# re: 谈isalnum(c)函数的实现效率
[url="http://blog.vckbase.com/bruceteen"]周星星
全文顶一下，另外“我是想说开源的ANSI C绝对能使程序员更准确的理解其实现的本质，从而不会错用、误用代码而不自知。”更要顶一下，很多时候俺也是查看实现源代码才知道怎么用。
Posted @ 2005-01-19 22:27

# re: 谈isdigit(c)函数的实现效率
茹枫
源代码是什么东西，我要查看机器码才知道他的本质
Posted @ 2005-01-20 00:34

# to : 茹枫
一笑
有时候门电路和电子迁移也是需要研究一下的，当然你要是能研究原子核物理或质子、夸子之类的就更了不得了。 ^_^
Posted @ 2005-01-20 00:55

# re: 谈isdigit(c)函数的实现效率
七猫
空间换效率，
Posted @ 2005-01-20 01:23

# re: 谈isdigit(c)函数的实现效率
shell909090
经过刚刚实际测试，VC++6.0&win2k编译环境下，编译器自动去除了inline前缀。所以改用宏的方法测试，得到结果如下。
#define isdigit(c) ((c)>='0'&&(c)<'9')
10: bool a=isdigit(c);
0040103C movsx eax,byte ptr [ebp-4]
00401040 cmp eax,30h
00401043 jl main+37h (00401057)
00401045 movsx ecx,byte ptr [ebp-4]
00401049 cmp ecx,39h
0040104C jge main+37h (00401057)
0040104E mov dword ptr [ebp-0Ch],1
00401055 jmp main+3Eh (0040105e)
00401057 mov dword ptr [ebp-0Ch],0
0040105E mov dl,byte ptr [ebp-0Ch]
00401061 mov byte ptr [ebp-8],dl

#define isdigit(c) ((_ctype+1)[c]&(_D))
29: bool a=isdigit(c);
0040103C movsx eax,byte ptr [ebp-4]
00401040 xor ecx,ecx
00401042 mov cl,byte ptr _ctype+1 (00422301)[eax]
00401048 and ecx,4
0040104B neg ecx
0040104D sbb ecx,ecx
0040104F neg ecx
00401051 mov byte ptr [ebp-8],cl

总共节省了三条指令。

实际如果精简代码，则可以达到九条指令的状态，大致如下：
#define isdigit(c) ((c)>='0'&&(c)<'9')
10: bool a=isdigit(c);
0040103C movsx eax,byte ptr [ebp-4]
00401040 cmp eax,30h
00401043 jl main+37h (00401057)
00401049 cmp eax,39h
0040104C jge main+37h (00401057)
0040104E mov dl,1
00401055 jmp main+3Eh (0040105e)
00401057 mov dl,0
00401061 mov byte ptr [ebp-8],dl

可以看出，两者效率的差异仅仅在一两条指令上，仅仅是编写小型程序并不值得。不过如果是大规模定义此类宏，又有很多非连续的（例如Hex）。那么后者显然值得这些代价。
Posted @ 2005-01-20 14:06

# 隔行如隔山！
fancyf
楼主，我是《判断一个字符串是否全是数字的多种方法及其性能比较（C#实现）》一文的作者，先不说我那篇文章的水平怎么样（其实已经遭到了很多批评），我但就你这篇文章谈一下看法。
首先，C#不是C，而楼主却把两者混为一潭。既然楼主承认“我对C#实现理解不深”，却又怎么敢由“C中诸如isdigit(c)、isalpha(c)之类函数的实现”来推断““Char.IsNumber(str,i)的效率不如(r<'0' || str>'9')”绝对是个谬论！”呢？你怎么知道Char.IsNumber(str,i)是通过调用isdigit(char c)来写的呢？你的猜测错了，根本就不是。我通过Reflactor对Framework进行了反编译，得到了Char.IsNumber的实现（用微软提供的ildasm可以得到IL的代码，结论是一样的）：
这是Char.IsNumber(string,int)的实现：
public static bool IsNumber(string s, int index)
{
if (s == null)
{
throw new ArgumentNullException("s");
}
if (index >= s.Length)
{
throw new ArgumentOutOfRangeException("index");
}
return char.IsNumber(s[index]);
}

被调用的char.IsNumber(char)实现如下：
public static bool IsNumber(char c)
{
return CharacterInfo.IsNumber(c);
}

继续追踪，CharacterInfo.IsNumber(c)的实现：
public static bool IsNumber(char ch)
{
UnicodeCategory category1 = CharacterInfo.GetUnicodeCategory(ch);
if ((category1 != UnicodeCategory.DecimalDigitNumber) && (category1 != UnicodeCategory.LetterNumber))
{
return (category1 == UnicodeCategory.OtherNumber);
}
return true;
}

继续，CharacterInfo.GetUnicodeCategory(ch)的实现：
public static UnicodeCategory GetUnicodeCategory(char ch)
{
return CharacterInfo.InternalGetUnicodeCategory(ch);
}

还有，CharacterInfo.InternalGetUnicodeCategory(ch)的实现：
internal static unsafe UnicodeCategory InternalGetUnicodeCategory(char ch)
{
byte num1 = CharacterInfo.m_pDataTable[ch >> 8];
ushort num2 = CharacterInfo.m_pLevel2WordOffset[(num1 << 4) + ((ch >> 4) & '\x000f')];
byte num3 = CharacterInfo.m_pDataTable[num2 + (ch & '\x000f')];
return (UnicodeCategory) num3;
}

好了，终于结束了。一个Char.IsNumber(str,i)就是通过上面的一系列调用来实现的，你说效率如何？如果不信可以自己去验证。

Char.IsNumber(str,i)判断的是Unicode字符，而不仅仅是ASCII字符，我在你批判的那篇文章中也提到了，Char.IsNumber(str,i)可以判断全角的１，所以调用是麻烦了一些，不过功能是增加了。可见，楼主的批判是毫无道理的。
Posted @ 2005-01-21 23:11

# .NET和Linux，怎么说呢！就是不同抽象层次的问题！[TrackBack]
lxutao
Ping Back来自：blog.csdn.net
lxutao引用了该文章,地址:http://blog.csdn.net/lxutao/archive/2005/01/21/262305.aspx
Posted @ 2005-01-21 11:44

# re: 谈isdigit(c)函数的实现效率
lxutao
大家都知道现在Delphi之父在哪里吧。
《Borland传奇》应该也看过吧，Compiler可能在校学的人不多！

只是通过Reflector去分析的话，我想这样也不稳妥。
我们能看到的只是ildasm，到了底层，会是什么样子呢？

在Borland C 31下面可以把一个C程序编译成一个asm文件，我们可以分析它。
在Linux下面我们编译起来可能更方便，资料也很多，就是AT&T的汇编可能平时接触的少。
Posted @ 2005-01-26 08:16

# to fancyf :
一笑
我手头上没有.NET环境，你能不能帮忙贴一下public static bool IsNumber(char ch) 中调用的UnicodeCategory.DecimalDigitNumber 和UnicodeCategory.LetterNumber 属性的实现机理？就是说UnicodeCategory这个类(或结构)如何实现判断自身是不是一个DecimailDigitNumber和LetterNumber的？我想我本文讨论的主题也仅在于此。

Posted @ 2005-01-28 20:26

# re: 谈isdigit(c)函数的实现效率
rovershen
呵呵，我没有对编译器做过研究，不过这个效率值得讨论么？如何那几条指令的时间真的影响了执行效率，自己写代码是不是更有效率？不论是cisc还是risc，地址跳转是最需要时间的，其间还要传递参数。。。
Posted @ 2005-02-08 01:17

# re: 谈isdigit(c)函数的实现效率
jinzhong
支持一下。
Posted @ 2005-03-23 15:41

# re: 谈isdigit(c)函数的实现效率
血刀门
无论如何，C#写出来的程序绝对不如效率高。
如了汇编，效率高的其次就是C了。

更何况C#的还是解释型的呢，不信可以找个C#程序的反编译
程序来把C#的可执行程序转成源代码，输出还很漂亮呢。

就像VB3.0,VB4.0一样。

我天天写汇编。谁有效率谁没效率生出来的汇编代码最能说明问题。
Posted @ 2005-04-07 08:57

# 用Char.IsNumber()能否判断Char是不是数字？ [TrackBack]
lxutao
先说答案，不行。
大家都知道数字有全角和半角，如果有Str=“123１２３”。 则判断是数字。 //但是后面的１２３是全角。在dotnet中使用unicode，感觉用它自己带的函数有问题，很多情况还是自己判断的好。...
lxutao引用了该文章,地址:http://qihang.net/blogs/lxutao/archive/2005/07/12/554.aspx
Posted @ 2005-07-12 06:49

# re: 谈isdigit(c)函数的实现效率
fancyf
TO LXUTAO:
我在原文章以及前面回复的最后一句话都提到这个问题了
Posted @ 2005-07-13 21:56

# re: 谈isdigit(c)函数的实现效率
longrid
这个是标准库函数，是个宏定义
Posted @ 2005-09-08 13:45

# re: 谈isdigit(c)函数的实现效率
qwerty
II bez</a> II

[url="http://blog.vckbase.com/smileonce/archive/2005/01/19/2703.html#28557"]# xdzbhycd
xdzbhycd
# xxqqjnlk
xxqqjnlk
uhezjgsd
Posted @ 2007-08-16 23:42

# xxqqjnlk
xxqqjnlk
uhezjgsd
Posted @ 2007-08-16 23:44

# re: 谈isdigit(c)函数的实现效率
qrlvls
我以前曾经想用汇编指令优化浮点运算，结果轻易地被编译器优化给b4了，汇编已成历史，厌烦楼上有人回复拿汇编说事
Posted @ 2007-08-29 11:16

# re: 谈isdigit(c)函数的实现效率
qrlvls
当时用的全是协处理器指令，不过万般辛苦终不如编译器/O2
Posted @ 2007-08-29 11:17