Función C isupper ()

Actualmente estoy leyendo “The C Programming Language 2nd edition” y no tengo claro este ejercicio:

Se pueden implementar funciones como isupper para ahorrar espacio o para ahorrar tiempo. Explora ambas posibilidades.

  • ¿Cómo puedo implementar esta función?
  • ¿Cómo debo escribir dos versiones, una para ahorrar tiempo y otra para ahorrar espacio (algún pseudo código sería bueno)?

Apreciaría algún consejo sobre esto.

Respuesta original

Una versión usa una matriz inicializada con los valores apropiados, un byte por carácter en el conjunto de códigos (más 1 para permitir EOF, que también se puede pasar a las funciones de clasificación):

static const char bits[257] = { ...initialization... }; int isupper(int ch) { assert(ch == EOF || (ch >= 0 && ch <= 255)); return((bits+1)[ch] & UPPER_MASK); } 

Tenga en cuenta que los 'bits' pueden ser utilizados por todas las funciones como isupper() , islower() , isalpha() , etc. con los valores adecuados para la máscara. Y si hace que la matriz de 'bits' se pueda cambiar en el tiempo de ejecución, puede adaptarse a diferentes conjuntos de códigos (de un solo byte).

Esto toma espacio - la matriz.

La otra versión hace suposiciones sobre la continuidad de los caracteres en mayúsculas y también sobre el conjunto limitado de caracteres en mayúsculas válidos (multa para ASCII, no tan buena para ISO 8859-1 o sus parientes):

 int isupper(int ch) { return (ch >= 'A' && ch <= 'Z'); // ASCII only - not a good implementation! } 

Esto puede (casi) implementarse en una macro; es difícil evitar la evaluación del personaje dos veces, lo que en realidad no está permitido en la norma. Usando extensiones no estándar (GNU), puede implementarse como una macro que evalúa el argumento de carácter solo una vez. Para extender esto a ISO 8859-1 se requeriría una segunda condición, en la línea de:

 int isupper(int ch) { return ((ch >= 'A' && ch <= 'Z')) || (ch >= 0xC0 && ch <= 0xDD)); } 

Repítalo muy a menudo como macro y el "ahorro de espacio" se convierte rápidamente en un costo, ya que el enmascaramiento de bits tiene un tamaño fijo.

Dados los requisitos de los conjuntos de códigos modernos, la versión de mapeo se usa casi invariablemente en la práctica; puede adaptarse en tiempo de ejecución al conjunto de códigos actual, etc., que las versiones basadas en rango no pueden.


Respuesta extendida

Todavía no puedo entender cómo funciona UPPER_MASK. ¿Puedes explicarlo más específicamente?

Al ignorar los problemas de los espacios de nombres para los símbolos en los encabezados, tiene una serie de doce macros de clasificación:

  • isalpha()
  • isupper()
  • islower()
  • isalnum()
  • isgraph()
  • isprint()
  • iscntrl()
  • isdigit()
  • isblank()
  • isspace()
  • ispunct()
  • isxdigit()

La distinción entre isspace() y isblank() es:

  • isspace() : espacio ( ' ' ), avance de página ( '\f' ), nueva línea ( '\n' ), retorno de carro ( '\r' ), tabulación horizontal ( '\t' ) y tabulación vertical ( '\v' ) .
  • isblank() : espacio ( ' ' ) y tabulación horizontal ( '\t' ) .

Existen definiciones para estos conjuntos de caracteres en el estándar C, y pautas para la configuración regional C.

Por ejemplo (en la configuración regional de C), islower() o isupper() es verdadero si isalpha() es cierto, pero eso no tiene por qué ser cierto en otras configuraciones regionales.

Creo que los bits necesarios son:

  • DIGIT_MASK
  • XDIGT_MASK
  • ALPHA_MASK
  • LOWER_MASK
  • UPPER_MASK
  • PUNCT_MASK
  • SPACE_MASK
  • PRINT_MASK
  • CNTRL_MASK
  • BLANK_MASK

A partir de estas diez máscaras, puedes crear las otras dos:

  • ALNUM_MASK = ALPHA_MASK | DIGIT_MASK
  • GRAPH_MASK = ALNUM_MASK | PUNCT_MASK

Superficialmente, también puede usar ALPHA_MASK = UPPER_MASK | LOWER_MASK ALPHA_MASK = UPPER_MASK | LOWER_MASK , pero en algunas configuraciones regionales, hay caracteres alfabéticos que no son mayúsculas ni minúsculas.

Así, podemos definir máscaras de la siguiente manera:

 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[]; 

Los datos para el conjunto de caracteres; Los datos mostrados corresponden a la primera mitad de ISO 8859-1, pero son los mismos para la primera mitad de todos los conjuntos de códigos 8859-x. Estoy usando los inicializadores designados C99 como ayuda documental, aunque todas las entradas están en orden:

 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) 

Como ya se mencionó, los nombres aquí están en realidad en el espacio de nombres reservado para los usuarios, por lo que si busca en un encontrará más nombres crípticos y probablemente todos empiecen con uno o dos guiones bajos.

La compensación clásica es la velocidad frente a la memoria: ya sea calcular un resultado o buscarlo en una tabla.

No debería ser difícil averiguar cómo se verían estos, para la función isupper() .

Sin embargo, algunas cosas hacen que sea inesperadamente complicado en la CPU de hoy en día: s:

Una tabla para admitir ASCII necesita 128 bits, o 256 bits, si no desea enmascararse el bit superior, asumiendo un carácter de 8 bits. Esto es solo de 32 bytes, pero probablemente sea más que un código que explota la naturaleza secuencial de la asignación ASCII. El tamaño de código grande generalmente es malo para el rendimiento, ya que afecta la eficiencia de la memoria caché y generalmente expone la gran diferencia en el ancho de banda entre las CPU de hoy y sus subsistemas de memoria.

El código que usa comparaciones explícitas para calcular el resultado, sin explotar la asignación secuencial, será bastante grande, más grande que la tabla de consulta correspondiente. Esto no es típico; es más fácil ver la diferencia en el equilibrio entre la velocidad y la memoria en los casos en que el código para calcular un valor es más compacto que la tabla de consulta.

Un método puede hacer algunas comparaciones con ‘A’, ‘Z’.

El otro método puede usar una tabla de búsqueda precalculada.

Es la primera sugerencia mencionada en la página de Wikipedia para las compensaciones espacio-temporales .

Puede ahorrar espacio y tiempo, en realidad. Los caracteres en mayúsculas son contiguos en la tabla ASCII, por lo que solo tiene que hacer esto (esto obviamente no controla las configuraciones regionales, pero dudo que ese sea el punto de su ejercicio):

 BOOL isUpper(char c) { return (c >= 'A' && c <= 'Z'); } 

Los caracteres en mayúsculas son ASCII hex 0x41 a 0x5A. Eso significa que el bit 0x40 siempre está establecido. Si está seguro de que el argumento es un carácter ASCII, puede devolver:

(c & 0x40);