C isupper()函数
我目前正在阅读“C编程语言第2版”,我不清楚这个练习:
可以实现像isupper这样的函数以节省空间或节省时间。 探索两种可能性。
- 我该如何实现这个function?
- 我应该如何编写两个版本,一个用于节省时间,另一个用于节省空间(一些伪代码会很好)?
我很感激有关这方面的一些建议。
原始答案
一个版本使用一个用适当的值初始化的数组,代码集中每个字符一个字节(加1以允许EOF,也可以传递给分类函数):
static const char bits[257] = { ...initialization... }; int isupper(int ch) { assert(ch == EOF || (ch >= 0 && ch <= 255)); return((bits+1)[ch] & UPPER_MASK); }
请注意,'bits'可以被所有各种函数使用,例如isupper()
, islower()
, isalpha()
等,并且具有适当的掩码值。 如果在运行时使'bits'数组可以更改,则可以适应不同的(单字节)代码集。
这需要空间 - 数组。
另一个版本假设有关大写字符的连续性,以及有限的有效大写字符集(对于ASCII很好,对ISO 8859-1或其亲属不太好):
int isupper(int ch) { return (ch >= 'A' && ch <= 'Z'); // ASCII only - not a good implementation! }
这可以(几乎)在宏中实现; 很难避免两次评估字符,这在标准中实际上是不允许的。 使用非标准(GNU)扩展,它可以实现为只评估一次字符参数的宏。 要将其扩展到ISO 8859-1,则需要第二个条件,即:
int isupper(int ch) { return ((ch >= 'A' && ch <= 'Z')) || (ch >= 0xC0 && ch <= 0xDD)); }
经常重复这个宏作为宏,并且'节省空间'迅速成为成本,因为位掩码具有固定的大小。
鉴于现代代码集的要求,映射版本几乎总是在实践中使用; 它可以在运行时适应当前的代码集等,基于范围的版本不能。
扩展答案
我仍然无法弄清楚UPPER_MASK的工作原理。 你能更具体地解释一下吗?
忽略标头中符号的命名空间问题,您有一系列十二个分类宏:
-
isalpha()
-
isupper()
-
islower()
-
isalnum()
-
isgraph()
-
isprint()
-
iscntrl()
-
isdigit()
-
isblank()
-
isspace()
-
ispunct()
-
isxdigit()
isspace()
和isblank()
之间的区别是:
-
isspace()
- 空格(' '
),换页('\f'
),换行符('\n'
),回车符('\r'
),水平制表符('\t'
)和垂直制表符('\v'
) 。 -
isblank()
- 空格(' '
)和水平制表符('\t'
) 。
C标准中有这些字符集的定义,以及C语言环境的指南。
例如(在C语言环境中),如果isalpha()
为true,则islower()
或isupper()
isalpha()
为true,但在其他语言环境中不需要为true。
我认为必要的部分是:
-
DIGIT_MASK
-
XDIGT_MASK
-
ALPHA_MASK
-
LOWER_MASK
-
UPPER_MASK
-
PUNCT_MASK
-
SPACE_MASK
-
PRINT_MASK
-
CNTRL_MASK
-
BLANK_MASK
从这十个面具中,您可以创建另外两个:
- ALNUM_MASK = ALPHA_MASK | DIGIT_MASK
- GRAPH_MASK = ALNUM_MASK | PUNCT_MASK
表面上,您还可以使用ALPHA_MASK = UPPER_MASK | LOWER_MASK
ALPHA_MASK = UPPER_MASK | LOWER_MASK
,但在某些语言环境中,有字母字符既不是大写字母也不是小写字母。
所以,我们可以定义掩码如下:
enum CTYPE_MASK { DIGIT_MASK = 0x0001, XDIGT_MASK = 0x0002, LOWER_MASK = 0x0004, UPPER_MASK = 0x0008, ALPHA_MASK = 0x0010, PUNCT_MASK = 0x0020, SPACE_MASK = 0x0040, PRINT_MASK = 0x0080, CNTRL_MASK = 0x0100, BLANK_MASK = 0x0200, ALNUM_MASK = ALPHA_MASK | DIGIT_MASK, GRAPH_MASK = ALNUM_MASK | PUNCT_MASK }; extern unsigned short ctype_bits[];
字符集的数据; 显示的数据是ISO 8859-1的前半部分,但是对于所有8859-x代码集的前半部分是相同的。 我正在使用C99指定的初始化程序作为纪录片辅助工具,即使这些条目都是有序的:
unsigned short ctype_bits[] = { [EOF +1] = 0, ['\0' +1] = CNTRL_MASK, ['\1' +1] = CNTRL_MASK, ['\2' +1] = CNTRL_MASK, ['\3' +1] = CNTRL_MASK, ['\4' +1] = CNTRL_MASK, ['\5' +1] = CNTRL_MASK, ['\6' +1] = CNTRL_MASK, ['\a' +1] = CNTRL_MASK, ['\b' +1] = CNTRL_MASK, ['\t' +1] = CNTRL_MASK|SPACE_MASK|BLANK_MASK, ['\n' +1] = CNTRL_MASK|SPACE_MASK, ['\v' +1] = CNTRL_MASK|SPACE_MASK, ['\f' +1] = CNTRL_MASK|SPACE_MASK, ['\r' +1] = CNTRL_MASK|SPACE_MASK, ['\x0E'+1] = CNTRL_MASK, ['\x0F'+1] = CNTRL_MASK, ['\x10'+1] = CNTRL_MASK, ['\x11'+1] = CNTRL_MASK, ['\x12'+1] = CNTRL_MASK, ['\x13'+1] = CNTRL_MASK, ['\x14'+1] = CNTRL_MASK, ['\x15'+1] = CNTRL_MASK, ['\x16'+1] = CNTRL_MASK, ['\x17'+1] = CNTRL_MASK, ['\x18'+1] = CNTRL_MASK, ['\x19'+1] = CNTRL_MASK, ['\x1A'+1] = CNTRL_MASK, ['\x1B'+1] = CNTRL_MASK, ['\x1C'+1] = CNTRL_MASK, ['\x1D'+1] = CNTRL_MASK, ['\x1E'+1] = CNTRL_MASK, ['\x1F'+1] = CNTRL_MASK, [' ' +1] = SPACE_MASK|PRINT_MASK|BLANK_MASK, ['!' +1] = PUNCT_MASK|PRINT_MASK, ['"' +1] = PUNCT_MASK|PRINT_MASK, ['#' +1] = PUNCT_MASK|PRINT_MASK, ['$' +1] = PUNCT_MASK|PRINT_MASK, ['%' +1] = PUNCT_MASK|PRINT_MASK, ['&' +1] = PUNCT_MASK|PRINT_MASK, ['\'' +1] = PUNCT_MASK|PRINT_MASK, ['(' +1] = PUNCT_MASK|PRINT_MASK, [')' +1] = PUNCT_MASK|PRINT_MASK, ['*' +1] = PUNCT_MASK|PRINT_MASK, ['+' +1] = PUNCT_MASK|PRINT_MASK, [',' +1] = PUNCT_MASK|PRINT_MASK, ['-' +1] = PUNCT_MASK|PRINT_MASK, ['.' +1] = PUNCT_MASK|PRINT_MASK, ['/' +1] = PUNCT_MASK|PRINT_MASK, ['0' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['1' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['2' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['3' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['4' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['5' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['6' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['7' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['8' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, ['9' +1] = DIGIT_MASK|PRINT_MASK|XDIGT_MASK, [':' +1] = PUNCT_MASK|PRINT_MASK, [';' +1] = PUNCT_MASK|PRINT_MASK, ['<' +1] = PUNCT_MASK|PRINT_MASK, ['=' +1] = PUNCT_MASK|PRINT_MASK, ['>' +1] = PUNCT_MASK|PRINT_MASK, ['?' +1] = PUNCT_MASK|PRINT_MASK, ['@' +1] = PUNCT_MASK|PRINT_MASK, ['A' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['B' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['C' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['D' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['E' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['F' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK|XDIGT_MASK, ['G' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['H' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['I' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['J' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['K' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['L' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['M' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['N' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['O' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['P' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['Q' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['R' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['S' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['T' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['U' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['V' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['W' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['X' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['Y' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['Z' +1] = ALPHA_MASK|UPPER_MASK|PRINT_MASK, ['[' +1] = PUNCT_MASK|PRINT_MASK, ['\\' +1] = PUNCT_MASK|PRINT_MASK, [']' +1] = PUNCT_MASK|PRINT_MASK, ['^' +1] = PUNCT_MASK|PRINT_MASK, ['_' +1] = PUNCT_MASK|PRINT_MASK, ['`' +1] = PUNCT_MASK|PRINT_MASK, ['a' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['b' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['c' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['d' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['e' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['f' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK|XDIGT_MASK, ['g' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['h' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['i' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['j' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['k' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['l' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['m' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['n' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['o' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['p' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['q' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['r' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['s' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['t' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['u' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['v' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['w' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['x' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['y' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['z' +1] = ALPHA_MASK|LOWER_MASK|PRINT_MASK, ['{' +1] = PUNCT_MASK|PRINT_MASK, ['|' +1] = PUNCT_MASK|PRINT_MASK, ['}' +1] = PUNCT_MASK|PRINT_MASK, ['~' +1] = PUNCT_MASK|PRINT_MASK, ['\x7F'+1] = CNTRL_MASK, ...continue for second half of 8859-x character set... }; #define isalpha(c) ((ctype_bits+1)[c] & ALPHA_MASK) #define isupper(c) ((ctype_bits+1)[c] & UPPER_MASK) #define islower(c) ((ctype_bits+1)[c] & LOWER_MASK) #define isalnum(c) ((ctype_bits+1)[c] & ALNUM_MASK) #define isgraph(c) ((ctype_bits+1)[c] & GRAPH_MASK) #define isprint(c) ((ctype_bits+1)[c] & PRINT_MASK) #define iscntrl(c) ((ctype_bits+1)[c] & CNTRL_MASK) #define isdigit(c) ((ctype_bits+1)[c] & DIGIT_MASK) #define isblank(c) ((ctype_bits+1)[c] & BLANK_MASK) #define isspace(c) ((ctype_bits+1)[c] & SPACE_MASK) #define ispunct(c) ((ctype_bits+1)[c] & PUNCT_MASK) #define isxdigit(c) ((ctype_bits+1)[c] & XDIGT_MASK)
如前所述,这里的名称实际上位于为用户保留的命名空间中,因此如果查看
标题,您会发现更多含义模糊的名称,并且它们可能都以一个或两个下划线开头。
经典的权衡是速度与内存:要么计算结果,要么在表格中查找。
对于isupper()
函数,要弄清楚它们的外观应该不难。
在今天的主流CPU中,有些事情可能意外地复杂化:s,但是:
假设一个8位char
,一个支持ASCII的表需要128位,如果你不想自己屏蔽最高位,则需要256位。 这只是32个字节,但这可能仍然比利用ASCII映射的顺序性质的代码更多。 大代码大小通常对性能不利,因为它会影响缓存效率,并且通常会暴露当今CPU与其内存子系统之间的大量带宽差异。
使用显式比较来计算结果而不利用顺序映射的代码将非常大,比相应的查找表大。 这不典型; 在计算值的代码比查找表更紧凑的情况下,更容易看出速度与内存权衡的差异。
一种方法可以与’A’,’Z’进行一些比较。
另一种方法可以使用预先计算的查找表。
这是维基百科页面上提到的关于时空权衡的第一个建议。
实际上,您可以节省空间和时间。 大写字符在ASCII表中是连续的,所以你只需要这样做(这显然不能处理语言环境,但我怀疑这是你的练习点):
BOOL isUpper(char c) { return (c >= 'A' && c <= 'Z'); }
大写字符是ASCIIhex0x41到0x5A。 这意味着始终设置位0x40。 如果您确定参数是ASCII字符,则可以返回:
(c&0x40);