istream, eine zeile zurück springen[gelöst]

Rustyspoon

ich will eigentlich nciht groß rum diskutieren sondern nur ne lösung für mein problem, aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Tachyon

Rustyspoon schrieb:

ich will eigentlich nciht groß rum diskutieren sondern nur ne lösung für mein problem, aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Hast Du es mal so probiert? Woher weisst Du, dass "viel Zeit kosten würde"?

DocShoe

Jungejunge, du brauchst Hilfe für eine Funktion, die keinen bzw. einen oder zwei Parameter erwartet? Ist das dein Ernst?

LordJaxom

Du musst mit seekg an die Position springen, an der die letzte Zeile begonnen hat, oder zeichenweise rückwärts bis zum letzten '\n' lesen. Eine Funktion zum Rückwärtslesen von Zeilen gibt es nicht.

Du hast behauptet, dass das Zwischenspeichern viel Zeit kostet und weniger effizient als das Zurückspringen und neu Einlesen ist. Das sehe ich jetzt nicht ein. Deswegen die Frage: "Wie kommst Du darauf?"

Rustyspoon schrieb:

aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Ja und? Das ist eine sehr billige Operation.

Alternativ könnte man es so machen:

string zeilen[2];
for (int aktuell=0; getline(is,zeilen[aktuell]); aktuell^=1) {
  // zeilen[aktuell]   <-- zuletzt gelesen
  // zeilen[aktuell^1] <-- die davor
}

Das ist vielleicht ein paar Nanosekunden schneller als das davor.
Kannste ja mal testen...

Rustyspoon

LordJaxom schrieb:

Du musst mit seekg an die Position springen, an der die letzte Zeile begonnen hat, oder zeichenweise rückwärts bis zum letzten '\n' lesen. Eine Funktion zum Rückwärtslesen von Zeilen gibt es nicht.

ich will die zeile davor nochmal lesen nicht die selbe zeile nochmal

Athar

Rustyspoon schrieb:

ich will eigentlich nciht groß rum diskutieren sondern nur ne lösung für mein problem, aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Ja, aber die Vertauschung ist kostenlos (fast).
Edit: moment mal, der war gut. Du ziehst ernsthaft ein Zurückspringen und neu einlesen einer Stringvertauschung vor? Das Vertauschen dürfte dich drei CPU-Instruktionen kosten, deine Idee kostet dich höchstwahrscheinlich hunderte bis tausende Zyklen.

Rustyspoon

krümelkacker schrieb:

Du hast behauptet, dass das Zwischenspeichern viel Zeit kostet und weniger effizient als das Zurückspringen und neu Einlesen ist. Das sehe ich jetzt nicht ein. Deswegen die Frage: "Wie kommst Du darauf?"

Rustyspoon schrieb:

aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Ja und? Das ist eine sehr billige Operation.

Alternativ könnte man es so machen:
string zeilen[2];
for (int aktuell=0; getline(is,zeilen[aktuell]); aktuell^=1) {
  // zeilen[aktuell]   <-- zuletzt gelesen
  // zeilen[aktuell^1] <-- die davor
}
Das ist vielleicht ein paar Nanosekunden schneller als das davor.
Kannste ja mal testen...

ich verstehe die forschleife schon nicht :>

Ad aCTa

So könnte es zwar klappen, ist aber mindestens genauso teuer wie Strings zu swappen.

std::string line;
std::getline(input_stream, line);
std::streambuf* buffer = input_stream.rdbuf();
buffer->pubseekpos(std::ios::beg);
buffer->sputn(line.c_str(), line.size());

Rustyspoon

Athar schrieb:

Rustyspoon schrieb:

ich will eigentlich nciht groß rum diskutieren sondern nur ne lösung für mein problem, aber hab ich jetzt nicht für jede zeile die ich einlese eine zusätzliche vertauschung von zwei strings?

Ja, aber die Vertauschung ist kostenlos (fast).
Edit: moment mal, der war gut. Du ziehst ernsthaft ein Zurückspringen und neu einlesen einer Stringvertauschung vor? Das Vertauschen dürfte dich drei CPU-Instruktionen kosten, deine Idee kostet dich höchstwahrscheinlich hunderte bis tausende Zyklen.

wo ist denn der unterschied zwischen dem speichern und dem tauschen?

Athar

"Speichern" zerstört den alten String (intern) und kopiert einen anderen an dessen Stelle. Beim Vertauschen werden die lediglich die internen Zeiger getauscht und fertig.

Ich habe das kurz getestet: Vertauschen kostet bei mir etwa 20 CPU-Zyklen pro Zeile, Zurückspringen und neueinlesen kostet ~14.200 Zyklen pro Zeile.

Insgesamt ist dieser Ansatz 50 mal langsamer als wenn du die letzte Zeile zwischenspeicherst (26 ms vs. 1320 ms für 274817 Zeilen in 2,7 MiB).
So viel zu "würde bei großen Dateien viel Zeit kosten" :p

Je nachdem, wie string bzw string::swap implementiert ist, ist das mit dem string-array von Seite 1 eventuell noch besser Laufzeit-technisch. Beim GCC ist string::swap schon super schnell. Bei MSVC meines Wissens nach etwas aufwändiger.

Rustyspoon

die Datei die ich habe ist 20 mb groß und hat ca 2,5 mio zeilen. Außerdem könenn die Dateien auch noch größer werden. Desshalb ist es für mich schwer vorstellbar, dass es günstiger ist 2,5mio mal zu tauschen/speichern. Anstatt ein einziges mal, eine zeile zurück zu springen.
Ich hab den effekt von dem tauschen auch noch immer nicht genau verstanden.

Ich verstehe das so, dass beim tauschen der zusätzliche aufwand pro zeile zwei adress/zeiger vertauschungen ist und absolut ein String an speicher mehr gebraucht wird,

Bei zwischenspeichern ist der Absolute aufwand gleich aber bei jeder zeile muss eine komplette Copiraktion des inhaltes durchgeführt werden?

Gruß

DocShoe

Vorschlag zur Güte: Implementier´ beides und miss was schneller ist. Kannst deine Ergebnisse ja anschließend hier mitteilen.

Athar

Ich verstehe das so, dass beim tauschen der zusätzliche aufwand pro zeile zwei adress/zeiger vertauschungen ist und absolut ein String an speicher mehr gebraucht wird,

Soweit richtig, der zusätzliche Speicherverbrauch ist aber irrelevant...

Bei zwischenspeichern ist der Absolute aufwand gleich aber bei jeder zeile muss eine komplette Copiraktion des inhaltes durchgeführt werden?

Vertauschen=Zwischenspeichern bei krümelkackers Variante.

... wie dem auch sei, wenn du tatsächlich nur ein einziges Mal in Verlauf des ganzen Einlesevorgangs zurückspringen musst, dann ist das schon ab nur 7.000 Zeilen die bessere Lösung. Eine Ausnahme liegt vor, wenn Seeking bei der Datei nicht möglich ist.

SeppJ

Athar schrieb:

... wie dem auch sei, wenn du tatsächlich nur ein einziges Mal in Verlauf des ganzen Einlesevorgangs zurückspringen musst, dann ist das schon ab nur 7.000 Zeilen die bessere Lösung. Eine Ausnahme liegt vor, wenn Seeking bei der Datei nicht möglich ist.

Da wäre ich mir nicht so sicher, vermutlich dauert beides ungefähr gleich lang, die Rückspringvariante jedoch ein paar Takte länger.

Bedenke, dass Ein-/Ausgabe mit Abstand das langsamste ist, was im Computer abläuft. Die Stringoperation ist jedoch extrem schnell. Vermutlich wird das Programm die meiste Zeit auf die Datei warten. Ob es während des Wartens noch 20 Takte für Stringvertauschung benutzt macht die Dateioperation nicht schneller oder langsamer. Der einmalige Rücksprung wird natürlich Zeit kosten, aber einmal Springen bei zigtausenden Zeilen dürfte insgesamt nicht viel ausmachen.

Das wäre natürlich anders, wenn die Daten schon im Speicher lägen, also beispielsweise wenn aus einem Stringstream gelesen würde.

P.S.: @Threadersteller: Eine 20 MB Datei und du machst dir Sorgen um die Lesegeschwindigkeit? Programmierst du für C64?

Nukularfüsiker

Rustyspoon schrieb:

Desshalb ist es für mich schwer vorstellbar, dass es günstiger ist 2,5mio mal zu tauschen/speichern.

Das gute beim Computer ist, dass man sich solche Sachen nicht vorstellen muss, sondern es einfach ausprobieren kann. Die Zeit, die du hier mit herumkritteln an einer funktionierenden Lösung aus abergläubischen Gründen verplemperst, könntest du besser genutzt haben.

Rustyspoon

SeppJ schrieb:

P.S.: @Threadersteller: Eine 20 MB Datei und du machst dir Sorgen um die Lesegeschwindigkeit? Programmierst du für C64?

wie ich sagte, die könne auch größer sein. außerdem interessiert es mich auch einfach so allgemein.

btw.
swapen und ueberschreiben spart tatsächlich etwas zeit. wie das mit dem zurückspringen geht habe ich noch nicht verstanden.

Athar

Ich ging von allen Betrachtungen davon aus, dass sich die Datei ohnehin schon vollständig im Filecache befindet. Muss zwar nicht der Fall sein, aber:

SeppJ schrieb:

Der einmalige Rücksprung wird natürlich Zeit kosten, aber einmal Springen bei zigtausenden Zeilen dürfte insgesamt nicht viel ausmachen.

Eben.

Moment mal: bei der Zurückspringvariante muss man sich beim Einlesen einer neuen Zeile die Position der alten merken - das tellg() kostet auch wieder mehrere tausend Zyklen pro Zeile.

Gut, dann unterm Strich:
Vergiss das mit dem Zurückspringen einfach.
Letzte Zeile merken ist in allen Lebenslagen besser.

Rustyspoon

Athar schrieb:

Ich ging von allen Betrachtungen davon aus, dass sich die Datei ohnehin schon vollständig im Filecache befindet. Muss zwar nicht der Fall sein, aber:

SeppJ schrieb:

Der einmalige Rücksprung wird natürlich Zeit kosten, aber einmal Springen bei zigtausenden Zeilen dürfte insgesamt nicht viel ausmachen.

Eben.

Moment mal: bei der Zurückspringvariante muss man sich beim Einlesen einer neuen Zeile die Position der alten merken - das tellg() kostet auch wieder mehrere tausend Zyklen pro Zeile.

Gut, dann unterm Strich:
Vergiss das mit dem Zurückspringen einfach.
Letzte Zeile merken ist in allen Lebenslagen besser.

selbst wenn es für das ausrechnen der stelle und für das springen, zweimal mehrere tausen sind ist das unterm strich n absoluter wert und die nadere variante ist lineare und wird somit iwann durch die erste übertrumpft.