7
votes

Plus rapide que Scanf?

Je faisais une analyse massive d'entiers positifs utilisant scanf ("% d", & peint) . Comme je voulais voir si Scanf était un goulot d'étranglement, j'ai mis en place une fonction d'analyse entière naïve utilisant Fread , tout comme: xxx

mais à mon étonnement, la performance de Cette fonction est (même avec l'inlinisation) environ 50% pire. Il ne devrait-il pas y avoir de possibilité d'améliorer Scanf pour des cas spécialisés? N'est-ce pas Fread supposé être rapide (indice supplémentaire: les entiers sont ( Edit: principalement ) 1 ou 2 chiffres)?


                        
                        
                            
                                                                    c
                                                                    input
                                                                    scanf
                                                                    numeric-input
                                                            
                        
                                                    
                            
                            
                                12 commentaires
                                
                                                                            Vous ne voulez pas dire  c> = '0' && c <= '9' 

                                        
                                                                             scanf  est probablement optimisé par le compilateur.  Fread  est presque définitivement  pas  optimisé pour utiliser STDIN comme entrée.

                                        
                                                                            Au moins, vous devriez utiliser  fgetc. / code> ...

                                        
                                                                            Fread () n'est certainement pas destiné à lire un personnage à la fois. Vraisemblablement, même Fgec () fonctionne mieux.
                                        
                                                                            Si vous pensez que le goulot d'étranglement peut être une conversion de texte, une meilleure réponse est peut-être une meilleure réponse consiste à essayer de stocker vos données comme un texte binaire plutôt que du texte.
                                        
                                                                            @ASVEIKAU Aucun sens dans la modification de son format de stockage à moins qu'il  sache  c'est un goulot d'étranglement.

                                        
                                                                            @jforberg - Je suis d'accord, mais c'est une question différente. S'il vous méfie vraiment (ou simplement curieux), il peut essayer de la mettre en œuvre et comparer les résultats.
                                        
                                                                            Sur un point de vue de la norme, je suggère d'utiliser  isdigit ()  au lieu de  c> = '0' && c <= '9' , puisque les chiffres peuvent ne pas être contigu dans chaque ensemble de caractères, par exemple EBCDIC.

                                        
                                                                            @Philip: Les chiffres sont consécutifs dans EBCDIC, même si les lettres ne sont pas. Les représentations spéciales des données alphanumériques peuvent utiliser des codages non consécutifs (par exemple le code BAUDOT, utilisé dans les dispositifs de télécommunication pour les sourds, cartographique les chiffres 1234567890 aux mêmes codes que les lettres qwertyuiop, mappées non consécutives). Je ne suis pas au courant de tout code qui serait utilisé pour stocker des données dans quelque chose que l'on peut "freir" de, qui n'aurait pas de chiffres consécutifs.
                                        
                                                                             ISDigit ()  est certainement plus rapide, et pas seulement mieux car il n'assume pas la contiguïté: il est plus rapide parce que c'est un test unique plutôt que deux, sans une branche interne.

                                        
                                                                            Pour complétude,  isdigit  est implémenté comme  (non signé) C-'0 '<10  dans Musl Libc qui n'est en effet qu'un seul test. En attendant, j'ai changé mon test sur  c> = '0'  qui fonctionne à mes fins (espaces et chiffres uniquement garantis pour l'entrée ASCII) et est encore plus rapide. Mais la vitesse principale vient d'utiliser  déverrouillé_stdio (3) .

                                        
                                                                            @Philip inexact; Les normes C ont  Toutes  indiquées, dans 5.2.1 Clause 3,  "Dans les ensembles de caractères de base de la source et d'exécution, la valeur de chaque caractère après 0 dans la liste ci-dessus de la liste décimale Les chiffres doivent être supérieurs à la valeur de la précédente ". Il s'ensuit que  c> = '0' && c <= '9'  englobe tous les chiffres décimaux.

4 Réponses : 4 votes Vous pourrez vous améliorer de manière significative sur votre exemple en maintenant la mise en mémoire tampon - lisez un grand nombre de caractères dans la mémoire, puis de les analyser à partir de la version en mémoire. Si vous lisez du disque, vous pouvez obtenir une augmentation de performance par votre tampon étant un multiple de la taille du bloc. Edit: Vous pouvez laisser le noyau gérer ceci pour vous en utilisant MMAP pour mapper le fichier en mémoire. 5 commentaires J'aimerais douter de ça. Je suis à peu près sûr que libc se tamponner. Sauf si vous utilisez des appels système (lire (2) / écriture (2)), la mise en œuvre de votre propre tampon est susceptible de ralentir les choses, je pense ... Essayez-vous - heureux de me tromper :) Je me souviens de la mémoire tamponnage manuelle de vitesse de vitesse qui accélère considérablement le code qui était un getc (), mais cela aurait pu être STDIN, ce qui n'est pas bloqué tamponné. Vous pouvez également essayer de donner setvbuf () un plus grand tampon. @Joso: Juste pour des coups de pied, j'ai lu un fichier de 372 Mo avec des appels vers Freead avec 1 octet à la fois et il a fallu près de 30 secondes. La lecture de 4K à la fois a pris 1,3 seconde. Bien sûr, vous avez déjà compris cela. Néanmoins, accepter cette réponse serait probablement bonne. Ce n'était pas une réponse exactement à ma question, qui était sur battement Scanf sur un champ plus étroit ( scanf (% d, ...) n'est pas censé faire tampon, non plus!). Quoi qu'il en soit accepté parce que personne d'autre ne voudrait écrire une réponse ;-) @Joso OUI, STDIO sera tampon, mais il est plus probable que le goulot d'étranglement soit simplement les 372 millions d'appels à Fgec plutôt que tous les effets secondaires de la double tampon. -2 votes De ce que vous dites, je dérive les faits suivants: Les numéros sont compris entre 0 et 99, qui représentent 10 + 100 chaînes différentes (y compris les zéros de premier plan) li> Vous avez confiance que votre flux d'entrée adhère à une sorte de spécification et ne contiendra aucune séquence de caractères inattendue li> ul> Dans ce cas, j'utiliserais une table de recherche pour convertir des chaînes en chiffres. Compte tenu d'une chaîne S [2], l'index à votre table de recherche peut être calculé par S [1] * 10 + S [0] code>, échangeant les chiffres et en utilisant le fait que '\ 0' code> est égal 0 code> en ASCII. P> Ensuite, vous pouvez lire votre entrée de la manière suivante: p> // given our lookup method, this table may need padding entries int lookup_table[] = { /*...*/ }; // no need to call superfluous functions #define str2int(x) (lookup_table[(x)[1]*10 + (x)[0]]) while(read_token_from_stream(stdin, buf)) next_int = str2int(buf); 2 commentaires Désolé, je voulais dire "la plupart" des chiffres sont de 1 ou 2 chiffres. Quoi qu'il en soit, où est le point d'utiliser une table de recherche? Je ne peux pas voir où vous économisez des cycles. (Vous enregistrez la partie C - '0' de ma solution, mais d'autre part, vous avez plus de redirection) Jo donc: je sauve aussi le c> = '0' || C <= '9' et c == '' || c == '\ n' pièces avec au plus trois instructions chacune. Mais certes, un vrai sous-ensemble de ces opérations est nécessaire dans ce que j'ai abrégé avec read_token_from_stream () . 1 votes Voici quelque chose que j'utilise. #define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0) char _; 3 commentaires Cela fonctionne bien! Bien que, je suggère d'utiliser getcx () ou getchar_unlocked () au lieu de GetChartar (). Qu'est-ce que char _; faire? @ Light2Yellow the Char _; Définit une variable dont le nom est le caractère de soulignement, _ , utilisé dans la macro elle-même telle que (_ = getchar () ) . L'intention est d'avoir une variable globale qui est définie dans laquelle la macro est définie que la macro utilise ensuite. J'utiliserais probablement Static Char _; à la place afin de limiter la portée à l'unité de fichier ou de compilation. Probablement pas une bonne idée d'applications multi-filetées. Devrait vraiment être une fonction, pas une macro. Lit l'entrée pour le premier chiffre puis convertit une série de chiffres en une valeur entière. arrête de lire au premier non chiffre. 8 votes La surcharge que j'avais rencontrée n'était pas l'analyse elle-même mais les nombreux appels vers Fread (identique avec fget et amis). Pour chaque appel, le LIBC doit verrouiller le flux d'entrée pour vous assurer que deux threads ne sont pas sur les pieds de l'autre. Le verrouillage est une opération très coûteuse. Ce que nous recherchons est une fonction qui nous donne une entrée tamponnée américaine (la mise en mémoire tampon de réinstallation est tout simplement un effort) mais évite l'énorme surcharge de verrouillage de Fgec . < / p> Si nous pouvons garantir qu'il n'y a qu'un seul thread utilisant le flux d'entrée, nous pouvons utiliser les fonctions à partir de déverrouillé_stdio (3) , telle que getchar_unlocked (3) < / code>. Voici un exemple: xxx La version ci-dessus ne vérifie pas les erreurs. Mais il est garanti de se terminer. Si la manipulation des erreurs est nécessaire, il peut être suffisant pour vérifier Feof (stdin) et ferror (stdin) à la fin, ou laissez l'appelant le faire. < P> Mon objectif initial soumettait des solutions aux problèmes de programmation chez SPOJ, où l'entrée n'est que des espaces et des chiffres. Donc, il y a toujours de la place pour l'amélioration, à savoir le isdigit check. xxx C'est très, très difficile à battre cette routine d'analyse, à la fois de la performance sage et en termes de commodité et de maintenabilité. 0 commentaires

Articles qui pourrait vous intéresser : Que puis-je utiliser pour la conversion d'entrée au lieu de scanf? Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde? Comment vérifier si un pointeur void (void *) est l'un des deux types de données? L'écran LCD affiche des caractères aléatoires (MPLAB)