Gepuffertes Lesen von stdin mit fread in C

Werde ich empfehlen, versucht die volle Pufferung mit setvbuf und Notwasserung fread. Wenn die Spezifikation ist, dass es eine Zahl pro Zeile, ich werde Sie nehmen, dass für selbstverständlich halten, verwenden fgets zu Lesen, in eine komplette Linie und übergeben es an strtoul analysieren, die Nummer, die sein sollte, in der Zeile.

#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;
}

Verwendete ich ein Perl-Skript zum erstellen von 1.000.000 zufällige Ganzzahlen zwischen 0 und 1.000.000 und überprüft, wenn Sie teilbar durch 5 nach dem kompilieren das Programm mit gcc version 3.4.5 (mingw-vista special r3) auf meinem Windows XP-laptop. Die ganze Sache dauerte weniger als 0,8 Sekunden.

Als ich mich umdrehte Pufferung aus mit setvbuf(stdin, (char*)NULL, _IONBF, 0);, die Zeit ging bis etwa 15 Sekunden.

Version 1 : Mit getchar_unlocked wie vorgeschlagen von R Samuel Klatchko (siehe Kommentare)

#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;
}

Version 2: Mit fread zu Lesen, dass ein block-und Analyse-Nummer von ihm.

#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;
}

Ergebnisse: (10 Millionen zahlen getestet für die Teilbarkeit durch 11)

Run 1: ( Version 1 ohne setvbuf ) 0.782 Sek.

Run 2: ( Version 1 mit setvbuf ) 0.684 Sek.

Run 3: ( Version 2 ) 0.534

P. S. - Jedem ausführen kompiliert mit GCC -O1-flag

Wenn Sie nach aus-und-out-Geschwindigkeit, und Sie arbeiten auf einem POSIX-ish-Plattform, sollten Sie über die memory-mapping. Ich nahm Sinan die Antwort mit standard-I/O und zeitlich, und auch das Programm erstellt unter der Verwendung von Speicher-mapping. Beachten Sie, dass memory-mapping nicht funktioniert, wenn die Datenquelle ein terminal oder eine pipe und nicht eine Datei.

Mit einer million Werte zwischen 0 und einer Milliarde (und einen festen Teiler von 17), die durchschnittlichen Zeiten für die beiden Programme wurde:

• standard-I/O: 0.155 s
• memory-mapped: 0.086 s

Grob, memory-mapped I/O ist doppelt so schnell wie standard-I/O.

In jedem Fall war das timing wiederholt 6 mal, nach ignorieren ein warm-up-run. Den Befehl Linien auf:

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);
}

Gut, direkt aus der Spitze, scanf("%d%d",&n,&k) wird shove einen Wert in n nur still und leise verlassen k unset - würde Sie sehen, wenn Sie überprüft den Rückgabewert von scanf(), die Ihnen sagt, wie viele Variablen es gefüllt. Ich denke, Sie wollen scanf("%d %d",&n,&k) mit dem Raum.

Zweite ist n die Anzahl der Iterationen, die ausgeführt werden können, aber Sie testen für "n>0" noch nie verringern es. Ergo, n>0 ist immer true und die Schleife wird nicht verlassen.

Als jemand anderes erwähnt, Fütterung stdin über eine pipe bewirkt, dass die Schleife zu beenden, da das Ende von stdin hat ein EOF, was bewirkt, dass fread() NULL zurück, verlassen der Schleife. Wahrscheinlich möchten Sie fügen Sie ein "- n=n-1" oder "n--" irgendwo in dort.

Nächsten, in deiner sscanf, %n ist nicht wirklich eine standard-Sache; ich bin nicht sicher, was es bedeutete, zu tun, aber es kann nichts tun: scanf() in der Regel Stoppt das Parsen bei der ersten unbekanntes format identifier, die nichts anderes tut als hier (denn Sie haben bereits Ihre Daten), sondern ist eine schlechte Praxis.

Schließlich, wenn die Leistung wichtig ist, solltest du besser nicht mit fread() etc auf alle, wie Sie sind nicht wirklich hohe Leistung. Blick auf isdigit(3) und iscntrl(3) und denke darüber nach, wie Sie analysieren die zahlen aus einem raw-Daten-buffer Lesen mit read(2).

Mabe auch einen Blick auf dieses getline Umsetzung:

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

(Eine ISO-C-routine, um eine Zeile von Daten, Länge unbekannt, aus einem stream.)

Hier ist mein byte-by-byte nehmen:

/*

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;

}