9
votes

Lecture tamponnée de stdin en utilisant de la faille en c

J'essaie de lire efficacement à partir du stdin à l'aide de SETVBUF dans `_iofbf ~ mode. Je suis nouveau à tamponner. Je cherche travail exemples.

L'entrée commence par deux entiers ( n , k ). Le prochain n lignes d'entrée contient 1 entier. L'objectif est d'imprimer combien d'entiers sont divisibles par k . xxx

Le problème est si le numéro est à la limite, le tampon buf lira 23 à partir de 2354 \ n , quand il devrait avoir soit lu 2354 (qui Il ne peut ni) ni rien du tout.

Comment puis-je résoudre ce problème?


Modifier
Résolu maintenant (avec analyse) . < / p>

Modifier
Spécification complète du problème


0 commentaires

11 Réponses :


-1
votes

Le plus externe tandis que () La boucle ne quittera que lorsque la lecture de stdin retourne eof . Cela ne peut se produire que lorsque vous atteignez l'extrémité de fichier de fichier sur un fichier d'entrée ou si le processus écrit sur une conduite d'entrée est parti. D'où la déclaration printf () n'est jamais exécutée. Je ne pense pas que cela a quelque chose à voir avec l'appel à SETVBUF () .


5 commentaires

Je savais déjà ce que vous avez répondu ici, mais comment puis-je arrêter de fread? Et je n'ai pas indiqué que le problème est dû à SETVBUF.


OK, donc si je comprends correctement, vous définissez la taille de la mémoire tampon sur STDIN à une certaine valeur, puis en le lisant. Vous devriez probablement omettre l'appel à Fread () et changer l'appel SSCANF () à FSCANF (). Le premier appel de ce type devrait lire les octets de bufsize dans le tampon de flux (interne), puis les appels ultérieurs lui remettent une ligne à la fois.


Avez-vous lu la question complètement ?? Veuillez le lire et s'il vous plaît ne postez pas de réponse avant de le faire.


J'ai complètement lu votre question complètement, alors je me suis senti libre de proposer une meilleure approche - n'utilisez pas de fread ()


Eh bien c'est tout le point :). Je dois utiliser Fread pour consommer d'énormes entrées.



-1
votes

MABE Jetez également un coup d'oeil à cette implémentation de gaine:

http://www.cpax.org .uk / PRG / Portable / C / Libs / Sosman / Index.php

(une routine ISO C pour obtenir une ligne de données, une longueur inconnue, d'un flux.)


0 commentaires

0
votes

Vous pouvez utiliser la valeur de n pour arrêter la lecture de l'entrée après avoir vu n entiers.

changer l'état du tandis que boucle à: xxx

et modifier le corps de l'intérieur à: xxx


Le problème que vous continuez d'avoir est que, parce que vous n'ajusez jamais buf dans l'interne pendant boucle, sscanf continue à lire le même numéro et encore une fois.

Si vous passez à l'aide d'utiliser strtol () intead of sscanf () , vous pouvez utiliser le endptr Paramètre de sortie Pour passer à travers le tampon lorsque les chiffres sont lus.


7 commentaires

Vous devez également modifier la chaîne sscanf , voir la réponse mise à jour.


J'utilise maintenant N> 0 && SSCANF (BUF, "% D", & TMP), bien qu'il s'arrête, mais la réponse imprimée est fausse. Et chaque numéro est dans une ligne différente, donc je suppose que SCANF (buf, "\ n% d", & tmp)


Si vous ne changez jamais buf dans la boucle interne, sscanf continuera à regarder la même entrée et à voir le même numéro.


ya. J'utilise donc une autre variable I pour garder une trace de la position. Mais si le tampon cesse de lire entre un nombre (lit 23 du dernier numéro 2354), j'ai un problème.


Droit. Il est possible de gérer cela aussi, mais cela devrait vraiment vous dire que Fread est une cheville carrée et ce problème est un trou rond. Vous pouvez lire une ligne à la fois à l'aide de fgets () à la place.


@CAF: Il n'y aura pas de vitesse dans ce cas, chaque numéro est déjà sur une ligne différente maintenant.


@caf vérifier ma réponse. Ça valait l'effort supplémentaire :)



1
votes

Le problème lorsque vous n'utilisez pas la redirection, c'est que vous ne causez pas EOF.

Étant donné que cela semble être POSIX (basé sur le fait que vous utilisez GCC), tapez simplement Ctrl-d (c'est-à-dire tout en appuyant sur la touche de commande, appuyez sur / relâche D) qui causera EOF à être atteint.

Si vous utilisez Windows, je pense que vous utilisez ctrl-z à la place.


2 commentaires

ya ça marche. Mais j'ai toujours un problème, SSCANF () ne scanne que le premier entier, dans chaque boucle, la valeur de Temp est le premier entier.


Publié une solution avec getchar_unlocked () et une analyse. Puis-je l'améliorer plus?



2
votes

Une chose que je trouve déroutant est la raison pour laquelle vous avez la fois la mise en mémoire tampon complète dans l'objet de flux via l'appel à SETVBUF CODE> et faire votre propre tampon en lisant un tampon complet dans BUF Code>.

Je comprends la nécessité de faire tampon, mais c'est un peu surkill. P>

Je vais vous recommander de vous enregistrer avec SETVBUF CODE> et supprimez votre propre tampon . La raison pour laquelle la mise en œuvre de votre propre tampon peut être délicate. Le problème est ce qui se passera lorsqu'un jeton (dans votre cas un nombre) chevauche la limite de la mémoire tampon. Par exemple, disons que votre mémoire tampon est de 8 octets (9 octets totaux pour la null de la trailing) et votre flux d'entrée ressemble à p> xxx pré>

la première fois que vous remplissez le tampon que vous obtenez: xxx pré>

tandis que la deuxième fois que vous remplissez le tampon, vous obtenez: p>

"345"


5 commentaires

Maintenant, tu as mon problème exactement. Pour une bonne compréhension, j'aimerais toujours le faire en utilisant Fread :). Bien que la prochaine chose sera à faire avec juste setvbuf.


et FYI, j'ai d'abord essayé d'utiliser simplement SetVbuf seul, puis je me faisais aussi autour du même temps d'exécution (~ 5Secs). Je veux juste accélérer l'Io de toute façon.


À moins que vous n'ayez une version horriblement mauvaise de Stdio, vous n'allez pas obtenir de vitesse significative en effectuant votre propre tampon.


@samuel: Veuillez voir ma réponse :)


SETVBUF peut parfois être très efficace. Par exemple, cela a aidé beaucoup à la définir à 1 Mo dans le cas de la lecture de morceaux de données de 45kb d'une carte SD. Sans l'utiliser, la lecture pourrait prendre jusqu'à une demi-seconde parfois, mais il faut maintenant moins de 0,05 seconde.



0
votes

Eh bien, juste hors top, scanf ("% d% d", & n, & k) poussera une valeur en n uniquement et en silence K non définie - vous le verriez si vous avez vérifié la valeur de retour de Scanf ( ), qui vous dit combien de variables remplies. Je pense que vous voulez Scanf ("% D% D", & N, & K) avec l'espace.

Deuxièmement, n est le nombre d'itérations à exécuter, mais vous testez "n> 0" pourtant ne le décompre jamais. Ergo, n> 0 est toujours vrai et la boucle ne va pas sortir.

Comme quelqu'un d'autre l'a mentionné, l'alimentation de STDIN sur un tuyau provoque la sortie de la boucle car la fin de STDIN a un EOF, qui provoque une faille () de retourner NULL, sortant de la boucle. Vous voulez probablement ajouter un "N = N-1" ou "N--" quelque part là-bas.

Suivant, dans votre SSCANF,% N n'est pas vraiment une chose standard; Je ne suis pas sûr de ce que c'est censé faire, mais cela peut ne rien faire: Scanf () cesse généralement d'analyser le premier identifiant de format non reconnu, ce qui ne fait rien ici (puisque vous avez déjà vos données,) mais une mauvaise pratique.

Enfin, si la performance est importante, vous feriez mieux d'utiliser Fread (), etc., car ils ne sont pas vraiment élevés. Regardez Isdigit (3) et ISCNTRL (3) et réfléchissez à la manière dont vous pouvez analyser les chiffres d'un tampon de données brutes en lecture (2).


1 commentaires

Scanf ("% d% d", & n, & k) n'est pas un problème. --n est en fait là. A été supprimé par erreur cela maintenant. % n stocke le nombre de caractères lu.



3
votes

Je vais vous recommander d'essayer une mise en mémoire tampon complète avec SETVBUF CODE> et DECHING FREAD code>. Si la spécification est qu'il existe un nombre par ligne, je prendrai cela pour acquis, utilisez fgets code> pour lire dans une ligne complète et le transmettre à strtoul code> Analyser le numéro qui est censé être sur cette ligne.

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


2 commentaires

Pourriez-vous expliquer la raison de Ditch Fread et passer à SETVBUF ?


Ainsi, les points sont: 1) Il n'y a aucune raison d'essayer d'éliminer l'IO tamponnée; 2) Aucune bonne raison n'est fournie sur la raison pour laquelle on devrait lire des blocs binaires et analysez le chiffre numérique par chiffre. Au lieu de cela, comptez sur la mémoire tampon et l'analyse de la bibliothèque.



-2
votes

La raison pour laquelle cette optimisation de la permanence a un effet négligable sur le temps d'exécution est que dans * Nix et Windows Type Systèmes d'exploitation, le système d'exploitation gère tous les E / S et depuis le système de fichiers et met en œuvre 30 ans de recherche, de tromperie et de déviosité Pour le faire très efficacement.

La mémoire tampon que vous essayez de contrôler est simplement le bloc de mémoire utilisé par votre programme. Donc, toute augmentation de la vitesse sera minimale (l'effet de faire 1 gros "mov" 6 ou 7 instructions de MOV 'MOV' plus petites).

Si vous voulez vraiment accélérer cela, essayez "MMAP", ce qui vous permet d'accéder directement aux données du tampon de systèmes de fichiers.


1 commentaires

Eh bien, comme Sinan proposé, l'accélération était importante. D'environ 5 secondes à 0,8 sec. Qu'as-tu à dire maintenant: P?



2
votes

Version 1: Utilisation getchar_unlocked code> comme suggéré par R Samuel Klatchko (voir Commentaires)

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


5 commentaires

Solution NEAT au problème des nombres étant potentiellement coupé de la fin d'un tampon mais que se passe-t-il si une ligne est composée de "z \ n" ?


Votre conclusion est incorrecte. La moitié de votre vitesse vient de faire votre propre caractère -> Conversion de numéro au lieu d'utiliser Scanf. L'autre moitié est que STDIO Verrouillage peut ajouter un peu de frais généraux. Essayez ceci: 1) Activez l'appel à SETVBUF , 2) Lire l'octet de données par octet par octet avec getchar_unlocked au lieu de Fread. Vous obtiendrez une vitesse similaire.


@Samuel: D'accord. va essayer aujourd'hui.


@Sinan Ünür: C'est une solution à une spécification de problèmes (de SPOJ) qui dit clairement qu'il n'y a qu'un numéro sur chaque ligne. J'ai donc comptabilisé cela seulement. Bien sûr, ce n'est pas une solution générale. BTW j'ai mentionné que dans ma question aussi!


Ne gère pas non plus les nombres négatifs. Peut-être que vous devriez être un lien vers le problème des spécifications?



-2
votes

Voici mon octet-byte le prendre:

/*

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;

}


1 commentaires

En utilisant les mêmes données, le code ci-dessus prend 9,389 secondes contre 0,572 sec (pour la réponse que j'ai soumise) avec drapeau -O3.



1
votes

Si vous êtes après la sortie de sortie et que vous travaillez sur une plate-forme POSIX-ISH, envisagez d'utiliser la mappage de mémoire. J'ai pris la réponse de Sinan à l'aide d'E / S standard et j'ai programmé et a également créé le programme ci-dessous à l'aide de la cartographie de la mémoire. Notez que la mappage de mémoire ne fonctionnera pas si la source de données est un terminal ou un tuyau et non un fichier.

avec un million de valeurs comprises entre 0 et un milliard (et un diviseur fixe de 17), les horaires moyens pour les deux programmes était:

  • E / S Standard: 0.155S
  • Mémoire mappée: 0.086S

    grossièrement, les E / S mappées de mémoire sont deux fois plus rapides que les E / S standard.

    Dans chaque cas, le timing a été répété 6 fois, après avoir ignoré une course d'échauffement. Les lignes de commande étaient les suivantes: xxx


    xxx

1 commentaires

@Jonathan Leffler: Merci pour la réponse :). Maintenant, la solution que j'ai affichée (en utilisant Fread) le fait également dans 0,08 secondsime. Donc, il n'y a pas d'amélioration significative avec Mmeed Io. J'ai édité la question, vérifiez les modifications.