Ich versuche, effizient vom stdin zu lesen, indem ich setvbuf im '_IOFBF ~ Modus benutze. Ich bin neu im Puffern. Ich suche working Beispiele.
Die Eingabe beginnt mit zwei Ganzzahlen ( n , k ). Die nächsten n Zeilen der Eingabe enthalten 1 Integer. Ziel ist es, zu drucken, wie viele ganze Zahlen durch k teilbar sind.
Das Problem ist, wenn die Zahl an der Grenze ist, der Puffer buf wird 23 von 2354\n lesen, wenn er entweder 2354 gelesen haben sollte (was nicht möglich ist) oder überhaupt nichts.
Wie kann ich dieses Problem lösen?
Bearbeiten
Gelöst jetzt (mit Analyse ) .
Bearbeiten Sie die vollständige Problemspezifikation
Version 1: Verwendung von getchar_unlocked wie von Samuel Klatchko vorgeschlagen (siehe Kommentare)
Version 2: Verwenden von fread , um einen Block zu lesen und eine Nummer zu analysieren.
Ergebnisse: (10 Millionen Zahlen, die auf Teilbarkeit mit 11 getestet wurden)
Run 1: (Version 1 ohne setvbuf) 0.782 Sekunden
Run 2: (Version 1 mit setvbuf) 0.684 Sekunden
Run 3: (Version 2) 0.534
P.S. - Jeder Lauf, der mit GCC kompiliert wurde, mit dem Flag -O1
Ich empfehle, die vollständige Pufferung mit setvbuf und mit fread zu versuchen. Wenn die Spezifikation ist, dass es eine Zahl pro Zeile gibt, nehme ich das als selbstverständlich, benutze fgets , um eine volle Zeile einzulesen und übergebe es an strtoul analysiere die Zahl, die in dieser Zeile sein soll.
Ich habe ein Perl-Skript verwendet, um 1.000.000 zufällige Ganzzahlen zwischen 0 und 1.000.000 zu erzeugen, und nach dem Kompilieren dieses Programms mit gcc version 3.4.5 (mingw-vista special r3) auf meinem Windows XP-Laptop überprüft, ob sie durch 5 teilbar sind. Die ganze Sache dauerte weniger als 0,8 Sekunden.
Als ich die Pufferung mit setvbuf(stdin, (char*)NULL, _IONBF, 0); deaktiviert habe, ist die Zeit auf ungefähr 15 Sekunden gestiegen.
Eine Sache, die ich verwirre, ist, warum Sie beide die vollständige Pufferung innerhalb des Stream-Objekts über den Aufruf von setvbuf aktivieren und Ihre eigene Pufferung durchführen, indem Sie einen vollständigen Puffer in buf lesen.
Ich verstehe die Notwendigkeit, Pufferung zu tun, aber das ist ein bisschen übertrieben.
Ich werde dir empfehlen, bei setvbuf zu bleiben und deine eigene Pufferung zu entfernen. Der Grund dafür ist, dass die Implementierung einer eigenen Pufferung schwierig sein kann. Das Problem tritt auf, wenn ein Token (in Ihrem Fall eine Zahl) die Puffergrenze überspannt. Angenommen, Ihr Puffer ist 8 Byte groß (insgesamt 9 Byte für abschließendes NULL) und Ihr Eingabestream sieht wie
Beim ersten Füllen des Puffers erhalten Sie:
%Vor%Beim zweiten Füllen des Puffers erhalten Sie:
%Vor%Bei der richtigen Pufferung müssen Sie diesen Fall behandeln, damit Sie den Puffer als die beiden Zahlen {12345, 12345} und nicht als drei Zahlen {12345, 12, 234} behandeln.
Da stdio das bereits für Sie erledigt, benutzen Sie das einfach. Rufen Sie weiterhin setvbuf auf, entfernen Sie fread und verwenden Sie scanf , um einzelne Zahlen aus dem Eingabestream zu lesen.
Das Problem, wenn Sie keine Umleitung verwenden, ist, dass Sie EOF nicht verursachen.
Da dies Posix zu sein scheint (basierend auf der Tatsache, dass Sie gcc verwenden), geben Sie einfach ctrl-D ein (d. h. drücken Sie gleichzeitig die Steuertaste, d / drücken Sie d), wodurch EOF erreicht wird.
Wenn Sie Windows verwenden, verwenden Sie stattdessen ctrl-Z .
Wenn Sie nach einer ausdauernden Geschwindigkeit suchen und auf einer POSIX-ish-Plattform arbeiten, sollten Sie die Speicherzuordnung in Erwägung ziehen. Ich nahm Sinans Antwort mit Standard-I / O und Timed es, und erstellte auch das Programm unten mit Memory Mapping. Beachten Sie, dass die Speicherzuordnung nicht funktioniert, wenn die Datenquelle ein Terminal oder eine Pipe und keine Datei ist.
Bei einer Million Werten zwischen 0 und einer Milliarde (und einem festen Teiler von 17) war das durchschnittliche Timing für die beiden Programme:
Grob gesagt ist die Speicherbelegung von E / A doppelt so schnell wie die von Standard-E / A.
In jedem Fall wurde das Timing 6 Mal wiederholt, nachdem ein Aufwärmlauf ignoriert wurde. Die Befehlszeilen waren:
%Vor% %Vor% Sie können den Wert von n verwenden, um das Lesen der Eingabe zu beenden, nachdem Sie n Ganzzahlen gesehen haben.
Ändern Sie den Zustand der äußeren while Schleife zu:
und ändere den Körper des inneren zu:
%Vor% Das Problem, das Sie weiterhin haben, besteht darin, dass buf in der inneren while -Schleife nie korrigiert wird, sscanf die gleiche Zahl immer wieder liest.
Wenn Sie strtol() intad von sscanf() verwenden, können Sie den Ausgabeparameter endptr verwenden, um sich beim Lesen von Zahlen durch den Puffer zu bewegen.
Nun, ganz oben, scanf ("% d% d", & amp; n, & amp; k) wird nur einen Wert in n schieben und stillschweigend k unset lassen - Sie würden dies sehen, wenn Sie die Rückkehr überprüfen Wert von scanf (), der Ihnen sagt, wie viele Variablen es gefüllt hat. Ich denke, Sie wollen scanf ("% d% d", & amp; n, & amp; k) mit dem Leerzeichen.
Zweitens ist n die Anzahl der auszuführenden Iterationen, aber Sie testen auf "n & gt; 0", dekrementieren sie jedoch nie. Ergo, n & gt; 0 ist immer wahr und die Schleife wird nicht verlassen.
Wie jemand anderes bereits erwähnt, führt die Eingabe von stdin über eine Pipe dazu, dass die Schleife beendet wird, da das Ende von stdin einen EOF hat, der bewirkt, dass fread () NULL zurückgibt und die Schleife verlässt. Wahrscheinlich möchtest du irgendwo "n = n-1" oder "n--" hinzufügen.
Als nächstes ist% n in Ihrem sscanf nicht wirklich Standard; Ich bin mir nicht sicher, was es zu tun ist, aber es kann nichts tun: scanf () hört im Allgemeinen auf, mit dem ersten unbekannten Format-Bezeichner zu analysieren, der hier nichts tut (da Sie bereits Ihre Daten erhalten haben), aber es ist eine schlechte Übung.
Wenn die Leistung wichtig ist, sollten Sie besser nicht fread () usw. verwenden, da sie nicht wirklich leistungsstark sind. Sehen Sie sich isdigit (3) und iscntrl (3) an und überlegen Sie, wie Sie die Zahlen aus einem Rohdatenpuffer lesen können, der mit read (2) gelesen wurde.
Die äußerste Schleife while() wird nur beendet, wenn das Lesen von stdin EOF zurückgibt. Dies kann nur passieren, wenn das tatsächliche Dateiende für eine Eingabedatei erreicht wird oder wenn der Prozess, der in eine Eingabedatei schreibt, beendet wird. Daher wird die printf() -Anweisung niemals ausgeführt. Ich glaube nicht, dass dies etwas mit dem Aufruf von setvbuf() zu tun hat.
Der Grund, warum all diese Permature-Optimierung einen vernachlässigbaren Effekt auf die Laufzeit hat, liegt darin, dass das Betriebssystem in * nix- und Windows-Betriebssystemen alle I / O-Vorgänge zum und vom Dateisystem abwickelt und 30 Jahre Forschung, Trickserei und Verschlagenheit umsetzt um das sehr effizient zu machen.
Die Pufferung, die Sie zu steuern versuchen, ist nur der Speicherblock, den Ihr Programm verwendet. Jede Erhöhung der Geschwindigkeit wird minimal sein (der Effekt, 1 große 'mov' zu machen, verse 6 oder 7 kleinere 'mov' Anweisungen).
Wenn Sie dies wirklich beschleunigen möchten, versuchen Sie "mmap", mit dem Sie direkt auf die Daten im Dateisystempuffer zugreifen können.