Буферизированное чтение из использования stdin, освобожденного в C

Одна вещь, которая меня смущает, - это то, почему вы одновременно включаете полную буферизацию внутри объекта потока с помощью вызова setvbuf и выполняете собственную буферизацию, считывая полный буфер в buf .

Я понимаю необходимость буферизации, но это немного излишне.

Я рекомендую вам использовать setvbuf и удалить собственную буферизацию. Причина в том, что реализация собственной буферизации может быть сложной задачей. Проблема в том, что произойдет, когда токен (в вашем случае число) пересечет границу буфера. Например, предположим, что ваш буфер составляет 8 байтов (всего 9 байтов для конечного NULL), а ваш входной поток выглядит как

12345 12345

При первом заполнении буфера вы получаете:

"12345 12"

, а при втором заполнении буфера вы получаете :

"345"

Правильная буферизация требует от вас обработки этого случая, поэтому вы обрабатываете буфер как два числа {12345, 12345}, а не как три числа {12345, 12, 234}.

Поскольку stdio уже делает это за вас, просто используйте это. Продолжайте вызывать setvbuf , избавьтесь от fread и используйте scanf для чтения отдельных номеров из входного потока.

Я порекомендую попробовать полную буферизацию с помощью setvbuf и исключить fread . Если в спецификации указано, что в каждой строке есть одно число, я буду считать это само собой разумеющимся, используйте fgets для чтения всей строки и передайте его в strtoul , чтобы проанализировать предполагаемое число быть на этой линии.

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INITIAL_BUFFER_SIZE 2 /* for testing */

int main(void) {
    int n;
    int divisor;
    int answer = 0;
    int current_buffer_size = INITIAL_BUFFER_SIZE;
    char *line = malloc(current_buffer_size);

    if ( line == NULL ) {
        return EXIT_FAILURE;
    }

    setvbuf(stdin, (char*)NULL, _IOFBF, 0);

    scanf("%d%d\n", &n, &divisor);

    while ( n > 0 ) {
        unsigned long dividend;
        char *endp;
        int offset = 0;
        while ( fgets(line + offset, current_buffer_size, stdin) ) {
            if ( line[strlen(line) - 1] == '\n' ) {
                break;
            }
            else {
                int new_buffer_size = 2 * current_buffer_size;
                char *tmp = realloc(line, new_buffer_size);
                if ( tmp ) {
                    line = tmp;
                    offset = current_buffer_size - 1;
                    current_buffer_size = new_buffer_size;
                }
                else {
                    break;
                }
            }
        }
        errno = 0;
        dividend = strtoul(line, &endp, 10);
        if ( !( (endp == line) || errno ) ) {
            if ( dividend % divisor == 0 ) {
                answer += 1;
            }
        }
        n -= 1;
    }

    printf("%d\n", answer);
    return 0;
}

Я использовал сценарий Perl для генерации 1 000 000 случайных целых чисел от 0 до 1 000 000 и проверил, делятся ли они на 5 после компиляции этой программы с gcc версии 3.4.5 (mingw-vista special r3) на моем компьютере. Ноутбук с Windows XP. Все это заняло менее 0,8 секунды.

Когда я отключил буферизацию с помощью setvbuf (stdin, (char *) NULL, _IONBF, 0); , время увеличилось примерно до 15 секунд.

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

Поскольку это похоже на Posix (исходя из того факта, что вы используете gcc), просто введите ctrl-D (то есть, удерживая кнопку управления, нажмите / отпустите d), что приведет к тому, что EOF будет достиг.

Если вы используете Windows, я полагаю, вы используете вместо него ctrl-Z .

Вы можете использовать значение n, чтобы остановить чтение входных данных после того, как вы увидите n целых чисел.

Измените условие внешнего цикла while на:

while(n > 0 && fread(buf, sizeof('1'), BUFSIZE, stdin))

и измените тело внутреннего цикла на:

{
  n--;
  if(tmp%k == 0)  ++ans;
}

Проблема, с которой вы продолжаете сталкиваться, заключается в том, что поскольку вы никогда не изменяете buf во внутреннем цикле while, sscanf продолжает читать одно и то же число снова и снова.

Если вы перейдете на использование strtol() вместо sscanf(), то вы сможете использовать выходной параметр endptr для перемещения по буферу по мере чтения чисел.

Внешний цикл while () завершится только тогда, когда чтение из stdin вернет EOF . Это может произойти только при достижении фактического конца файла во входном файле или при завершении процесса записи во входной канал. Следовательно, оператор printf () никогда не выполняется. Я не думаю, что это имеет какое-либо отношение к вызову setvbuf () .

Ну, прямо с самого начала, scanf("%d%d",&n,&k) запихнет значение только в n и молча оставит k неустановленным - Вы увидите это, если проверите возвращаемое значение scanf(), которое скажет вам, сколько переменных оно заполнило. Я думаю, вам нужна scanf("%d %d",&n,&k) с пробелом.

Во-вторых, n - это количество итераций, но вы проверяете "n>0", но никогда не уменьшаете его. Следовательно, n>0 всегда истинно, и цикл не завершится.

Как уже кто-то упоминал, передача stdin по трубе приводит к выходу цикла, потому что в конце stdin есть EOF, что заставляет fread() вернуть NULL, выходя из цикла. Вероятно, вы хотите добавить "n=n-1" или "n--" где-то здесь.

Далее, в вашем sscanf, %n - не совсем стандартная вещь; я не уверен, для чего она предназначена, но она может ничего не делать: scanf() обычно останавливает разбор при первом нераспознанном идентификаторе формата, что здесь ничего не делает (поскольку вы уже получили свои данные), но это плохая практика.

Наконец, если важна производительность, то лучше вообще не использовать fread() и т.п., поскольку они не отличаются высокой производительностью. Посмотрите на isdigit(3) и iscntrl(3) и подумайте, как можно разобрать числа из буфера необработанных данных, считанных с помощью read(2).

Причина, по которой вся эта постоянная оптимизация оказывает незначительное влияние на время выполнения, заключается в том, что в операционных системах типа * nix и Windows ОС обрабатывает все операции ввода-вывода и из файловой системы и реализует 30-летние исследования, уловки и хитрости, чтобы сделать это очень эффективно.

Буферизация, которой вы пытаетесь управлять, - это просто блок памяти, используемый вашей программой. Таким образом, любое увеличение скорости будет минимальным (эффект от выполнения 1 большого "mov" стиха 6 или 7 меньших инструкций "mov").

Если вы действительно хотите ускорить этот процесс, попробуйте «mmap», который позволяет получить прямой доступ к данным в буфере файловой системы.

Если вам нужна максимальная скорость и вы работаете на платформе POSIX, подумайте об использовании отображения памяти. Я взял ответ Синана, используя стандартный ввод-вывод, и рассчитал его по времени, а также создал программу ниже, используя отображение памяти. Обратите внимание, что отображение памяти не будет работать, если источником данных является терминал или канал, а не файл.

При одном миллионе значений от 0 до одного миллиарда (и фиксированном делителе 17) среднее время для двух программ было:

• стандартный ввод-вывод: 0,155 с
• отображенная память: 0,086 с

Грубо говоря, ввод-вывод с отображением в память в два раза быстрее, чем стандартный ввод-вывод.

В каждом случае хронометраж повторялся 6 раз после игнорирования прогрева. Командные строки были следующими:

time fbf < data.file    # Standard I/O (full buffering)
time mmf < data.file    # Memory mapped file I/O

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>

static const char *arg0 = "**unset**";
static void error(const char *fmt, ...)
{
    va_list args;
    fprintf(stderr, "%s: ", arg0);
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(EXIT_FAILURE);
}

static unsigned long read_integer(char *src, char **end)
{
    unsigned long v;
    errno = 0;
    v = strtoul(src, end, 0);
    if (v == ULONG_MAX && errno == ERANGE)
        error("integer too big for unsigned long at %.20s", src);
    if (v == 0 && errno == EINVAL)
        error("failed to convert integer at %.20s", src);
    if (**end != '\0' && !isspace((unsigned char)**end))
        error("dubious conversion at %.20s", src);
    return(v);
}

static void *memory_map(int fd)
{
    void *data;
    struct stat sb;
    if (fstat(fd, &sb) != 0)
        error("failed to fstat file descriptor %d (%d: %s)\n",
              fd, errno, strerror(errno));
    if (!S_ISREG(sb.st_mode))
        error("file descriptor %d is not a regular file (%o)\n", fd, sb.st_mode);
    data = mmap(0, sb.st_size, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);
    if (data == MAP_FAILED)
        error("failed to memory map file descriptor %d (%d: %s)\n",
              fd, errno, strerror(errno));
    return(data);
}

int main(int argc, char **argv)
{
    char *data;
    char *src;
    char *end;
    unsigned long k;
    unsigned long n;
    unsigned long answer = 0;
    size_t i;

    arg0 = argv[0];
    data = memory_map(0);

    src = data;

    /* Read control data */
    n = read_integer(src, &end);
    src = end;
    k = read_integer(src, &end);
    src = end;

    for (i = 0; i < n; i++, src = end)
    {
        unsigned long v = read_integer(src, &end);
        if (v % k == 0)
            answer++;
    }

    printf("%lu\n", answer);
    return(0);
}

Вот мой байтовый вариант:

/*

Buffered reading from stdin using fread in C,
http://stackoverflow.com/questions/2371292/buffered-reading-from-stdin-for-performance

compile with:
gcc -Wall -O3  fread-stdin.c

create numbers.txt:
echo 1000000 5 > numbers.txt
jot -r 1000000 1 1000000 $RANDOM >> numbers.txt

time -p cat numbers.txt | ./a.out

*/

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

#define BUFSIZE 32

int main() {

   int n, k, tmp, ans=0, i=0, countNL=0;
   char *endp = 0;

   setvbuf(stdin, (char*)NULL, _IOFBF, 0);       // turn buffering mode on
   //setvbuf(stdin, (char*)NULL, _IONBF, 0);     // turn buffering mode off

   scanf("%d%d\n", &n, &k);

   char singlechar = 0;
   char intbuf[BUFSIZE + 1] = {0};

   while(fread(&singlechar, 1, 1, stdin))     // fread byte-by-byte
   {
      if (singlechar == '\n') 
      {
         countNL++;
         intbuf[i] = '\0';
         tmp = strtoul(intbuf, &endp, 10);
         if( tmp % k == 0) ++ans;
         i = 0;
      } else {
         intbuf[i] = singlechar; 
         i++;
      }
      if (countNL == n) break;
   }

   printf("%d integers are divisible by %d.\n", ans, k);
   return 0;

}

Можете также взглянуть на реализацию getline:

http://www.cpax.org.uk/prg/portable/c/libs/sosman/index.php

(Процедура ISO C для получения строки данных неизвестной длины из потока.)