Estoy tratando de leer eficazmente desde el stdin mediante setvbuf en `_IOFBF~ modo. Soy nuevo en el almacenamiento en búfer. Estoy buscando de trabajo ejemplos.

La entrada comienza con dos números enteros (n,k). El próximo n líneas de entrada contienen 1 entero. El objetivo es imprimir cuántos números enteros son divisibles por 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;
}

El problema es que si el número está en el límite, la búfer buf leerá 23 de 2354\n, cuando debía leer 2354 (que no se puede) o nada en absoluto.

¿Cómo puedo solucionar este problema?


Editar
Resuelto ahora (con análisis).

Editar
Completar La Especificación Del Problema

OriginalEl autor |

11 Comentarios

  1. 3

    Voy a recomendar tratando de búfer completo con setvbuf y amaraje fread. Si la especificación es que hay un número por línea, voy a tomar eso por descontado, el uso de fgets a leer en una línea completa y se pasa a strtoul analizar el número que se supone que está en esa línea.

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

    He utilizado un script en Perl para generar 1.000.000 de enteros aleatorios entre 0 y 1 000 000 y se comprueba si fueran divisibles por 5 después de compilar este programa con gcc version 3.4.5 (mingw-vista special r3) en mi Windows XP del portátil. Todo duró menos de 0,8 segundos.

    Cuando he activado el almacenamiento en búfer fuera de uso setvbuf(stdin, (char*)NULL, _IONBF, 0);, el tiempo se fue hasta alrededor de 15 segundos.

    OriginalEl autor Sinan Ünür

  2. 2

    Una cosa que me parece confuso es la razón por la que ambos están permitiendo la plena búfer dentro de la secuencia de objetos a través de la llamada a setvbuf y hacer su propio búfer mediante la lectura de un búfer completo en buf.

    Entiendo la necesidad de hacer buffering, pero que es un poco excesivo.

    Voy a recomendar a usted se pega con setvbuf y eliminar su propio búfer. La razón es que la aplicación de su propio búfer puede ser complicado. El problema es qué va a pasar cuando un token (en el caso de un número) se extiende el límite de búfer. Por ejemplo, digamos que el buffer es de 8 bytes (9 bytes total de NULL final) y su flujo de entrada se ve como

    12345 12345

    La primera vez que se llena el buffer que se obtiene:

    "12345 12"

    mientras que la segunda vez que se llena el buffer que se obtiene:

    "345"

    Adecuado almacenamiento en búfer requiere que usted para manejar ese caso por lo que tratar el buffer, como los dos números {12345, 12345} y no tres números {12345, 12, 234}.

    Desde stdio asas que ya para usted, sólo tiene que utilizar. Seguir llamando setvbuf, deshacerse de la fread y uso scanf para leer los números individuales de la secuencia de entrada.

    Ahora tienes mi problema exactamente. Para la correcta comprensión, todavía me gustaría hacerlo con fread :). Aunque, lo siguiente será hacer sólo con setvbuf.
    y para tu INFORMACIÓN, lo probé por primera vez con el uso de sólo setvbuf solo, entonces también estaba recibiendo alrededor de la misma en tiempo de ejecución (~5secs). Sólo quiero acelerar el IO de todos modos.
    A menos que usted tenga una horriblemente mala versión de stdio, usted no va a conseguir ninguna aceleración significativa haciendo su propio búfer.
    amablemente ver mi respuesta 🙂
    setvbuf a veces puede ser es en efectivo. Por ejemplo, lo hizo de gran ayuda para establecer a 1 mb en el caso de la lectura de 45KB fragmentos de datos desde una tarjeta SD. Sin uso, la lectura podría tomar hasta la mitad de un segundo en el tiempo, pero ahora se tarda menos de 0.05 seg.

    OriginalEl autor R Samuel Klatchko

  3. 2

    Versión 1 : el Uso de getchar_unlocked como sugiere R Samuel Klatchko (ver comentarios)

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

    Versión 2: Uso de fread para leer un bloque de análisis y el número de ella.

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

    Resultados: (10 millones de números de prueba de divisibilidad por 11)

    Ejecutar 1: ( Versión 1 sin setvbuf ) 0.782 secs

    Ejecutar 2: ( Versión 1 con setvbuf ) 0.684 secs

    3: ( Versión 2 ) 0.534

    P. S. – Cada carrera compilado con GCC usa-O1 bandera

    Buena solución para el problema de los números que potencialmente podrían ser de un corte en el extremo de un buffer, pero ¿qué pasa si una línea se compone de "z\n"?
    Su conclusión es incorrecta. La mitad de su speedup viene de hacer su propio carácter -> número de conversión en lugar de usar scanf. La otra mitad es que stdio bloqueo puede agregar un poco de sobrecarga. Prueba esto: 1) activar la llamada a setvbuf, 2) leer los datos byte a byte con getchar_unlocked en lugar de con fread. Usted obtendrá una similar speedup.
    bien. va a probar hoy.
    Esta es la solución a un problema de especificación (de SPOJ), que dice claramente que sólo hay 1 número en cada línea. Por lo que me han explicado que sólo. Por supuesto, esto no es una solución general. Por CIERTO me han mencionado que en mi pregunta!
    Por qué la baja de votos ?!!

    OriginalEl autor N 1.1

  4. 1

    El problema cuando usted no está utilizando la redirección es que no están causando EF.

    Ya que éste parece ser Posix (basado en el hecho de que usted está usando gcc), justo el tipo de ctrl-D (es decir, mientras que pulsando el botón control, presione/suelte d) que hará EF a ser alcanzado.

    Si está utilizando Windows, creo que el uso de ctrl-Z lugar.

    ya que funciona. pero todavía tengo un problema, sscanf() analiza sólo el primer entero, en cada bucle el valor de temp es el primer número entero.
    publicó una solución con getchar_unlocked() y un análisis. Puedo mejorar más?

    OriginalEl autor R Samuel Klatchko

  5. 1

    Si usted es después de que fuera-y-hacia fuera de la velocidad y de trabajar en un POSIX-ish plataforma, considere el uso de la asignación de memoria. Tomé Sinan respuesta utilizando el estándar de e/S y el tiempo, y también se creó el programa a continuación mediante la asignación de memoria. Tenga en cuenta que la asignación de memoria no funcionará si el origen de datos es una terminal o en un tubo y no un archivo.

    Con un millón de valores entre 0 y un millones (y un divisor fijo de 17), el promedio de los tiempos de los dos programas fue:

    • de e/S estándar: 0.155 s
    • de memoria asignada: 0.086 s

    Aproximadamente, de la memoria de e/S asignada es dos veces tan rápido como estándar de I/O.

    En cada caso, el momento en que se repitió 6 veces, después de ignorar un warm-up de ejecución. El comando líneas fueron:

    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);
    }
    Leffler: Gracias por la respuesta :). Ahora, la solución que he publicado (utilizando fread) también lo hace en 0,08 segundos. Así que no hay ninguna mejora significativa con MMAPed IO. He editado la pregunta, comprobar los cambios.

    OriginalEl autor

  6. 0

    Puede utilizar el valor de n a dejar de leer la entrada después de haber visto n enteros.

    Cambiar la condición del exterior while bucle:

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

    y cambiar el cuerpo de la interna:

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

    El problema continúa a tener es que porque nunca se ajuste buf en el interior de la while bucle, sscanf sigan leyendo el mismo número una y otra vez.

    Si cambia a utilizar strtol() en lugar de sscanf(), entonces usted puede utilizar el endptr parámetro de salida para moverse a través del buffer, como los números se leen.

    ya he probado que, aún no funciona.
    También es necesario cambiar el sscanf cadena, ver respuesta actualizada.
    ahora estoy usando n>0 && sscanf(buf,»%d»,&tmp), a pesar de que se detenga, pero la respuesta impreso está mal. Y cada número está en una línea diferente, así que supongo que sscanf(buf, «\n%d», &tmp)
    Si usted nunca cambio buf en el bucle interno, sscanf se sigue buscando en la misma entrada y ver el mismo número.
    ya. así que estoy utilizando otra variable i para guardar la pista de su posición. pero si el búfer deja de leer entre un número (lee 23 de último número 2354), entonces tengo un problema.

    OriginalEl autor caf

  7. 0

    Bien, a la derecha, en la parte superior, scanf(«%d%d»,&n,&k) empujar un valor en n solo y en silencio, dejar k unset – este si se comprueba el valor de retorno de scanf(), que indica cuántas variables se llena. Yo creo que se quiere scanf(«%d %d»,&n,&k) con el espacio.

    Segunda, n es el número de iteraciones a ejecutar, pero para hacer la prueba de «n>0», pero nunca disminuir. Ergo, n>0 es siempre verdadera y el bucle no salir.

    Como alguien mencionó, la alimentación de la entrada estándar a través de una tubería hace que el bucle porque el fin de stdin tiene un EF, que hace que fread() para devolver un valor NULO, salir del bucle. Usted probablemente desea agregar un «n=n-1» o «n» en algún lugar de allí.

    Siguiente, en su sscanf, %n no es realmente una cosa estándar; no estoy seguro de lo que se supone que debe hacer, pero se puede hacer nada: scanf() por lo general deja de análisis en el primer formato no reconocido identificador, que no hace nada aquí (ya que ya tengo los datos, pero es una mala práctica.

    Finalmente, si el rendimiento es importante, que sería mejor no usar fread (), etc, como que no son verdaderamente de alto rendimiento. Mira isdigit(3) y iscntrl(3) y pensar en cómo se podría analizar los números de un sistema de datos del búfer de lectura con la lectura(2).

    scanf(«%d%d»,&n,&k) no es ningún problema. –n es realmente allí. Fue eliminado por error ahora. %n almacena el número de caracteres a leer.

    OriginalEl autor user205666

  8. -1

    La ultraperiféricas while() bucle sólo saldrá cuando la lectura de stdin devuelve EOF. Esto sólo puede suceder cuando se alcance el final real-de-archivo en un archivo de entrada, o si el proceso de escritura de una entrada de la tubería sale. De ahí el printf() instrucción no se ejecuta nunca. No creo que esto tenga nada que ver con la llamada a setvbuf().

    Yo ya sabía lo que han respondido aquí, pero ¿cómo hago para dejar de fread? Y no me indica que el problema es debido a setvbuf.
    OK, si entiendo correctamente, se establece el tamaño del buffer de entrada para algún valor, entonces la lectura de la misma. Probablemente, usted debe omitir la llamada a fread(), y cambiar el sscanf() llamada a fscanf(). La primera de estas llamadas deben leer BUFSIZE de bytes en el flujo (interna) de búfer, a continuación, las llamadas posteriores de la mano a usted una línea a la vez.
    has leído la pregunta?? por favor de leer y por favor no publicar respuesta antes de hacerlo.
    He leído tu pregunta, así que me sentí libre de proponer un mejor enfoque – no utilizar fread()
    bueno esa es toda la idea :). Tengo que usar fread a consumir grandes entradas.

    OriginalEl autor Max

  9. -1

    La razón de todo esto permature optimización tiene un negligable efecto en el tiempo de ejecución es que en *nix y windows tipo de sistemas operativos el sistema operativo se encarga de todas las e/S y del sistema de archivos y los implementos de 30 años de investigación, el engaño y el engaño para hacer esto de manera muy eficiente.

    El almacenamiento en búfer usted está tratando de controlar es simplemente el bloque de memoria utilizada por el programa. Por lo que cualquier aumento de la velocidad será mínimo (el efecto de hacer 1 grande ‘mov’ los versículos 6 o 7 menor ‘mov’ instrucciones).

    Si realmente quieres aumentar tu velocidad, tratar de «mmap», que permite el acceso directo a los datos en los sistemas de archivo de búfer.

    así como Sinan propuesto, la aceleración del ritmo fue significativa. De todo 5secs a 0.8 segundos. ¿Qué tienes que decir ahora 😛 ?

    OriginalEl autor James Anderson

  10. -1

    Aquí está mi byte por byte toma en ella:

    /*
    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;
    }
    Utilizando los mismos datos, el código anterior se lleva a 9.389 secs contra 0.572 segundos (para la respuesta que he presentado) con -O3 bandera.

    OriginalEl autor

Dejar respuesta

Please enter your comment!
Please enter your name here