Буферизованное чтение из stdin с использованием fread в C

Question

Я пытаюсь эффективно читать из stdin, используя setvbuf в режиме `_IOFBF ~. Я новичок в буферизации. Я ищу работающих примеров.

Ввод начинается с двух целых чисел (n, k). Следующие n строки ввода содержат 1 целое число. Цель состоит в том, чтобы напечатать, сколько целых чисел делится на k.

#define BUFSIZE 32
int main(){
  int n, k, tmp, ans=0, i, j;
  char buf[BUFSIZE+1] = {'0'};
  setvbuf(stdin, (char*)NULL, _IONBF, 0);
  scanf("%d%d\n", &n, &k);
  while(n>0 && fread(buf, (size_t)1, (size_t)BUFSIZE, stdin)){
    i=0; j=0;
    while(n>0 && sscanf(buf+j, "%d%n", &tmp, &i)){
    //printf("tmp %d - scan %d\n",tmp,i); //for debugging
      if(tmp%k==0)  ++ans;
      j += i; //increment the position where sscanf should read from
      --n;
    }
  }
  printf("%d", ans);
  return 0;
}

Проблема в том, что если число находится на границе, буфер buf будет читать 23 из 2354\n, когда он должен либо прочитать 2354 (что не может), либо ничего вообще.

Как я могу решить эту проблему?

---

Редактировать
Решено сейчас (с анализом) .

Редактировать
Полная спецификация задачи

Answer 1

Я собираюсь порекомендовать попробовать полную буферизацию с помощью 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 version 3.4.5 (mingw-vista special r3) на моем ноутбуке с Windows XP. Все это заняло менее 0,8 секунд.

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

Answer 2

Версия 1: использование getchar_unlocked в соответствии с предложением Р. Самуэля Клатчко (см. Комментарии)

#define BUFSIZE 32*1024
int main(){
  int lines, number=0, dividend, ans=0;
  char c;
  setvbuf(stdin, (char*)NULL, _IOFBF, 0);// full buffering mode
  scanf("%d%d\n", &lines, &dividend);
  while(lines>0){
    c = getchar_unlocked();
    //parse the number using characters
    //each number is on a separate line
    if(c=='\n'){
      if(number % dividend == 0)    ans += 1;
      lines -= 1;
      number = 0;
    }
    else
      number = c - '0' + 10*number;
  }

  printf("%d are divisible by %d \n", ans, dividend);
  return 0;
}

---

Версия 2: использование fread для чтения блока и разбор номера с него.

#define BUFSIZE 32*1024
int main(){
int lines, number=0, dividend, ans=0, i, chars_read;
char buf[BUFSIZE+1] = {0}; //initialise all elements to 0
scanf("%d%d\n",&lines, &dividend);

while((chars_read = fread(buf, 1, BUFSIZE, stdin)) > 0){
  //read the chars from buf
  for(i=0; i < chars_read; i++){
    //parse the number using characters
    //each number is on a separate line
    if(buf[i] != '\n')
      number = buf[i] - '0' + 10*number;
    else{
      if(number%dividend==0)    ans += 1;
      lines -= 1;
      number = 0;
    }       
  }

if(lines==0)  break;
}

printf("%d are divisible by %d \n", ans, dividend);
return 0;
}

---

Результаты: (10 миллионов чисел, проверенных на делимость на 11)

Прогон 1: (Версия 1 без setvbuf) 0,782 с
Прогон 2: (Версия 1 с setvbuf) 0,684 с
Прогон 3: (версия 2) 0,534

P.S. - Каждый прогон скомпилирован с GCC с использованием флага -O1

Answer 3

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

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

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

12345 12345

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

"12345 12"

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

"345"

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

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

Answer 4

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

При одном миллионе значений от 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);
}

Answer 5

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

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

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

Answer 6

Вот мой побайтовый подход:

/*

Buffered reading from stdin using fread in C,
/2048197/buferizovannoe-chtenie-iz-stdin-s-ispolzovaniem-fread-v-c

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;

}

Answer 7

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

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

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

Answer 8

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

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

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

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

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

Answer 9

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

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

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

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

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

---

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

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

Answer 10

Mabe также взглянем на эту реализацию getline:

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

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