Быстрее, чем Scanf? - PullRequest
Новая
       16

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

6 голосов
/ 13 декабря 2011

Я делал массивный анализ натуральных чисел, используя 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 цифры)?

Ответы [ 4 ]

7 голосов
/ 17 января 2015

Сверху я столкнулся не с самим анализом, а с многочисленными вызовами 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;
}

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

4 голосов
/ 13 декабря 2011

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

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

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

1 голос
/ 17 января 2015

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

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

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

0 голосов
/ 13 декабря 2011

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

  • числа находятся в диапазоне 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() подход.

...