Быстрее, чем Scanf?

Question

Я делал массивный анализ натуральных чисел, используя scanf("%d", &someint), Как я хотел увидеть, является ли scanf узким местом, я реализовал наивную целочисленную функцию синтаксического анализа, используя fread, как:

int result;
char c;

while (fread(&c, sizeof c, 1, stdin), c == ' ' || c == '\n')
    ;

result = c - '0';
while (fread(&c, sizeof c, 1, stdin), c >= '0' || c <= '9') {
     result *= 10;
     result += c - '0';
}

return result;

Но, к моему удивлению, производительность этой функции (даже с наклоном) примерно на 50% хуже. Разве не должно быть возможности улучшить scanf для специализированных случаев? не fread должен быть быстрым (дополнительная подсказка: целые числа (редактировать: в основном) 1 или 2 цифры)?

Answer 1

Сверху я столкнулся не с самим анализом, а с многочисленными вызовами fread (то же самое с fgetc, и друзья). Для каждого вызова libc должен блокировать входной поток, чтобы убедиться, что два потока не наступают друг другу на ноги. Блокировка - очень дорогая операция.

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

Если мы можем гарантировать, что существует только один поток, использующий входной поток, мы можем использовать функции из unlocked_stdio(3), такие как getchar_unlocked(3), Вот пример:

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while (isdigit((c = getchar_unlocked())))
        n = 10*n + c-'0';

    return n;
}

Вышеприведенная версия не проверяет наличие ошибок. Но это гарантированно прекратится. Если требуется обработка ошибок, может быть достаточно проверить feof(stdin) а также ferror(stdin) в конце, или пусть звонящий сделает это.

Моей первоначальной целью было представить решение проблем программирования в SPOJ, где вводом являются только пробелы и цифры. Таким образом, есть еще возможности для улучшения, а именно isdigit проверять.

static int parseint(void)
{
    int c, n;

    n = getchar_unlocked() - '0';
    while ((c = getchar_unlocked()) >= '0')
        n = 10*n + c-'0';

    return n;
}

Очень и очень трудно побороть эту процедуру синтаксического анализа, как с точки зрения производительности, так и с точки зрения удобства и удобства обслуживания.

Answer 2

Вы сможете значительно улучшить свой пример с помощью буферизации - прочитайте большое количество символов в память, а затем проанализируйте их из версии в памяти.

Если вы читаете с диска, вы можете получить увеличение производительности, если ваш буфер будет кратен размеру блока.

Изменить: вы можете позволить ядру обработать это для вас, используя mmap для отображения файла в память.

Answer 3

Вот что я использую.

 #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
 char _;

Однако это работает только с целыми числами.

Answer 4

Из того, что вы говорите, я извлекаю следующие факты:

• числа находятся в диапазоне 0-99, что составляет 10+100 различных строк (включая ведущие нули)
• Вы уверены, что ваш поток ввода соответствует какой-то спецификации и не будет содержать никаких неожиданных последовательностей символов

В этом случае я бы использовал таблицу поиска для преобразования строк в числа. Учитывая строку s[2], индекс вашей таблицы поиска может быть вычислен как s[1]*10 + s[0], меняя цифры и используя тот факт, что '\0' равняется 0 в ASCII.

Затем вы можете прочитать ваши данные следующим образом:

// given our lookup method, this table may need padding entries
int lookup_table[] = { /*...*/ };

// no need to call superfluous functions
#define str2int(x) (lookup_table[(x)[1]*10 + (x)[0]])

while(read_token_from_stream(stdin, buf))
        next_int = str2int(buf);

На современных машинах будет сложно придумать более быструю технику. Я думаю, что этот метод будет работать в 2-10 раз быстрее, чем любой scanf()подход.