[C] Как считать с клавиатуры целое число ?

yolki

Попридержите коней, коллеги. Я далеко не новичок в этом деле и этот философский вопрос очень глубок и содержит массу подводных камней.
И так, перед вами тривиальная задача: считать с клавиатуры целое число.
После выполненных операций программа должна:
1) либо назначить введённое число некоторой переменной типа int и выставить флаг типа SUCCESS=TRUE
2) либо выставить флаг SUCCESS=FALSE, при этом значение целевой переменной не определено (читай - implementation defined)
требования: пользователь бренчит на клавиатуре что угодно, вменяемое содержимое stdin после операции гарантируется только в случае SUCCESS=TRUE. пользоваться сторонними библиотеками нельзя.
жду ваших красивых решений

psihodog

А на каком вводе программа должна гарантированно выдавать SUCCESS==TRUE? А то, в текущих условиях и такое сойдёт:
int getInt
{
SUCCESS= FALSE;
return 0;
}

vall

suc = scanf("%d", &val) == 1;
или libc это уже сторонняя библиотека?

yolki

любой ввод, попадающий в тип int.
2:
что программа скажет на ввод "10000000000000000000000" ?
не знаю, что подразумевается под libc, но scanf и stdio.h описаны в стандарте ISO 9899

vall

ах вот ты о чём, ну на errno тогда ещё посмотреть нужно.

yolki

а оно в этом случае разве что-то даст?

vall

в мане не написано, проверил — scanf меняет errno при переполнении
доверяю тебе изучить его поведение в стандарте =)

yolki

хм, странно.. какой компилятор используется? мой вот ничего такого не делает
щас стандарты поботаю

psihodog

любой ввод, попадающий в тип int.
ну это понятно. вопрос в том, допускаются ли какие-либо другие символы во вводе? например пробелы до/после числа или ничего не значащие нули?
хватит ли стандартного буффера ввода, или его нужно эмулировать самому? (на stdlib — не получится, имхо).
ну, в общем, если по простому, то:
#define BUFFLEN 1024

int getInt
{
char buff[BUFFLEN];
int i, u;
scanf("%s", buff);
sscanf(buff, "%i", &i);
sscanf(buff, "%u", &u);
SUCCESS= i==u;
return i;
}

yolki

"-1" не сработает
2 : поведение errno для scanf-а стандартом не определено

mira-bella


#define BUFFLEN 1024

int getInt
{
  char buff[BUFFLEN];
  int i, u;
  scanf("%s", buff);
  sscanf(buff, "%i", &i);
  sscanf(buff, "%u", &u);
  SUCCESS= i==u;
  return i;
}

ужос нах
из серии "найдите 50 ошибок"

psihodog

"-1" не сработает
у меня работает :-) (gcc 3.4.4)
возможно, компиляторозависимое решение, но можно сделать и чётко по стандарту :-)

psihodog

э... давай хотя бы две-три назови.

vall

ну если так, то можно считать long long, а дальше очевидно =)

yolki

на 100000000000000000000 этот код считывает 1661992960 (int=32bit и типа это считается удачным считыванием.
что не есть гуд.

yolki

это автомагически поднимает смежные вопросы про считывание лонг-лонга с клавиатуры, не находишь?

vall

у меня int и long long при переполнении насыщаются
хочешь супер переносимость — пеши фсё сам =)

psihodog

у тебя неправильный компилятор =)

vall

уж не вижуал ли студией ты это проверяешь?

yolki


Open Watcom C/C++ CL Clone for 386 Version 1.3
Portions Copyright (c) 1995-2002 Sybase, Inc. All Rights Reserved.
Source code is available under the Sybase Open Watcom Public License.
See http://www.openwatcom.org/ for details.

mira-bella


00: #define BUFFLEN 1024
01:
02: int getInt
03: {
04: char buff[BUFFLEN];
05: int i, u;
06: scanf("%s", buff);
07: sscanf(buff, "%i", &i);
08: sscanf(buff, "%u", &u);
09: SUCCESS= i==u;
10: return i;
11: }

э... давай хотя бы две-три назови.
строка 4: хотя и не ошибка, но совершенно отвратная практика - стек не резиновый.
строка 6: не просто ошибка, а самая тривиальная, часто встречающаяся и потому опасная разновидность секьюрной уязвимости - переполнение буфера. Тому у кого есть возможность формировать входные данные в stdin позволяет запускать произвольный код с привилегиями процесса, который использует функцию getInt.
строка 8: scanf по идее символ '-' должен идентифицировать как ошибку формата без заполнения переменной u, хотя фактическое поведение может и зависит от реализации стандартной библиотеки.
функциональность в целом совершенно не соответствует заявленной, а именно:
 в случае корректного ввода заведомо правильный результат только для положительного ввода (точнее, если ввод не начинается на '-' для отрицательного поведение неопределено или некорректно.
 в случае любого некорректного ввода результат не определен или некорректен плюс имеется секьюрная уязвимость.
 подробнее о некорректном вводе:
  (1) если переменные i,u не инициализируются компилятором и не заполняются scanf-ами, то SUCCESS заполняется результатом сравнения мусора (результат которого непредсказуем
  (2) если же они инициализируются компилятором в нули (как в некоторых компиляторах бывает то результат и вовсе всегда "истина" (вместо ожидаемой "ложь").

psihodog

> строка 4: хотя и не ошибка, но совершенно отвратная практика - стек не резиновый.
а ты хотел, чтобы я здесь malloc/free стал вызывать? и ещё ошибки обрабатывать? понятное дело, что в реальном коде я бы такого не написал..
> строка 6: не просто ошибка, а самая тривиальная, часто встречающаяся и потому опасная разновидность секьюрной уязвимости - переполнение буфера.
тоже, очевидно, что если бы это был реальный код, то я сначала сгенерил бы строку для сканфа с ограничителем длины. я об этом подумал, когда писал, но записывать было влома. и так понятно, что этоа идея компиляторозависима, поэтому добиваться чистоты кода — глупо.
> строка 8: scanf по идее символ '-' должен идентифицировать как ошибку формата без заполнения переменной u, хотя фактическое поведение может и зависит от реализации стандартной библиотеки.
ну вот одно дело "по идее", а компилятор мне совсем другое выдал.
так что это:
> в случае корректного ввода заведомо правильный результат только для положительного ввода (точнее, если ввод не начинается на '-' для отрицательного поведение неопределено или некорректно.
не правда =)
по поводу некорректного ввода — ты прав, действительно надо проверять, чтчо вернули сканфы, но т.к. код лишь демонстрировал идею, то и эту придирку можно отбросить.

mira-bella

и ещё ошибки обрабатывать? понятное дело, что в реальном коде я бы такого не написал..
а зачем ты тогда вообще это все написал?
Весь смысл задачи в том и состоит, чтобы выловить все ошибки и корректно считать все случаи корректного ввода.
и так понятно, что этоа идея компиляторозависима, поэтому добиваться чистоты кода — глупо.
любое компиляторозависимое решение априори неверно. Ибо по условию код должен быть на языке C, а не для какой-то конкретной версии конкретного компилятора на конкретной платформе с конкретной реализацией стандартной библиотеки.
Для данной задачи весь смысл именно в том, чтобы добиться чистоты кода - именно в этом вся задача и состоит. В противном случае подошло бы и решение
 
if( scanf("%d",&i) == 1 )
SUCCESS = TRUE;
else
SUCCESS = FALSE;

> строка 8: scanf по идее символ '-' должен идентифицировать как ошибку формата без заполнения переменной u, хотя фактическое поведение может и зависит от реализации стандартной библиотеки.
ну вот одно дело "по идее", а компилятор мне совсем другое выдал.
ну детский сад просто
кого вообще интересует, что выдал твой конкретный компилятор с твоей конкретной реализацией scanf-а (которая вообще не в компиляторе находится)
Код на языке C у тебя неверный и точка.
по поводу некорректного ввода — ты прав, действительно надо проверять, чтчо вернули сканфы, но т.к. код лишь демонстрировал идею, то и эту придирку можно отбросить.
так какую же идею этот код демонстрировал?
В общем строки твоего кода делятся на те, которые "понятное дело, что в реальном коде ты бы такого не написал" и те, в которых ты признаешь ошибку.

mira-bella

вообще ясно, что единственно_правильное_и_самое_наикрасивейшее_решение - это посимвольное считывание.
и уж конечно самое эффективное и переносимое, если правильно написать.

psihodog

так какую же идею этот код демонстрировал?
как я уже писал выше, компиляторозависимую.
(задача — определить что было переполнение инта в сканфе по косвенным признакам, если уж сканф errno не устанавливает)
ещё была другая идея, но без ограничений на ввод, она тоже становится не такой красивой.
а посимвольно считывать... каждый насильник(тм) может

Marinavo_0507

строка 4: хотя и не ошибка, но совершенно отвратная практика - стек не резиновый.
с чего бы это?

yolki

если этот самый getInt будет использован в рекурсивной функции, то на некотором [очень близком] шаге прога схватит переполнение стека.

Marinavo_0507

если этот самый getInt будет использован в рекурсивной функции, то на некотором [очень близком] шаге прога схватит переполнение стека.
ошибаешься
сам-то getInt не рекурсивен

yolki

однако, прав. но практика всё равно дурная

Marinavo_0507

разве что внутри ядра, где размер стека 4 или 8 килобайт
в виндовом ядре уже больше - там можно и на стек класть большие структуры
ничуть не понимаю, почему усложнение кода без веских причин вы считаете хорошей практикой

mira-bella

если этот самый getInt будет использован в рекурсивной функции, то на некотором [очень близком] шаге прога схватит переполнение стека.
это скорее если бы сам getInt был рекурсивным,
но и для нерекурсивной функции это отвратная практика ибо так вот несколько друг друга вызывающих функций скушают по килобайту и получим переполнение,
или человек привыкший так писать начнет кушать не по килобайту, а по мегабайту.

mira-bella

апередил

Marinavo_0507

ибо так вот несколько друг друга вызывающих функций скушают по килобайту и получим переполнение
ты хотел сказать "несколько тысяч", да?
самому-то не смешно?
или человек привыкший так писать начнет кушать не по килобайту, а по мегабайту
разве что быдлокодер(tm)
а программист с нормальными умственными способностями разницу между килобайтом и мегабайтом осознаёт

Ivan8209

> пользоваться сторонними библиотеками нельзя.
Если честно, принимая во внимание выделенное, я бы плюнул
и на libc, ввод-вывод целых чисел не настолько сложное действие,
его и переписать нетрудно.
Я бы перенёс >NUMBER (ANSI X3.215--94 6.1.0570
сделав "ambiguous condition" менее "ambiguous",
тем более, что исходники уже есть.
Выделение дополнительной памяти, вызывающее споры,
никак не требуется, если использовать единственно верное
представление строк --- в виде пары "указатель---длина".
---
...Я работаю антинаучным аферистом...

sergey_m

man strtod

Marinavo_0507

> man strtod
то есть, сначала в буфер считывать?

Ivan8209

man fgetln
Оно считает это за тебя.
---
...Я работаю антинаучным аферистом...

vall

а если там гигабайт ведущих нулей? =)

Ivan8209

Сотня опытных пользователей сидит и тупо набивает на клавиатуре ведущие нули.
Гигабайтами.
---
...Я работаю антинаучным аферистом...

Olenenok

Я делал так:
1) Предлагал ввести число, но записывал ввод в строку, причём максимальная длина текста была ограничена. Всё что не лезло в буфер просто выкидывал
char buffer[1024];
while (scanf ("%1023s", buffer) < 1);
while (getchar != '\n')

2) Разбирал, что там ввёл юзер. Разбирал количество значащих цифр, не дай бог ввели какую-то букву вместо цифры и пр.

Ivan8209

> char buffer[1024];
<<Commonly, when the user is preparing an input string to be
transmitted to a program, the system allows the user to edit
that string and correct mistakes before transmitting the final
version of the string.>>
> scanf ("%1023s", buffer)
<<As in previous standards, EXPECT returns the input string
immediately after the requested number of characters are
entered, as well as when a line terminator is received. The
"automatic termination after specified count of characters have
been entered" behavior is widely considered undesirable because
the user "loses control" of the input editing process at a
potentially unknown time (the user does not necessarily know
how many characters were requested
from EXPECT). Thus EXPECT
and SPAN have been made obsolescent...>>
Подчёркивание моё.
---
...Я работаю антинаучным аферистом...

bleyman

На вводе "10 20 30" твоя функция считает 10 и дискарднет всё остальное. Это как бы не очень хорошее поведение, на мой взгляд.

Marinavo_0507

Дык автор треда не сказал, что нужно делать с остатком входного потока.
Многие версии Бейсика, помнится, писали в таких случаях "extra ignored" или типа того.

bleyman

Автор сказал, что "вменяемое содержимое stdin после операции гарантируется только в случае SUCCESS=TRUE."
Я не могу представить, что ещё он мог иметь в виду.

yolki

20, 30 - останутся в потоке. это имелось в виду

Marinavo_0507

то есть если пользователь промахнулся и вместо "203" написал "2 3", то не будет никакой ошибки, а просто на следующий вопрос ему не дадут ответить?

yolki

именно

Marinavo_0507

ну тогда я бы действительно вручную посимвольно сделал
никакого буфера не надо, и ungetc есть

garikus

Сообщение удалил

mira-bella

ты хотел сказать "несколько тысяч", да?
самому-то не смешно?
конечно не смешно
несколько постов назад ты сам упомянул про стек в несколько килобайт для потока ядра.
я уж не говорю про программирование всяких встроенных микродевайсов, и т.п.
разве что быдлокодер(tm)
а программист с нормальными умственными способностями разницу между килобайтом и мегабайтом осознаёт
так же как и разницу между несколькими байтами и килобайтами

mira-bella

...............
PROCEDURE ExpectEOL (c: CHAR): BOOLEAN;
BEGIN
...............
подойдёт

не подойдет
в заголовке каждого поста упоминается язык C, если ты не заметил.

Olyalyau

В предположении, работа происходит кодировке, в которой символы '0',...,'9' идут по порядку и подряд, а также, что под словами
целое число

подразумевалось "возможное значение переменной int, не являющее сигнальным (trap)":

#include <limits.h>
#include <stdio.h>

#undef TRUE
#define TRUE 1

#undef FALSE
#define FALSE 0

inline
int
is_numeric (char c)
{
return c >= '0') && (c <= '9';
}

inline
int
is_terminating (char c)
{
return c == '\n') || (c == '\r') ||
(c == ' ') || (c == '\t';
}

int
read_int (int * result)
{
int read;
int sign = 1;
int value = 0;
int c_value;
int no_number_present = 1;
char c;

read = scanf ("%c", & c);

if (read != 1)
return FALSE;

if (c == '-')
{
sign = -1;
read = scanf ("%c", & c);
}
else if (c == '+')
read = scanf ("%c", & c);

if (sign == 1)
{
while read == 1) && (is_numeric (c
{
no_number_present = 0;
c_value = c - '0';
if INT_MAX - c_value) / 10) < value)
return FALSE;
value = value * 10 + c_value;
read = scanf ("%c", & c);
}
}
else
{
while read == 1) && (is_numeric (c
{
no_number_present = 0;
c_value = c - '0';
if INT_MIN + c_value) / 10) > value)
return FALSE;
value = value * 10 - c_value;
read = scanf ("%c", & c);
}
}

if no_number_present) ||
read != EOF) && (! is_terminating (c
return FALSE;

(* result) = value;
return TRUE;
}

int
main
{
int result;
int flag = read_int (& result);

if (flag == TRUE)
fprintf (stdout, "%d\n", result);
else
fprintf (stderr, "Error!\n");

return (! flag);
}

PS. Поддержка недесятичных систем счисления оставляется читателю в качестве упражнения

Ivan8209

Правильный ответ уже дан и не совпадает с твоим.
> is_numeric
> scanf ("%c", & c)
То, как ты пишешь, показывает, что ты не знаком с libc.
Любишь переизобретать велосипед?
> fprintf (stderr, "Error!\n")
Умные люди уже давно придумали err/warn.
---
...Я работаю антинаучным аферистом...

Russula

а в стандарте c есть inline? Вроде как это плюсовая фича

Ivan8209

А плевать. -D'inline=' решает.
---
...Я работаю антинаучным аферистом...

garikus

вот ещё одно

/*
EBNF:
number = [sign] digit {digit} eol .
sign = '+' | '-' .
digit = '0'..'9' .
eol = 0x0a | 0x0d .
*/

#include <ctype.h>
#include <stdio.h>
#include <limits.h>

#define expecteol(c) c) == 0x0a) || c) == 0x0d
#define expectdigit(c) isdigit(c)
#define ctoi(c) c) - '0')
#define FALSE 0
#define TRUE 1

void getnumber (int *num, int *success)
{
int x, i;
int sign, overflow;
int c;

c = getchar;
if (c == '-') {
sign = TRUE;
c = getchar;
} else if (c == '+') {
sign = FALSE;
c = getchar;
} else
sign = FALSE;

if (expectdigit(c {
x = 0;
while (1) {
i = ctoi(c);
overflow = (x > (INT_MAX - i) / 10);
if (overflow)
break;
x = x * 10 + i;
c = getchar;
if (!expectdigit(c
break;
}

if !overflow) && (expecteol(c {
*num = sign ? -x : x;
*success = TRUE;
} else
*success = FALSE;
} else
*success = FALSE;
}

int main (int argc, char *argv[])
{
int x, success;

getnumber(&x, &success);
if (success)
printf("%d\n", x);
else
printf("error\n");

return 0;
}

Ivan8209

> void getnumber (int *num, int *success)
Любишь strto* переизобретать?
> expecteol(c)
Ещё и с жёстко зашитым fgetln/getline.
---
...Я работаю антинаучным аферистом...

garikus

> void getnumber (int *num, int *success)
Любишь strto* переизобретать?
Так писали же, что не подойдёт.
> expecteol(c)
Ещё и с жёстко зашитым fgetln/getline.
В условии же не было сказано, чем должно заканчиваться число. А так можно легко изменить.

Ivan8209

>>> void getnumber (int *num, int *success)
>> Любишь strto* переизобретать?
> Так писали же, что не подойдёт.
Где именно?
>> Ещё и с жёстко зашитым fgetln/getline.
> В условии же не было сказано, чем должно заканчиваться число.
И?
Это повод переизобретать strto*?
Повод переизобретать fgetln/readline?
Насколько я помню погнутую libc, там есть соответствующая примочка. Это раз.
Во-вторых, "с клавиатуры" означает вмешательство пользователя,
что означает либо специализированную процедуру ввода,
то есть _необходимо_ работать в неканоническом режиме терминала
и производить закат солнца вручную, либо надо работать в каноническом
режиме и не париться с вводом строки, задействовав штатную
процедуру ввода, предоставляемую ОС.
Потому что ОС _уже_ предоставляет готовое решение.
В частности, getchar лезет в то же самое место, что и fgetln,
следовательно, использовать вместо него getchar нахрен не надо.
"Вы должны знать, для чего пишете, иначе <...> вы заблудитесь."
Типа, Чехов. "Чайка."
---
"Мы продолжаем то, что мы уже много наделали."

garikus

И?
Это повод переизобретать strto*?
Повод переизобретать fgetln/readline?
Это же не то, что надо. Если бы была функция fgetint, то другое дело. Вообще-то есть scanf, но видимо он парсит-что то не то, что надо, иначе бы не было этого треда. Моё решение простое.

Ivan8209

> Это же не то, что надо.
Это то, что надо в случае UNIX-подобных систем.
> Вообще-то есть scanf, но видимо он парсит-что то не то,
> что надо, иначе бы не было этого треда.
А ты хотя бы попытался выяснить, почему именно не подходит scanf?
Я понимаю, почему он может не подходить.
> Моё решение простое.
bzero/memset пишется просто, равно как strcpy и т. п.,
но правильно писать --- вызов bzero/memset,
а не соответствующий цикл, каким бы простым он ни был.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

garikus

bzero/memset пишется просто, равно как strcpy и т. п.,
но правильно писать --- вызов bzero/memset,
а не соответствующий цикл, каким бы простым он ни был.
при чём здесь это?

Ivan8209

Притом, что твоё решение --- это написание одного
удовлетворительного качества strto*, и одного очень плохого fgetln.
---
"Это глупость вообще, но мне это знакомая песня."

garikus

Притом, что твоё решение --- это написание одного
удовлетворительного качества strto*, и одного очень плохого fgetln.
Может быть memset/bzero ещё и integer распарсит?
И чем же так очень плохо моё решение по сравнению с fgetln, когда распарсить нужно integer, а не строку, я так и не понял.

Ivan8209

Тем, что оно не задействует (неполностью задействует)
имеющиеся средства операционной системы.
Я изначально считаю, что задача поставлена неполностью:
"с клавиатуры" может означать что угодно от "подсоединено устройство
(возможно, отрабатывающее дребезг и длительное удержание)",
с которого надо считывать нажатия, до терминала в каноническом режиме
или текстового поля в форме. Последние два случая равнозначны.
---
"Это глупость вообще, но мне это знакомая песня."

garikus

Тем, что оно не задействует (неполностью задействует)
имеющиеся средства операционной системы.
Я бы тоже хотел, чтобы оно задействовало средства библиотеки libc, если бы они были. Вот например в стандартной библиотеке для языка Oberon такие средства есть.

Ivan8209

И strto*, и fgetln входят в libc.
---
"Расширь своё сознание!"

Olyalyau

Правильный ответ уже дан и не совпадает с твоим.

Правильный ответ — это который?
, что выдаёт на моей машине "suc=1 val=2147483647" в ответ на предложенный "100000000000"?
Или , что выдаёт на моей машине"Segmentation fault" в ответ на простой автотест "(i=1; while [ $i -le 100 ]; do echo -n "000000000000000000000"; i=`expr $i + 1`; done) | ..."?
(Кстати, первый вариант выдаёт то же самое если заменить "$i -le 100" на "$i -le 100000".)
ещё кто-то предлагал воспользоваться функцией
fgetln
которая не описана в стандарте, но, видимо, подобно функции fgets оперирует буферами конечного размера.
Любишь переизобретать велосипед?

Обожаю. И как показывает практика, делаю это лучше первооткрывателей велосипеда. К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза, а моя реализация
MD5, на little-endian машине работает быстрее OpenSSL'евской в 1.3 раза, на big-endian — вровень с OpenSSL'вской.
> is_numeric

Я знаю о существовании функций isdigit и других функций из ctype.h. А также (видимо, в отличие от тебя) знаю чем они хуже моей is_numeric.
> scanf ("%c", & c)
Да, надо было read использовать
Умные люди уже давно придумали err/warn.

Вот это в точку. Никогда не причислял себя к умным людЯм

Olyalyau

а в стандарте c есть inline?

Да, в стандарте C есть inline: ISO/IEC 9899:1999 (AKA C99) "6.7.4 Function specifiers".

Olyalyau

Твоя программа выдаёт "error" в ответ на "-2147483648" (=INT_MIN на моей машине, мой вариант выдаёт "-2147483648"). А всё дело в том, что ты считываешь число из отрезка [-INT_MAX, INT_MAX] != [INT_MIN, INT_MAX]. Соотношение между INT_MIN и INT_MAX никак не специфицировано стандартом; на IA32 INT_MIN = -INT_MAX-1.

qsk78

К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза, а моя реализация MD5, на little-endian машине работает быстрее OpenSSL'евской в 1.3 раза, на big-endian — вровень с OpenSSL'вской.
Ну так отправь им свой код, помоги сообществу.

poi1981

>К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза
а sizeof(string) твой во сколько раз больше жэцэцэшного? в 5?

Olyalyau

bzero/memset пишется просто, равно как strcpy и т. п.

Блаженны верующие.
Я знаю, что не способен сейчас, сходу, без доки на SSE/3d now!/SSE2/..., написать memset, strcpy и проч. оптимальнее GNU'шных. Между тем, это возможно; причём тот код, что я видел, работает заметно быстрее GNU'шного. Но даже GNU'шный код memset (порядка 25-30 инструкций) не "прост".

Olyalyau


>К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза
а sizeof(string) твой во сколько раз больше жэцэцэшного? в 5?

На IA32 sizeof(string) = 4 для GNU, 12 для меня, и, естественно не зависит от длины строки.
(Кстати, я легко могу сделать 4 и скорость при это упадёт не сильно, но — не вижу повода).
Это просто по тому, что GNU string содержит один единственный указатель на структуру данных строки (которая выделяется динамически и имеет объём 12 байт). Таким образом, под вспомогательные данные (в том числе под указатель на данные строки) GNU тратит 16 байт, я — 12. Минимум — 6, на котором строки будут __так__ тормозить (и иметь длину не больше 64K).
А, ты, видимо имел в виду не то, что написал, а "сколько памяти расходует экземпляр string в зависимости от длины строки, которой он инициализирован?" (Причём именно "инициализирован" — ни я, ни GNU не уменьшаем объём данных строки, если сама строка укорачивается).
Это надо уточнить, дойду завтра до работы, посмотрю. Мой вариант имеет асимптотику = вспомогательные данные + 2^(ceil (log_2 (string::size + 1.

kokoc88

Обожаю. И как показывает практика, делаю это лучше первооткрывателей велосипеда. К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза, а моя реализация
Ты неимоверно крут. Только не понятно, почему в коде столько copy-paste
  if (sign == 1)
{
while read == 1) && (is_numeric (c
{
no_number_present = 0;
c_value = c - '0';
if INT_MAX - c_value) / 10) < value)
return FALSE;
value = value * 10 + c_value;
read = scanf ("%c", & c);
}
}
else
{
while read == 1) && (is_numeric (c
{
no_number_present = 0;
c_value = c - '0';
if INT_MIN + c_value) / 10) > value)
return FALSE;
value = value * 10 - c_value;
read = scanf ("%c", & c);
}
}

Olyalyau

Ты неимоверно крут.

Да, я знаю
Только не понятно, почему в коде столько copy-paste

Сначала я написал if (sign == ...) внутри while. Но sign в цикле не меняется, так что, чтобы не делать лишний if в теле, я его вынес наружу (при этом, естественным образом, while раздвоился). Дополнительный плюс вынесения этого if наружу — снижение icache pressure и увеличение локальности кода (при считывании символов данного числа). Кто не верит, что от этого функция стала быстрее работать — rdtsc + sched_yield в руки — проверьте. Естественно, вызов scanf ситуацию в теле цикла портит гораздо сильнее этого if'а, но тут уж ничего не поделать (кроме полной смены алгоритма всей функции read_int .
PS. Кстати, а слона-то никто и не заметил!
Делить в цикле не на степень двойки
 if INT_MAX - c_value) / 10) < value) 

и
  if INT_MIN + c_value) / 10) > value) 

верх неприличия, естественно надо сравнивать с таблицей. Вот так:

int
read_int (int * result)
{
static int const max_limit_value [10] = {(INT_MAX - 0) / 10,
(INT_MAX - 1) / 10,
(INT_MAX - 2) / 10,
(INT_MAX - 3) / 10,
(INT_MAX - 4) / 10,
(INT_MAX - 5) / 10,
(INT_MAX - 6) / 10,
(INT_MAX - 7) / 10,
(INT_MAX - 8) / 10,
(INT_MAX - 9) / 10};

static int const min_limit_value [10] = {(INT_MIN + 0) / 10,
(INT_MIN + 1) / 10,
(INT_MIN + 2) / 10,
(INT_MIN + 3) / 10,
(INT_MIN + 4) / 10,
(INT_MIN + 5) / 10,
(INT_MIN + 6) / 10,
(INT_MIN + 7) / 10,
(INT_MIN + 8) / 10,
(INT_MIN + 9) / 10};

int read;
int sign = 1;
int value = 0;
int c_value;
int no_number_present = 1;
char c;

read = scanf ("%c", & c);

if (read != 1)
return FALSE;

if (c == '-')
{
sign = -1;
read = scanf ("%c", & c);
}
else if (c == '+')
read = scanf ("%c", & c);

if (sign == 1)
{
while read == 1) && (is_numeric (c
{
c_value = c - '0';
no_number_present = 0;
if (max_limit_value [c_value] < value)
return FALSE;
value = value * 10 + c_value;
read = scanf ("%c", & c);
}
}
else
{
while read == 1) && (is_numeric (c
{
c_value = c - '0';
no_number_present = 0;
if (min_limit_value [c_value] > value)
return FALSE;
value = value * 10 - c_value;
read = scanf ("%c", & c);
}
}

if no_number_present) ||
read != EOF) && (! is_terminating (c
return FALSE;

(* result) = value;
return TRUE;
}

Я тут ещё и поменял местами строки

c_value = c - '0';
no_number_present = 0;

(раньше было в обратном порядке). Вот это уже чистой воды arcane knowledge (см. intel optimization guide).

Olyalyau

>К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза
а sizeof(string) твой во сколько раз больше жэцэцэшного? в 5?
Сначала про скорость:
RedHat/intel (измерялось с помощью sched_yeild + rdtsc) показано время в тактах на выполнение одинаковых тестовых наборов операций, svg — моя реализация строк, std — GNU. error — погрешность измерения (то есть разность между последовательными rdtsc):

error svg std
119 410632 883897

Тут моя реализация в 2.15253 раза быстрее GNU'шной.
Solaris/sparc (измерялось с помощью sched_yeild + gettimeofday ; у Sparc'а есть регистр со счётчиком тактов процессора, но он доступен только при -arch=v9 и обладает подозрительной странностью, из-за которой я его не использовал, — он 64-битный с 32-мя битами нулей):

error svg std
0 249 386

Здесь моя реализация в 1.54953 раза быстрее GNU'шной.
Теперь про объём. Тут из STL такая шняга вылезла, что я от использования её вообще хочу отказаться. А именно — для некоторых строк (экспериментально — менее 116 байт и более 0 байт) GNU'шный STL выделяет огроменный кеш-буфер, из которого уже берёт куски памяти для таких строк. Буфер этот не освобождается в течении жизни программы (его объём только растёт по этому накладные расходы памяти зависят от всей истории программы, а не только от текущего объёма полезных данных. Кроме того такие действия снижают предсказуемость поведения долгоживущих программ (вроде демонов) и, в частности в RT-системе, нежелательны.
Из-за этого привожу результаты двух тестов: в одном последовательно создавались (и сразу уничтожались) строки длины от 0 до 65533 (замечательное число, дальше которого память начинает браться из не первой арены и функция mallinfo становится бесполезной). В этом тесте GNU сильно проигрывает мне по соотношению (длина строки)/(затрачиваемая память). Во втором тесте строки брались длины от 116 и до замечательного числа. При этом видно, что моё соотношение (расход памяти)/(длина строки) колеблется между ~50% и ~100%, а расход памяти GNU'шной реализации (кроме самого начала) — между ~80% и ~100%. Кроме того, видно, что асимптотика расхода памяти в зависимости от длины строки у GNU такая же, как у меня, но с другой константой (вместо 2-ки).
Функция одной итерации:

static char memory [65533];

void
test_size (size_t const size)
{
static unsigned long int std_cache (0);
static unsigned long int svg_cache (0);

struct mallinfo const mi_1 (mallinfo ;
std::string * const std_s (new std::string (memory, size;
struct mallinfo const mi_2 (mallinfo ;
svg::string * const svg_s (new svg::string (memory, size;
struct mallinfo const mi_3 (mallinfo ;
unsigned long int const std_m (mi_2.uordblks - mi_1.uordblks + std_cache);
unsigned long int const svg_m (mi_3.uordblks - mi_2.uordblks + svg_cache);
unsigned long int const std_u std_s->capacity * 1000) / std_m);
// double const std_u double) std_s->capacity / std_m);
unsigned long int const svg_u svg_s->capacity * 1000) / svg_m);
// double const svg_u double) svg_s->capacity / svg_m);

static unsigned long int old_std_m (0);
static unsigned long int old_svg_m (0);
static std::string::size_type old_std_c (0);
static svg::string::size_type old_svg_c (0);
static bool print_dots (true);

if old_std_m == std_m) and
(old_svg_m == svg_m) and
(old_std_c == std_s->capacity and
(old_svg_c == svg_s->capacity
{
if (print_dots)
{
std::cout << "...\n";
print_dots = false;
}
}
else
{
old_std_m = std_m;
old_svg_m = svg_m;
old_std_c = std_s->capacity ;
old_svg_c = svg_s->capacity ;
print_dots = true;
std::cout << std::setfill ('0') << size << '\t' << std_m
<< (std_m > svg_m ? "\t>\t" : "\t<=\t")
<< svg_m << '\t'
// double иногда после запятой выводится с большим числом знаков, чем std::setprecision (я так понял , STL пытается вывести хотябы две значащие цифры)
// << std::setw (7) << std::setprecision (5) << (double) size / std_m << '\t'
<< '.' << std::setw (6) << uint64_t) size * 1000000) / std_m << '\t'
// << std::setw (7) << std::setprecision (5) << (double) size / svg_m << '\t'
<< '.' << std::setw (6) << uint64_t) size * 1000000) / svg_m << '\t'
<< std_s->capacity << '\t'
<< svg_s->capacity << '\t'
// << std::setw (4) << std::setprecision (2) << std_u << (std_u > svg_u ? "\t> " : "\t<= ")
<< '.' << std::setw (3) << std_u << (std_u > svg_u ? "\t> " : "\t<= ")
// << std::setw (4) << std::setprecision (2) << svg_u << '\t' << std_cache << '\t' << svg_cache << '\n';
<< '.' << std::setw (3) << svg_u << '\t' << std_cache << '\t' << svg_cache << '\n';
}

struct mallinfo const mi_4 (mallinfo ;
delete svg_s;
struct mallinfo const mi_5 (mallinfo ;
delete std_s;
struct mallinfo const mi_6 (mallinfo ;

// if (mi_4.uordblks != mi_3.uordblks) // Всегда mi_4.uordblks == mi_3.uordblks
// std::cout << "std::cout memory disturbance: " << mi_4.uordblks - mi_3.uordblks << '\n';
svg_cache = svg_m - (mi_4.uordblks - mi_5.uordblks); // Всё равно равен нулю, я кеш себе не отвожу, но для симметричности посчитаем
std_cache = std_m - (mi_5.uordblks - mi_6.uordblks);
}

Первый вариант и его результат:

std::cout << "sizeof (std::string) = " << sizeof (std::string)
<< "; sizeof (svg::string) = " << sizeof (svg::string) << '\n';

std::cout << "length\tstd mem\tV\tsvg mem\tstd l/m\tsvg l/m\tstd cap\tsvg cap\tstd c/m\tsvg c/m\tstd cch\tsvg cch\n";

for (unsigned int i (0); i <= sizeof (memory); ++i)
test_size (i);

Столбцы:
1) длина строки
2) расход памяти на строку вместе с метаданными и указателем на строку для std::string
3) соотношение расхода памяти для std::string и svg::string (когда ">" — я экономнее расходую память, когда "<=" — std::string экономнее расходует память)
4) расход памяти на строку вместе с метаданными и указателем на строку для моих строк
5) отношение (длина строки)/(расход памяти) для std::string
6) отношение (длина строки)/(расход памяти) для svg::string
7) capacity созданной строки для std::string
8) capacity созданной строки для svg::string
9) отношение capacity /(расход памяти) для std::s

Olyalyau

Ну так отправь им свой код, помоги сообществу.

Начальник то же самое предлагал, но у меня до этого руки никак не дойдут.

kokoc88

Дополнительный плюс вынесения этого if наружу — снижение icache pressure и увеличение локальности кода
Где-то когда-то уже писали про то, сколько времени программисты тратят на ненужную оптимизацию... Забыл ссылку.

Ivan8209

> Правильный ответ — это который?
man strtod
>> fgetln
> которая не описана в стандарте,
И что?
> но, видимо, подобно функции fgets оперирует буферами конечного размера.
Настоящие программисты документацию не читают.
---
"Аллах не ведёт людей неверных."

Ivan8209

> Дополнительный плюс вынесения этого if наружу —
> снижение icache pressure и увеличение локальности кода
Ты думаешь, это имеет значение?
К сведению, изначально вопрос поставлен так:
"[C] Как считать с клавиатуры целое число?"
> Вот это уже чистой воды arcane knowledge (см. intel optimization guide).
Что если спрашивает про ARM?
---
"Верь сводке погоды..."

Olyalyau

Настоящие программисты документацию не читают.

Ага, настоящие программисты — те кто её пишут

Olyalyau


Где-то когда-то уже писали про то, сколько времени программисты тратят на ненужную оптимизацию... Забыл ссылку

Для кого как, а для меня оптимизация означает возможность ставиться не на $100k-сервак, а на жалкий
$30k.

Olyalyau


> Вот это уже чистой воды arcane knowledge (см. intel optimization guide).
Что если спрашивает про ARM?

Мне неизвестен ни один процессор, на котором та модификация кода снизит производительность, зато известны два семейства (IA32, AMD64 на которых та модификация повысит производительность.
Более того, нет никаких предпосылок (кроме того самого intel optimization guide) записать эти строки в определённом порядке.
А что ARM? Под удовлетворяющей C99 платформой моя программа будет работать, будет работать правильно, и будет работать (если компилятор нормальный) не сильно медленнее любой другой программы, правильно решающей поставленную задачу, на той же платформе.

Olyalyau


К сведению, изначально вопрос поставлен так:
"[C] Как считать с клавиатуры целое число?"

У меня дома есть большой шарик от подшипника, я готов положить его на кнопку "0" и уехать на работу.
А по возвращении, убрать шарик и нажать "Enter". Гигабайта нулей он, вероятно не сделает, но вот мегабайты — запросто (особенно есть сделать автоповтор быстрым). И эти мегабайты нулей будут считаны с клавиатуры Как там твой "fgetln" на это отреагирует?
Кстати, я только что разговаривал с лично, эта задачка — часть того, что он требует от студентов. Его слова "в файле записаны числа, их надо перемножить".

Olyalyau

> Дополнительный плюс вынесения этого if наружу —
> снижение icache pressure и увеличение локальности кода
Ты думаешь, это имеет значение?

Я не думаю, я знаю
А думать я не умею

Olyalyau

> Правильный ответ — это который?
man strtod

SYNOPSIS
#include <stdlib.h>
double strtod(const char *nptr, char **endptr);
float strtof(const char *nptr, char **endptr);
long double strtold(const char *nptr, char **endptr);
DESCRIPTION
The strtod, strtof, and strtold functions convert the initial por-
tion of the string pointed to by nptr to double, float, and long
double representation, respectively.

Как ты верно заметил,
К сведению, изначально вопрос поставлен так:
"[C] Как считать с клавиатуры целое число?"

клавиатура не есть string , так что
man strtod

также не является правильным решением поставленной задачи

Olyalyau


>К примеру, моя реализация std::string обгоняет стандартную из поставки GCC примерно в 1.5 раза
а sizeof(string) твой во сколько раз больше жэцэцэшного? в 5?

Да, если кто хочет заняться более углублёнными исследованиями std::string и svg::string — запощу код.

kokoc88

Для кого как, а для меня оптимизация означает возможность ставиться не на $100k-сервак, а на жалкий
$30k.
Слово "ненужную" ты не прочитал. Такая оптимизация явно не потянет на 100к-30к, она и на доллар-то не вытянет. А время разработчик тратит.

Olyalyau

Слово "ненужную" ты не прочитал. Такая оптимизация явно не потянет на 100к-30к, она и на доллар-то не вытянет. А время разработчик тратит.

Как показывает опыт, большая оптимизация имеет тенденцию складываться из маленьких — здесь std::sting переписали, там md5 hash, тут вместо множества вызовов gettimeofday сделали всего парочку (сразу после блокирующихся операций) и закешировали результат, в паре мест вынесли независящий от итерации код из цикла — глядишь, процентов 10 выиграли. А 10% производительности, это примерно 50% стоимости железа.

kokoc88

Как показывает опыт, большая оптимизация имеет тенденцию складываться из маленьких
Мне опыт пока что показывает только одно: большая оптимизация - это смена n*n на log n.

Ivan8209

> У меня дома есть большой шарик от подшипника,
> я готов положить его на кнопку "0" и уехать на работу.
И?
Приличный драйвер должен в таком случае заблокировать ввод,
поскольку устройство явно неисправно.
> особенно есть сделать автоповтор быстрым
А если автоповтор отменить?
Это, кстати, более верное решение при вводе с клавиатуры.
Автоповтор нужен для координатного устройства,
типа джойстика или части клавиатуры со стрелками,
на все клавиши автоповтор действовать, по-хорошему, не должен.
> Как там твой "fgetln" на это отреагирует?
Так, как написано в документации.
Кстати, мог бы сам проверить

decimal 100 1000 1000 * * dup . allocate throw free throw 100000000 ok

> "в файле записаны числа, их надо перемножить".
Это совсем другая задача.
---
"Аллах не ведёт людей неверных."

Ivan8209

> Как ты верно заметил,
...
> клавиатура не есть string , так что
Про написание драйвера я уже сказал: данных недостаточно.
---
"Аллах не ведёт людей неверных."

Olyalyau

Мне опыт пока что показывает только одно: большая оптимизация - это смена n*n на log n.

На этот счёт я уже всё сделал: даже если не выносить if из цикла, поставленная задача решена за C_1*n операций, где n — длина вводимого числа. Эта задача не может быть решена менее чем за C*n операций. (C_1, C — константы.) Всё, что я сделал выносом if из while — уменьшил C_1*n до C_2*n
(С<=C_2<C1).
Твоя позиция понятна. Видимо, разработчики std::string такие же небрежные люди, как и ты — и их реализация работает в 1.5 раза медленнее моей svg::string. Видимо оптимизация константы им, так же как и тебе, показалась несущественной.

Olyalyau

> У меня дома есть большой шарик от подшипника,
> я готов положить его на кнопку "0" и уехать на работу.
И?
Приличный драйвер должен в таком случае заблокировать ввод,
поскольку устройство явно неисправно.
> особенно есть сделать автоповтор быстрым
А если автоповтор отменить?
Это, кстати, более верное решение при вводе с клавиатуры.
Автоповтор нужен для координатного устройства,
типа джойстика или части клавиатуры со стрелками,
на все клавиши автоповтор действовать, по-хорошему, не должен.

Ты это о чём? Исходная задача была про считывание с клавиатуры числа на языке C. Никто не просил тебя писать драйвер клавиатуры
> Как там твой "fgetln" на это отреагирует?
Так, как написано в документации.
Кстати, мог бы сам проверить

Проблема именно в том, что я проверил — нет функции fgetln в языке C (см. ISO/IEC 9899:1999).
А всё дело в том, что

HISTORY
The fgetln function first appeared in 4.4BSD.

Так что от тебя всё ещё ждут правильного решения поставленной задачи.

Olyalyau

> Как ты верно заметил,
...
> клавиатура не есть string , так что
Про написание драйвера я уже сказал: данных недостаточно.

Вот-вот и я дивлюсь — зачем ты придумал себе задачу про написание драйвера?

mira-bella

Ты это о чём? Исходная задача была про считывание с клавиатуры числа на языке C. Никто не просил тебя писать драйвер клавиатуры
дотошно анализируя формулировку задачи можно заметить: в стандарте языка C нет функций для работы с клавиатурой (и быть не может, т.к. стандарт учитывает возможность использования языка C на оборудовании не имеющем клавиатуры, диска, монитора, и т.п.).
Очевидно для полной корректности формулировки следовало задать считывание числа из потока. Но суть задания и так конечно ясна.
Насчет всего остального: респект и +1

kokoc88

Твоя позиция понятна. Видимо, разработчики std::string такие же небрежные люди, как и ты — и их реализация работает в 1.5 раза медленнее моей svg::string. Видимо оптимизация константы им, так же как и тебе, показалась несущественной.
Я не знаю, что там у разработчиков std::string, а что там у тебя. Мне вообще плевать, за 0.0001 секунду моя программа ответит или за 0.00015. На реальных проектах большой оптимизации такими мелочами ты не получишь. Зато код они засорят будь здоров.
Впрочем, на мой изначальный вопрос ты вполне ответил.

Codcod

К концу треда я рыдал.

Ivan8209

> Проблема именно в том, что я проверил — нет функции fgetln в языке C (см. ISO/IEC 9899:1999).
И?
В языке С много чего нет, в частности нет средств работы с пространством адресов ввода-вывода,
ибо нет такого у мотороллеров. Про исходные ПДП не помню, но и там, думаю, нет.
> Так что от тебя всё ещё ждут правильного решения поставленной задачи.
Для начала я подожду от тебя правильного понимания задачи, чего пока что не наблюдается.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."

Olyalyau

И?
В языке С много чего нет, в частности нет средств работы с пространством адресов ввода-вывода,
ибо нет такого у мотороллеров. Про исходные ПДП не помню, но и там, думаю, нет.

Ты это о чём? О пространстве адресов ввода-вывода, мотороллерах и прочем в исходной задаче не говорилось, да и для её решения не требуется. А вот о языке C — говорилось.
Для начала я подожду от тебя правильного понимания задачи, чего пока что не наблюдается.

А я всё жду от тебя хоть какого-нибудь решения поставленной задачи. Именно решения — программы, а не отсылок к man. То есть хочется компилируемую C-программу (и желательно, не только под BSD — а то мне эту штуку ещё ставить придётся). Это решение нужно мне в сугубо меркантильных интересах — сравнить эффективность моего и чужого решения при обязательном условии правильности обоих. Особенно меня интересует решение, которое было бы эффективнее моего — изучая его я смогу чему-то научиться.
А вот трёп по поводу драйверов клавиатуры, контроллеров и т.д. меня в данный момент мало интересует. (По поводу драйвера клавиатуры интересует, но не трёп, а конкретный программный модуль. Сильнее всего, меня интересует перекодирование из scan-кодов в коды символов заданной раскладки. Желательно, чтобы поддерживались нетривиальные раскладки, типа utf8. Опять же, меня это интересует в чисто меркантильных интересах, потому что у меня опыт написания драйвера клавиатуры исчерпывается статически заданной ASCII-раскладкой.)

Olyalyau

Я не знаю, что там у разработчиков std::string, а что там у тебя. Мне вообще плевать, за 0.0001 секунду моя программа ответит или за 0.00015. На реальных проектах большой оптимизации такими мелочами ты не получишь. Зато код они засорят будь здоров.
Относительно того цикла ты прав — его можно было ценой некоторой потери эффективности переписать на ~5 строк короче.
А вот по поводу std::string — не прав. Код std::string сильнее засоряет программу, чем моя реализация строк, просто потому, что мой вариант проще. В моём варианте кода меньше и он ведёт себя более предсказуемо (освобождает память сразу после удаления строки). std::string некоторую выделенную им память (как я уже писал внутренний буфер для коротких строк) вообще не освобождает. А это засоряет не только код программы, но и логику её работы. Если бы при этом их код был быстрее моего или имел бы какие-либо другие очевидные преимущества — я бы ещё мог понять их подход к реализации. А так — я вижу только бессмысленное усложнение кода и логики его работы.
Впрочем, на мой изначальный вопрос ты вполне ответил.

Хоть это радует

Ivan8209

> А я всё жду от тебя хоть какого-нибудь решения поставленной задачи.
> Именно решения — программы, а не отсылок к man.
Конкретные ответы я даю только на конкретные вопросы.
В том виде, в котором задачу поставил , конкретного решения
быть не может, и я уже объяснял, почему.
---
"Аллах не ведёт людей неверных."

kokoc88

> А я всё жду от тебя хоть какого-нибудь решения поставленной задачи.
> Именно решения — программы, а не отсылок к man.
Конкретные ответы я даю только на конкретные вопросы.
Читать: Кохтпа не умеет программировать. Он может только всех вокруг опускать.
В том виде, в котором задачу поставил , конкретного решения
быть не может, и я уже объяснял, почему.

Все поняли. Просто кто-то не умеет писать код. И вообще решать прикладные задачи. Зато у этого кого-то всегда чешутся руки что-нибудь обосрать.

Ivan8209

> И вообще решать прикладные задачи.
"Считать с клавиатуры" относится к системным задачам, а не прикладным,
если брать классическую парадигму программирования. Правда, тебе это
не может быть известно.
К сведению, в настоящее время я читаю с клавиатуры с помощью define-key,
global-set-key и read-string. Тебе этого, как показал опыт, не осилить.
---
"Аллах не ведёт людей неверных."

kokoc88

"Считать с клавиатуры" относится к системным задачам, а не прикладным,
если брать классическую парадигму программирования. Правда, тебе это
не может быть известно.
Системные задачи ты тоже решать умеешь. (И с каких пор ты стал считать себя классиком? )
К сведению, в настоящее время я читаю с клавиатуры с помощью define-key,
global-set-key и read-string. Тебе этого, как показал опыт, не осилить.

Я с клавиатуры читаю глазами. Мне для этого помощь не требуется.

Olyalyau


Читать: Кохтпа не умеет программировать. Он может только всех вокруг опускать.

Похоже, он и этого не может
Оставить комментарий
Имя или ник:
Комментарий: