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

8

Я пытаюсь эффективно читать из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 (чего не может) или вообще ничего.

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

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

редактировать
Полная спецификация проблемы

Ваш Ответ

11   ответов
1

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

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

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

Я это работает. но у меня все еще есть проблема, sscanf () сканирует только первое целое число, в каждом цикле значение temp является первым целым числом. N 1.1
опубликовал решение с getchar_unlocked () и анализ. Могу ли я улучшить это больше? N 1.1
2

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

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

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

12345 12345

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

"12345 12"

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

"345"

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

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

и к вашему сведению, я сначала попробовал использовать только setvbuf, затем я также получал примерно то же время выполнения (~ 5 сек). Я просто хочу ускорить ввод-вывод в любом случае. N 1.1
@ samuel: пожалуйста, смотрите мой ответ :) N 1.1
Теперь вы точно поняли мою проблему. Для правильного понимания, я все еще хотел бы сделать это, используя fread :). Хотя, следующая вещь будет делать только с setvbuf. N 1.1
setvbuf иногда может бытьочень эффективный. Например, это очень помогло установить его на 1 МБ в случае чтения фрагментов данных размером 45 КБ с SD-карты. Без него чтение может занимать до полсекунды, но теперь это занимает менее 0,05 с. Albus Dumbledore
Если у вас нет ужасно плохой версии stdio, вы не получите существенного ускорения, выполняя собственную буферизацию. R Samuel Klatchko
-1

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

Я уже знал, что вы ответили здесь, но как мне остановить фред? И я не заявляю, что проблема связана с setvbuf. N 1.1
Итак, если я правильно понимаю, вы устанавливаете размер буфера в stdin на какое-то значение, а затем читаете из него. Вы, вероятно, должны опустить вызов fread () и изменить вызов sscanf () на fscanf (). Первый такой вызов должен прочитать байты BUFSIZE во внутренний (внутренний) буфер потока, затем последующие вызовы передадут его вам по одной строке за раз. Max
ты прочитал вопрос полностью ?? Пожалуйста, прочитайте его и, пожалуйста, не размещайте ответ, прежде чем сделать это. N 1.1
Я полностью прочитал ваш вопрос, поэтому я не стеснялся предлагать лучший подход - не используйте fread () Max
ну вот и весь смысл :). Я должен использовать фред, чтобы потреблять огромные ресурсы. N 1.1
0

% 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).

scanf ("% d% d", & n, & k) не проблема. - на самом деле там. Был удален по ошибке сейчас. % n хранит количество прочитанных символов. N 1.1
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, ÷nd);
  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

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

Ваш вывод неверен. Половина вашего ускорения происходит от выполнения преобразования вашего собственного символа -> числа вместо использования scanf. Другая половина заключается в том, что блокировка stdio может добавить немного накладных расходов. Попробуйте это: 1) включить вызовsetvbuf2) читать данные побайтно сgetchar_unlocked а не с фредом. Вы получите аналогичное ускорение. R Samuel Klatchko
@Sinan ünür: Это решение проблемы (от SPOJ), в которой четко сказано, что в каждой строке есть только 1 номер. Так что я учел только это. Конечно, это не общее решение. Кстати, я уже говорил об этом в своем вопросе! N 1.1
Почему отрицательные голоса? !! N 1.1
@ Самуил: хорошо. попробую сегодня. N 1.1
0

n прекратить чтение ввода после того, как вы увиделиn целые числа.

Изменить состояние внешнегоwhile цикл до:

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

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

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

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

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

Вы также должны изменитьsscanf строка, смотрите обновленный ответ. caf
теперь я использую n> 0 && sscanf (buf, "% d", & tmp), хотя это останавливается, но напечатанный ответ неверен. И каждое число находится в отдельной строке, так что я думаю, sscanf (buf, "\ n% d", & tmp) N 1.1
@caf проверь мой ответ. Это стоило дополнительных усилий :) N 1.1
я. поэтому я использую другую переменную i, чтобы отслеживать положение. но если буфер останавливает чтение между числом (читает 23 из последнего числа 2354), то у меня есть проблема. N 1.1
-1

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

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

не помогает вообще. N 1.1
3

Я собираюсь рекомендовать попробовать полную буферизацию с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 секунд.

Не могли бы вы объяснить причину рваfread и перейти кsetvbuf? Cacahuete Frito
Итак, пункты: 1) нет причин пытаться устранить буферизованный ввод-вывод; 2) нет веских оснований для того, чтобы считывать двоичные блоки и разбирать числа за цифрой. Вместо этого полагайтесь на буферизацию и анализ библиотеки. Sinan Ünür
-1

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

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

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

Как и предполагал Синан, ускорение было значительным. От 5 секунд до 0,8 секунд. Что ты сейчас скажешь: P? N 1.1
1

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

При одном миллионе значений от 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);
}
@ Джонатан Леффлер: Спасибо за ответ :). Теперь решение, которое я разместил (используя fread), также делает это в 0.08secs. Таким образом, с MMAPed IO нет значительного улучшения. Я отредактировал вопрос, проверьте изменения. N 1.1
-1

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

/*

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;

}
Используя те же данные, приведенный выше код занимает 9,389 с против 0,572 с (для ответа, который я отправил) с флагом -O3. N 1.1

Похожие вопросы