Функция c isupper()

Question

Функция c isupper()

В настоящее время я читаю "The C Programming Language 2nd edition", и мне не совсем понятно это упражнение:

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

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

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

5 6

5 ответов:

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

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

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

3

Один метод может сделать некоторые сравнения с 'A', 'Z'.

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

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

1

На самом деле вы можете сэкономить и пространство, и время. Символы верхнего регистра являются смежными в таблице ASCII, поэтому вам просто нужно сделать это (очевидно, что это не обрабатывает локали, но я сомневаюсь, что это является целью вашего упражнения):
BOOL isUpper(char c)
{
    return (c >= 'A' && c <= 'Z');
}

0

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

(c & 0x40);

0

Jonathan Leffler · Accepted Answer · 2018-04-07 20:50:21

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

Одна версия использует массив, инициализированный соответствующими значениями, по одному байту на символ в наборе кода (плюс 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(), и т.д. с соответствующими значениями для маски. И если вы сделаете массив' 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), либо islower(), либо isupper() истинно, если isalpha() истинно, но это не обязательно должно быть истинно в других локалях.

Я думаю, что необходимые биты являются:

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> вы найдете более загадочные имена, и они, вероятно, все будут начинаться с одного или двух подчеркиваний.