C isupper () функция - PullRequest
Новая
       14

C isupper () функция

6 голосов
/ 30 января 2010

В настоящее время я читаю «Язык программирования C, 2-е издание», и мне не совсем понятно об этом упражнении:

Такие функции, как isupper, могут быть реализованы для экономии места или экономии времени. Изучите обе возможности.

  • Как я могу реализовать эту функцию?
  • Как мне написать две версии, одну для экономии времени и одну для сэкономить место (какой-то псевдокод был бы хорош)?

Буду признателен за некоторые советы по этому поводу.

Ответы [ 5 ]

11 голосов
/ 30 января 2010

Оригинальный ответ

Одна версия использует массив, инициализированный с соответствующими значениями, один байт на символ в наборе кодов (плюс 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);
}

Обратите внимание, что «биты» могут использоваться всеми различными функциями, такими как isupper(), islower(), isalpha() и т. Д. С соответствующими значениями для маски. И если вы сделаете массив 'битов' изменяемым во время выполнения, вы сможете адаптироваться к различным (однобайтовым) кодовым наборам.

Это занимает место - массив.

В другой версии делаются предположения о смежности символов верхнего регистра, а также об ограниченном наборе допустимых символов верхнего регистра (хорошо для 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), islower() или isupper() - true, если 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, но в некоторых локалях есть буквенные символы, которые не являются ни прописными, ни строчными.

Итак, мы можем определить маски следующим образом: 

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)

Как уже отмечалось, имена здесь на самом деле находятся в пространстве имен, зарезервированном для пользователей, поэтому, если вы заглянете в заголовок <ctype.h>, вы найдете больше загадочных имен, и все они, вероятно, начнутся с одного или двух символов подчеркивания.

3 голосов
/ 30 января 2010

Классический компромисс между скоростью и памятью: либо вычислите результат, либо посмотрите его в таблице.

Нетрудно понять, как они будут выглядеть для функции isupper().

Некоторые вещи делают это, возможно, неожиданно сложным на сегодняшнем основном процессоре: s, хотя:

Таблица для поддержки ASCII требует 128 бит или 256 бит, если вы не хотите маскировать самый верхний бит самостоятельно, предполагая 8-битный char. Это всего 32 байта, но это, вероятно, все еще больше, чем код, который использует последовательный характер отображения ASCII. Большой размер кода, как правило, отрицательно сказывается на производительности, поскольку влияет на эффективность кэша и, как правило, представляет большую разницу в пропускной способности между современными процессорами и их подсистемами памяти.

Код, использующий явные сравнения для вычисления результата, без использования последовательного отображения, будет довольно большим, больше, чем соответствующая справочная таблица. Это не типично; легче увидеть разницу в соотношении скорости и памяти для случаев, когда код для вычисления значения более компактен, чем справочная таблица.

1 голос
/ 30 января 2010

Один метод может сделать несколько сравнений с «A», «Z».

Другой метод может использовать предварительно вычисленную таблицу поиска.

Это первое предложение, упомянутое на странице Википедии для пространственно-временных компромиссов .

0 голосов
/ 30 января 2010

Символы верхнего регистра являются ASCII-шестнадцатеричными от 0x41 до 0x5A. Это означает, что бит 0x40 всегда установлен. Если вы уверены, что аргумент является символом ASCII, вы можете просто вернуть:

(с & 0x40);

0 голосов
/ 30 января 2010

Вы можете сэкономить пространство и время. Символы в верхнем регистре являются непрерывными в таблице ASCII, так что вам просто нужно сделать это (очевидно, это не обрабатывает локали, но я сомневаюсь, что это смысл вашего упражнения): 

BOOL isUpper(char c)
{
    return (c >= 'A' && c <= 'Z');
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...