Warum ist das Lesen von Zeilen aus stdin in C ++ viel langsamer als in Python?

1840

Ich wollte das Lesen von Zeilen der Zeichenfolgeneingabe von stdin mit Python und C ++ vergleichen und war schockiert, als mein C ++ - Code eine Größenordnung langsamer als der entsprechende Python-Code ausgeführt wurde. Da mein C ++ rostig ist und ich noch kein Pythonista-Experte bin, sagen Sie mir bitte, ob ich etwas falsch mache oder ob ich etwas falsch verstehe.


(TLDR-Antwort: Fügen Sie die Anweisung hinzu: cin.sync_with_stdio(false)oder verwenden Sie fgetsstattdessen einfach .

TLDR-Ergebnisse: Scrollen Sie bis zum Ende meiner Frage und sehen Sie sich die Tabelle an.)


C ++ - Code:

#include <iostream>
#include <time.h>

using namespace std;

int main() {
    string input_line;
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    while (cin) {
        getline(cin, input_line);
        if (!cin.eof())
            line_count++;
    };

    sec = (int) time(NULL) - start;
    cerr << "Read " << line_count << " lines in " << sec << " seconds.";
    if (sec > 0) {
        lps = line_count / sec;
        cerr << " LPS: " << lps << endl;
    } else
        cerr << endl;
    return 0;
}

// Compiled with:
// g++ -O3 -o readline_test_cpp foo.cpp

Python-Äquivalent:

#!/usr/bin/env python
import time
import sys

count = 0
start = time.time()

for line in  sys.stdin:
    count += 1

delta_sec = int(time.time() - start_time)
if delta_sec >= 0:
    lines_per_sec = int(round(count/delta_sec))
    print("Read {0} lines in {1} seconds. LPS: {2}".format(count, delta_sec,
       lines_per_sec))

Hier sind meine Ergebnisse:

$ cat test_lines | ./readline_test_cpp
Read 5570000 lines in 9 seconds. LPS: 618889

$cat test_lines | ./readline_test.py
Read 5570000 lines in 1 seconds. LPS: 5570000

Ich sollte beachten, dass ich dies sowohl unter Mac OS X 10.6.8 (Snow Leopard) als auch unter Linux 2.6.32 (Red Hat Linux 6.2) versucht habe. Ersteres ist ein MacBook Pro, und letzteres ist ein sehr leistungsfähiger Server, nicht dass dies zu relevant wäre.

$ for i in {1..5}; do echo "Test run $i at `date`"; echo -n "CPP:"; cat test_lines | ./readline_test_cpp ; echo -n "Python:"; cat test_lines | ./readline_test.py ; done
Test run 1 at Mon Feb 20 21:29:28 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 2 at Mon Feb 20 21:29:39 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 3 at Mon Feb 20 21:29:50 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 4 at Mon Feb 20 21:30:01 EST 2012
CPP:   Read 5570001 lines in 9 seconds. LPS: 618889
Python:Read 5570000 lines in 1 seconds. LPS: 5570000
Test run 5 at Mon Feb 20 21:30:11 EST 2012
CPP:   Read 5570001 lines in 10 seconds. LPS: 557000
Python:Read 5570000 lines in  1 seconds. LPS: 5570000

Winziger Benchmark-Nachtrag und Zusammenfassung

Der Vollständigkeit halber dachte ich, ich würde die Lesegeschwindigkeit für dieselbe Datei auf derselben Box mit dem ursprünglichen (synchronisierten) C ++ - Code aktualisieren. Dies gilt wiederum für eine 100-MB-Zeilendatei auf einer schnellen Festplatte. Hier ist der Vergleich mit mehreren Lösungen / Ansätzen:

Implementation      Lines per second
python (default)           3,571,428
cin (default/naive)          819,672
cin (no sync)             12,500,000
fgets                     14,285,714
wc (not fair comparison)  54,644,808
JJC
quelle
14
Haben Sie Ihre Tests mehrmals durchgeführt? Möglicherweise liegt ein Problem mit dem Festplatten-Cache vor.
Vaughn Cato
9
@JJC: Ich sehe zwei Möglichkeiten (vorausgesetzt, Sie haben das von David vorgeschlagene Caching-Problem behoben): 1) Die <iostream>Leistung ist schlecht. Nicht das erste Mal, dass es passiert. 2) Python ist klug genug, um die Daten nicht in die for-Schleife zu kopieren, weil Sie sie nicht verwenden. Sie könnten erneut versuchen, zu verwenden scanfund a char[]. Alternativ können Sie versuchen, die Schleife neu zu schreiben, damit etwas mit der Zeichenfolge getan wird (z. B. den 5. Buchstaben behalten und in einem Ergebnis verketten).
JN
15
Das Problem ist die Synchronisation mit stdio - siehe meine Antwort.
Vaughn Cato
19
Da scheint niemand erwähnt zu haben, warum man mit C ++ eine Extrazeile bekommt: Nicht testen gegen cin.eof()!! Setzen Sie den getlineAufruf in die 'if'-Anweisung.
Xeo
21
wc -list schnell, da der Stream mehr als eine Zeile gleichzeitig liest (dies kann eine fread(stdin)/memchr('\n')Kombination sein). Python-Ergebnisse sind in der gleichen Größenordnung, zBwc-l.py
jfs

Antworten:

1644

Standardmäßig wird cines mit stdio synchronisiert, wodurch jegliche Eingabepufferung vermieden wird. Wenn Sie dies oben in Ihrem Hauptfenster hinzufügen, sollten Sie eine viel bessere Leistung sehen:

std::ios_base::sync_with_stdio(false);

Wenn ein Eingabestream gepuffert wird, wird der Stream normalerweise in größeren Blöcken gelesen, anstatt jeweils ein Zeichen zu lesen. Dies reduziert die Anzahl der Systemaufrufe, die typischerweise relativ teuer sind. Da die FILE*basierten stdiound iostreamshäufig getrennten Implementierungen und daher getrennte Puffer haben, könnte dies zu einem Problem führen, wenn beide zusammen verwendet würden. Zum Beispiel:

int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);

Wenn mehr Eingaben gelesen würden, cinals tatsächlich benötigt würden, wäre der zweite ganzzahlige Wert für die scanfFunktion, die über einen eigenen unabhängigen Puffer verfügt, nicht verfügbar . Dies würde zu unerwarteten Ergebnissen führen.

Um dies zu vermeiden, werden Streams standardmäßig mit synchronisiert stdio. Eine übliche Möglichkeit, dies zu erreichen, besteht darin cin, jedes Zeichen nach Bedarf mithilfe von stdioFunktionen einzeln zu lesen . Dies führt leider zu einem hohen Overhead. Bei kleinen Eingaben ist dies kein großes Problem, aber wenn Sie Millionen von Zeilen lesen, ist der Leistungsverlust erheblich.

Glücklicherweise haben die Bibliotheksdesigner entschieden, dass Sie diese Funktion auch deaktivieren können sollten, um eine verbesserte Leistung zu erzielen, wenn Sie wissen, was Sie tun. Daher haben sie die sync_with_stdioMethode bereitgestellt .

Vaughn Cato
quelle
142
Dies sollte oben sein. Es ist mit ziemlicher Sicherheit richtig. Die Antwort kann nicht darin bestehen, den Lesevorgang durch einen fscanfAufruf zu ersetzen , da dies ganz einfach nicht so viel Arbeit leistet wie Python. Python muss Speicher für die Zeichenfolge zuweisen, möglicherweise mehrmals, da die vorhandene Zuordnung als unzureichend angesehen wird - genau wie beim C ++ - Ansatz mit std::string. Diese Aufgabe ist mit ziemlicher Sicherheit an E / A gebunden, und es geht viel zu viel FUD um die Kosten für das Erstellen von std::stringObjekten in C ++ oder die Verwendung <iostream>an und für sich.
Karl Knechtel
51
Ja, das Hinzufügen dieser Zeile direkt über meiner ursprünglichen while-Schleife beschleunigte den Code, um sogar Python zu übertreffen. Ich bin dabei, die Ergebnisse als endgültige Bearbeitung zu veröffentlichen. Danke noch einmal!
JJC
6
Ja, dies gilt auch für Cout, Ferr und Clog.
Vaughn Cato
2
Gehen Sie folgendermaßen vor, um cout, cin, cerr und clog schneller zu machen. Std :: ios_base :: sync_with_stdio (false);
01100110
56
Beachten Sie, dass dies sync_with_stdio()eine statische Elementfunktion ist und ein Aufruf dieser Funktion für ein beliebiges Stream-Objekt (z. B. cin) die Synchronisierung für alle Standard-Iostream-Objekte ein- oder ausschaltet .
John Zwinck
171

Nur aus Neugier habe ich mir angesehen, was unter der Haube passiert, und ich habe Dtruss / Strace verwendet bei jedem Test verwendet.

C ++

./a.out < in
Saw 6512403 lines in 8 seconds.  Crunch speed: 814050

Systemaufrufe sudo dtruss -c ./a.out < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            6
pread                                           8
mprotect                                       17
mmap                                           22
stat64                                         30
read_nocancel                               25958

Python

./a.py < in
Read 6512402 lines in 1 seconds. LPS: 6512402

Systemaufrufe sudo dtruss -c ./a.py < in

CALL                                        COUNT
__mac_syscall                                   1
<snip>
open                                            5
pread                                           8
mprotect                                       17
mmap                                           21
stat64                                         29
2mia
quelle
159

Ich bin ein paar Jahre hinterher, aber:

In 'Edit 4/5/6' des ursprünglichen Beitrags verwenden Sie die Konstruktion:

$ /usr/bin/time cat big_file | program_to_benchmark

Dies ist in vielerlei Hinsicht falsch:

  1. Sie planen tatsächlich die Ausführung cat, nicht Ihren Benchmark. Die ‚Benutzer‘ und ‚sys‘ CPU - Auslastung angezeigt durch timediejenigen sind cat, nicht Ihre gebenchmarkt Programm. Schlimmer noch, die "Echtzeit" ist auch nicht unbedingt genau. Abhängig von der Implementierung von catund von Pipelines in Ihrem lokalen Betriebssystem ist es möglich, dass catein endgültiger Riesenpuffer geschrieben und beendet wird, lange bevor der Lesevorgang seine Arbeit beendet.

  2. Die Verwendung von catist unnötig und in der Tat kontraproduktiv; Sie fügen bewegliche Teile hinzu. Wenn Sie sich auf einem ausreichend alten System befinden (dh mit einer einzelnen CPU und - bei bestimmten Computergenerationen - E / A schneller als die CPU), kann die bloße Tatsache, dass sie catausgeführt wird, die Ergebnisse erheblich beeinflussen. Sie unterliegen auch jeglicher Eingabe- und Ausgabepufferung und anderer Verarbeitung cat. (Dies würde Ihnen wahrscheinlich die Auszeichnung "Nutzlose Verwendung von Katzen" einbringen, wenn ich Randal Schwartz wäre.

Eine bessere Konstruktion wäre:

$ /usr/bin/time program_to_benchmark < big_file

In dieser Anweisung ist es die Shell, die big_file öffnet und timeals bereits geöffneter Dateideskriptor an Ihr Programm übergibt (also tatsächlich an das dann Ihr Programm als Unterprozess ausgeführt wird). 100% des Dateilesens liegt ausschließlich in der Verantwortung des Programms, das Sie bewerten möchten. Auf diese Weise erhalten Sie einen echten Überblick über die Leistung ohne störende Komplikationen.

Ich werde zwei mögliche, aber tatsächlich falsche "Korrekturen" erwähnen, die ebenfalls in Betracht gezogen werden könnten (aber ich "nummeriere" sie unterschiedlich, da dies keine Dinge sind, die im ursprünglichen Beitrag falsch waren):

A. Sie können dies beheben, indem Sie nur Ihr Programm zeitlich festlegen:

$ cat big_file | /usr/bin/time program_to_benchmark

B. oder durch Timing der gesamten Pipeline:

$ /usr/bin/time sh -c 'cat big_file | program_to_benchmark'

Diese sind aus den gleichen Gründen wie # 2 falsch: Sie werden immer noch catunnötig verwendet. Ich erwähne sie aus mehreren Gründen:

  • Sie sind „natürlicher“ für Personen, die mit den E / A-Umleitungsfunktionen der POSIX-Shell nicht ganz vertraut sind

  • kann es Fälle geben, wo cat ist erforderlich (zB: die Datei erfordert eine Art Privileg , den Zugang zu lesen, und Sie wollen nicht dieses Privileg , um das Programm zu gewähren , werden gebenchmarkt: sudo cat /dev/sda | /usr/bin/time my_compression_test --no-output)

  • In der Praxis hat das Hinzufügen moderner Maschinen auf modernen Maschinen catwahrscheinlich keine wirkliche Konsequenz.

Aber ich sage das letzte mit einigem Zögern. Wenn wir das letzte Ergebnis in 'Edit 5' untersuchen -

$ /usr/bin/time cat temp_big_file | wc -l
0.01user 1.34system 0:01.83elapsed 74%CPU ...

- dies behauptet, dass cat74% der CPU während des Tests verbraucht wurden; und tatsächlich ist 1,34 / 1,83 ungefähr 74%. Vielleicht eine Serie von:

$ /usr/bin/time wc -l < temp_big_file

hätte nur die restlichen 0,49 Sekunden gedauert! Wahrscheinlich nicht: catHier mussten die read()Systemaufrufe (oder gleichwertige) bezahlt werden, die die Datei von 'disk' (eigentlich Puffer-Cache) übertragen haben, sowie die Pipe-Schreibvorgänge, um sie zu liefern wc. Der richtige Test hätte diese noch durchführen müssenread() Anrufe ; nur die Write-to-Pipe- und Read-from-Pipe-Aufrufe wären gespeichert worden, und diese sollten ziemlich billig sein.

Trotzdem gehe ich davon aus, dass Sie den Unterschied zwischen messen können cat file | wc -l undwc -l < file und einen spürbaren Unterschied (zweistelliger Prozentsatz) feststellen können. Jeder der langsameren Tests hat in absoluter Zeit eine ähnliche Strafe gezahlt; Dies würde jedoch einen kleineren Bruchteil seiner größeren Gesamtzeit ausmachen.

Tatsächlich habe ich einige schnelle Tests mit einer 1,5-Gigabyte-Mülldatei auf einem Linux 3.13-System (Ubuntu 14.04) durchgeführt, um diese Ergebnisse zu erhalten (dies sind tatsächlich die besten 3-Ergebnisse; natürlich nach dem Priming des Caches):

$ time wc -l < /tmp/junk
real 0.280s user 0.156s sys 0.124s (total cpu 0.280s)
$ time cat /tmp/junk | wc -l
real 0.407s user 0.157s sys 0.618s (total cpu 0.775s)
$ time sh -c 'cat /tmp/junk | wc -l'
real 0.411s user 0.118s sys 0.660s (total cpu 0.778s)

Beachten Sie, dass die beiden Pipeline-Ergebnisse angeblich mehr CPU-Zeit (Benutzer + System) als die tatsächliche Wanduhrzeit in Anspruch genommen haben. Dies liegt daran, dass ich den in die Shell (bash) integrierten Befehl 'time' verwende, der die Pipeline kennt. und ich bin auf einem Multi-Core-Computer, auf dem separate Prozesse in einer Pipeline separate Kerne verwenden können, wodurch die CPU-Zeit schneller als in Echtzeit angesammelt wird. Verwenden von/usr/bin/time sehe ich eine geringere CPU-Zeit als in Echtzeit - dies zeigt, dass nur das einzelne Pipeline-Element, das an ihn übergeben wurde, in der Befehlszeile zeitlich festgelegt werden kann. Außerdem gibt die Ausgabe der Shell Millisekunden an, während /usr/bin/timenur Hundertstelsekunden ausgegeben werden .

Also auf dem Wirkungsgrad von wc -l , dercat macht einen großen Unterschied: 409/283 = 1,453 oder 45,3% mehr in Echtzeit, und 775/280 = 2,768, oder ein sattes 177% mehr CPU verwendet! Auf meiner zufälligen Testbox war es zu der Zeit da.

Ich sollte hinzufügen, dass es mindestens einen weiteren signifikanten Unterschied zwischen diesen Teststilen gibt, und ich kann nicht sagen, ob es sich um einen Vorteil oder einen Fehler handelt. das musst du selbst entscheiden:

Wenn Sie ausführen cat big_file | /usr/bin/time my_program, empfängt Ihr Programm Eingaben von einer Pipe, genau in dem Tempo, das von gesendet wirdcat , und in Blöcken, die nicht größer als von geschrieben sindcat .

Wenn Sie ausführen /usr/bin/time my_program < big_file, erhält Ihr Programm einen offenen Dateideskriptor für die eigentliche Datei. Ihr Programm - oder in vielen Fällen die E / A-Bibliotheken der Sprache, in der es geschrieben wurde - kann unterschiedliche Aktionen ausführen, wenn ein Dateideskriptor angezeigt wird, der auf eine reguläre Datei verweist. Es kann verwendet werden mmap(2), um die Eingabedatei ihrem Adressraum zuzuordnen, anstatt explizite read(2)Systemaufrufe zu verwenden. Diese Unterschiede können sich weitaus stärker auf Ihre Benchmark-Ergebnisse auswirken als die geringen Kosten für die Ausführung der catBinärdatei.

Natürlich ist es ein interessantes Benchmark-Ergebnis, wenn dasselbe Programm zwischen den beiden Fällen signifikant unterschiedlich abschneidet. Es zeigt , dass in der Tat, das Programm oder dessen I / O - Bibliotheken sind etwas Interessantes zu tun, wie mit mmap(). In der Praxis kann es daher sinnvoll sein, die Benchmarks in beide Richtungen auszuführen. Vielleicht wird das catErgebnis um einen kleinen Faktor abgezinst , um die Kosten für den Betrieb catselbst zu "verzeihen" .

Bela Lubkin
quelle
26
Wow, das war ziemlich aufschlussreich! Obwohl mir bewusst war, dass cat nicht erforderlich ist, um Eingaben in stdin von Programmen einzugeben, und dass die <Shell-Umleitung bevorzugt wird, habe ich mich aufgrund des Datenflusses von links nach rechts, den die erstere Methode visuell beibehält, im Allgemeinen an cat gehalten wenn ich über Pipelines nachdenke. Leistungsunterschiede in solchen Fällen habe ich als vernachlässigbar befunden. Aber ich weiß es zu schätzen, dass Sie uns erzogen haben, Bela.
JJC
11
Die Umleitung wird frühzeitig aus der Shell-Befehlszeile heraus analysiert, sodass Sie eine dieser Aktionen ausführen können, wenn der Fluss von links nach rechts angenehmer aussieht: $ < big_file time my_program $ time < big_file my_program Dies sollte in jeder POSIX-Shell (dh nicht in `csh) funktionieren `und ich bin mir nicht sicher über exotica wie` rc` :)
Bela Lubkin
6
Abgesehen von dem möglicherweise uninteressanten inkrementellen Leistungsunterschied aufgrund der gleichzeitigen Ausführung der `cat`-Binärdatei geben Sie die Möglichkeit auf, dass das zu testende Programm die Eingabedatei mmap () kann. Dies könnte einen tiefgreifenden Unterschied in den Ergebnissen bewirken. Dies gilt auch dann, wenn Sie die Benchmarks selbst in den verschiedenen Sprachen geschrieben haben und nur die Redewendung "Eingabezeilen aus einer Datei" verwendet haben. Dies hängt von der detaillierten Funktionsweise der verschiedenen E / A-Bibliotheken ab.
Bela Lubkin
2
Randnotiz: Bashs integriertes System timemisst die gesamte Pipeline anstelle des ersten Programms. time seq 2 | while read; do sleep 1; donedruckt 2 Sek., /usr/bin/time seq 2 | while read; do sleep 1; donedruckt 0 Sek.
Folkol
1
@folkol - ja, << Beachten Sie, dass die beiden Pipeline-Ergebnisse mehr CPU [als] Echtzeit [mit] (Bash) 's integriertem' Zeit'-Befehl [zeigen]; ... / usr / bin / time ... kann nur das einzelne Pipeline-Element zeitlich festlegen, das in der Befehlszeile an es übergeben wurde. >> '
Bela Lubkin
90

Ich habe das ursprüngliche Ergebnis auf meinem Computer mit g ++ auf einem Mac reproduziert.

Durch Hinzufügen der folgenden Anweisungen zur C ++ - Version unmittelbar vor der whileSchleife wird sie mit der Python- Version in Einklang gebracht :

std::ios_base::sync_with_stdio(false);
char buffer[1048576];
std::cin.rdbuf()->pubsetbuf(buffer, sizeof(buffer));

sync_with_stdio verbesserte die Geschwindigkeit auf 2 Sekunden und durch Einstellen eines größeren Puffers auf 1 Sekunde.

Karunski
quelle
5
Möglicherweise möchten Sie verschiedene Puffergrößen ausprobieren, um weitere nützliche Informationen zu erhalten. Ich vermute, Sie werden schnell sinkende Renditen sehen.
Karl Knechtel
8
Ich war zu voreilig in meiner Antwort; Das Einstellen der Puffergröße auf einen anderen Wert als den Standardwert ergab keinen nennenswerten Unterschied.
Karunski
109
Ich würde auch vermeiden, einen 1-MB-Puffer auf dem Stapel einzurichten. Es kann zu einem Stapelüberlauf führen (obwohl ich denke, es ist ein guter Ort, um darüber zu debattieren!)
Matthieu M.
11
Matthieu, Mac verwendet standardmäßig einen 8-MB-Prozessstapel. Linux verwendet 4 MB pro Thread, Standard IIRC. 1 MB ist für ein Programm, das Eingaben mit relativ geringer Stapeltiefe transformiert, kein so großes Problem. Noch wichtiger ist jedoch, dass std :: cin den Stapel in den Papierkorb legt, wenn der Puffer den Gültigkeitsbereich verlässt.
SEK
22
Die Standardstapelgröße von @SEK Windows beträgt 1 MB.
Étienne
39

getlineStream-Operatoren scanfkönnen nützlich sein, wenn Sie sich nicht für die Ladezeit von Dateien interessieren oder wenn Sie kleine Textdateien laden. Wenn Sie sich jedoch für die Leistung interessieren, sollten Sie die gesamte Datei einfach in den Speicher puffern (vorausgesetzt, sie passt).

Hier ist ein Beispiel:

//open file in binary mode
std::fstream file( filename, std::ios::in|::std::ios::binary );
if( !file ) return NULL;

//read the size...
file.seekg(0, std::ios::end);
size_t length = (size_t)file.tellg();
file.seekg(0, std::ios::beg);

//read into memory buffer, then close it.
char *filebuf = new char[length+1];
file.read(filebuf, length);
filebuf[length] = '\0'; //make it null-terminated
file.close();

Wenn Sie möchten, können Sie einen Stream um diesen Puffer wickeln, um einen bequemeren Zugriff wie folgt zu erhalten:

std::istrstream header(&filebuf[0], length);

Wenn Sie die Kontrolle über die Datei haben, sollten Sie auch ein flaches Binärdatenformat anstelle von Text verwenden. Lesen und Schreiben ist zuverlässiger, da Sie sich nicht mit allen Mehrdeutigkeiten von Leerzeichen auseinandersetzen müssen. Es ist auch kleiner und viel schneller zu analysieren.

Stu
quelle
20

Der folgende Code war für mich schneller als der andere Code, der bisher hier veröffentlicht wurde: (Visual Studio 2013, 64-Bit-Datei mit 500 MB und einheitlicher Zeilenlänge in [0, 1000)).

const int buffer_size = 500 * 1024;  // Too large/small buffer is not good.
std::vector<char> buffer(buffer_size);
int size;
while ((size = fread(buffer.data(), sizeof(char), buffer_size, stdin)) > 0) {
    line_count += count_if(buffer.begin(), buffer.begin() + size, [](char ch) { return ch == '\n'; });
}

Es übertrifft alle meine Python-Versuche um mehr als den Faktor 2.

Petter
quelle
Mit einem winzigen benutzerdefinierten, aber völlig unkomplizierten C-Programm, das iterativ entweder ungepufferte readSystemaufrufe in einen statischen Puffer der Länge BUFSIZEoder über die entsprechenden entsprechenden mmapSystemaufrufe iterativ umwandelt und dann durch diesen Puffer peitscht und die Zeilenumbrüche à la zählt, können Sie noch schneller werden for (char *cp = buf; *cp; cp++) count += *cp == "\n". Sie müssen sich jedoch BUFSIZEauf Ihr System einstellen, was stdio bereits für Sie getan hat. Aber das forSchleife sollte awesomely kompiliert nach unten zu schreien schnellen Assemblersprache Anweisungen für die Hardware Ihrer Box.
Tchrist
3
count_if und ein Lambda kompilieren sich ebenfalls zu "unglaublich schreiend schnellem Assembler".
Petter
17

Der Grund, warum die Zeilenanzahl für die C ++ - Version um eins höher ist als die Anzahl für die Python-Version, ist übrigens, dass das eof-Flag nur gesetzt wird, wenn versucht wird, über eof hinaus zu lesen. Die richtige Schleife wäre also:

while (cin) {
    getline(cin, input_line);

    if (!cin.eof())
        line_count++;
};
Gregg
quelle
70
Die wirklich richtige Schleife wäre: while (getline(cin, input_line)) line_count++;
Jonathan Wakely
2
@ JonathanWakely Ich weiß, dass ich ziemlich spät bin, aber verwenden ++line_count;und nicht line_count++;.
Val sagt Reinstate Monica
7
@val Wenn das einen Unterschied macht, hat Ihr Compiler einen Fehler. Die Variable ist a long, und der Compiler kann durchaus erkennen, dass das Ergebnis des Inkrements nicht verwendet wird. Wenn kein identischer Code für Nach- und Vorinkrementierung generiert wird, ist er fehlerhaft.
Jonathan Wakely
2
In der Tat kann jeder anständige Compiler einen Missbrauch nach dem Inkrement erkennen und ihn stattdessen durch ein Pre-Inkrement ersetzen, Compiler müssen dies jedoch nicht . Also nein, es ist nicht kaputt, auch wenn der Compiler die Ersetzung nicht durchführt. Außerdem würde das Schreiben ++line_count;statt line_count++;nicht schaden :)
Fareanor
1
@valsaysReinstateMonica Warum sollte in diesem Beispiel eines davon bevorzugt werden? Das Ergebnis wird hier so oder so nicht verwendet, also würde es nach dem gelesen while, oder? Wäre es wichtig, wenn es einen Fehler gäbe und Sie sicherstellen möchten, dass der Fehler line_countkorrekt ist? Ich rate nur, aber ich verstehe nicht, warum es wichtig sein würde.
TankorSmash
14

In Ihrem zweiten Beispiel (mit scanf ()) liegt dies möglicherweise daran, dass scanf ("% s") die Zeichenfolge analysiert und nach Leerzeichen (Leerzeichen, Tabulator, Zeilenumbruch) sucht.

Ja, CPython führt auch ein Caching durch, um das Lesen von Festplatten zu vermeiden.

davinchi
quelle
12

Ein erstes Element einer Antwort: <iostream>ist langsam. Verdammt langsam. Ich bekomme einen enormen Leistungsschub mit scanfwie unten, aber es ist immer noch zweimal langsamer als Python.

#include <iostream>
#include <time.h>
#include <cstdio>

using namespace std;

int main() {
    char buffer[10000];
    long line_count = 0;
    time_t start = time(NULL);
    int sec;
    int lps;

    int read = 1;
    while(read > 0) {
        read = scanf("%s", buffer);
        line_count++;
    };
    sec = (int) time(NULL) - start;
    line_count--;
    cerr << "Saw " << line_count << " lines in " << sec << " seconds." ;
    if (sec > 0) {
        lps = line_count / sec;
        cerr << "  Crunch speed: " << lps << endl;
    } 
    else
        cerr << endl;
    return 0;
}
JN
quelle
Ich habe diesen Beitrag erst gesehen, als ich meine dritte Bearbeitung vorgenommen habe, aber nochmals vielen Dank für Ihren Vorschlag. Seltsamerweise gibt es jetzt keinen 2x Treffer für mich gegen Python mit der Scanf-Zeile in edit3 oben. Ich benutze übrigens 2.7.
JJC
10
Nach dem Korrigieren der c ++ - Version ist diese stdio-Version wesentlich langsamer als die c ++ - iostreams-Version auf meinem Computer. (3 Sekunden gegen 1 Sekunde)
Karunski
10

Nun, ich sehe, dass Sie in Ihrer zweiten Lösung von cinzu gewechselt haben scanf, was der erste Vorschlag war, den ich Ihnen machen wollte (cin ist sloooooooooooow). Wenn Sie jetzt von scanfzu wechseln fgets, sehen Sie einen weiteren Leistungsschub:fgets ist die schnellste C ++ - Funktion für die Eingabe von Zeichenfolgen.

Übrigens, wusste nichts über diese Synchronisierungssache, nett. Aber du solltest es trotzdem versuchen fgets.

José Ernesto Lara Rodríguez
quelle
2
Außer fgetsist falsch (in Bezug auf die Anzahl der Zeilen und in Bezug auf die Aufteilung der Zeilen auf Schleifen, wenn Sie sie tatsächlich verwenden müssen) für ausreichend große Zeilen, ohne zusätzliche Überprüfungen auf unvollständige Zeilen (und der Versuch, dies zu kompensieren, erfordert die Zuweisung unnötig großer Puffer , wo std::getlinedie Neuzuweisung nahtlos mit der tatsächlichen Eingabe übereinstimmt). Schnell und falsch ist einfach, aber es lohnt sich fast immer, "etwas langsamer, aber korrekt" zu verwenden, was Sie beim Ausschalten sync_with_stdiobringt.
ShadowRanger