Schnelle String-Konkatenation gesucht

[snoopysalive]

Hallo!

Eine weitere C++-Frage: Wie konkateniert man std::string-Strings in angemessener Zeit?

Mein Problem:
Ich will eine Textdatei aus über 150.000 Zeilen durchlaufen. Die Datei besteht aus HTML-Texten, welche durch eindeutige Separatoren voneinander getrennt sind. Bei der Abarbeitung werden die einzelnen Zeilen einer Homepage in einen String-Vector gesteckt und sollen anschließend zu einer einzigen Zeile in einen String zusammengesetzt werden. Erraten: Ich will sowas ähnliches wie eine join-Funktion schreiben.

Nachdem mir Google bis jetzt noch keine Antwort darauf liefern konnte, ob es eine join-Funktion in C++ gibt, wende ich mich nun an euch. Gibt es eine join-Funktion in C++? Wenn nicht, wie implementiere ich die, ohne dass mein Programm langsamer als jedes Perl-Skript wird? Hier mal meine rudimentäre join-Funktion:

string join(vector<string>& collection, string& delimiter)
{
    string result = "";
    int i;

    for (i = 0; i < collection.size() - 1; ++i)
    {
        result += collection.at(i) + delimiter;
    }
    result += collection.at(collection.size() - 1);

    return result;
}

Die String-Konkatenation im Inneren der for-Schleife bremst das Programm aber extremst aus. Kommentiere ich die Konkatenation aus, läuft das Programm mit allen darin enthaltenen Bearbeitungsschritten ca. 10 Sekunden. Das ist mehr als doppelt so schnell wie das Perl-Skript, das ich dazu geschrieben habe. Mit der Konkatenation, braucht das Programm zwei bis drei Minuten.

Gruß,
Matthias

 

[MCoder]

Hallo,

du könntest versuchen, den benötigten Speicherplatz abzuschätzen und mit "reserve()" vorher zu reservieren. Die Zeit dürfte beim ständigen Reallozieren des Speichers draufgehen und das sollte man damit verhindern können.

Gruß
MCoder

 

[deepthroat]

Hi.

Welchen Compiler (und welche STL Implementierung) verwendest du denn?

Versuch's mal damit:

#include <sstream>
#include <algorithm>
#include <iterator>

string join(const vector<string>& collection, const string& delimiter) {
  ostringstream o;

  if (!collection.empty()) {
    copy(collection.begin(),
         collection.end() - 1,
         ostream_iterator<string>(o, delimiter.c_str()));

    o << collection.back();
  }

  return o.str();
}

Bei mir dauern 100 Durchläufe für einen Vektor mit 500,000 Elementen etwas mehr als 8 Sek. (Da ist die Zeit um die Einträge aus einer Datei in den Vektor zu laden allerdings dabei)

Gruß

 

[snoopysalive]

Ah, danke für die Anregungen. Ich probiere mal beide Ideen aus.

Ich verwende den GCC 4.1.2 unter OS X. Die dort verwendete STL sollte demnach diejenige sein, die dem GCC per Standard beiliegt.

 

[snoopysalive]

@deepthroat: Hab's grad ausprobiert. Das Programm läuft damit genauso stockend und langsam wie in meinem Codeausschnitt.

Ich find's komisch. Wie wird join denn in Perl realisiert? Da geht das immer ratzfatz. Ich kann mir nicht vorstellen, dass das in C++ nicht mindestens genauso schnell gehen soll.

Dennoch schon mal danke!

 

[deepthroat]

Hi.

Hast du's mal mit dem Vorschlag von MCoder probiert?

#include <numeric>

inline
int sum_length(int c, const string& s) {
  return c + s.length();
}

string join(vector<string>& collection, string& delimiter)
{
  string result;

  if (!collection.empty()) {
    const unsigned int x = accumulate(collection.begin (),
				      collection.end (),
				      0,
				      sum_length);

    const unsigned int len = (x + collection.size() * delimiter.length());

    result.reserve(len);
    int i;

    for(vector<string>::const_iterator it = collection.begin ();
	it != collection.end ();
	++it) {
      result += *it;
      result += delimiter;
    }
    result += collection.back();
  }
  return result;
}

Und vermeide unnötiges Kopieren bei der Werterückgabe:

string s;

join(vec, del).swap(s);

Bei mir braucht das Programm 4,5 sek. - das äquivalente Perl Programm 6,3 sek. Wenn du (so wie Perl intern) mit C-Strings arbeitest (anstatt mit std::strings), geht es noch etwas schneller. Irgendwo muß man halt den Preis für die Objektorientierung und die erweiterte Funktionalität zahlen.

Gruß

 

[higret]

Hi

oder kann es sein, dass du dein Projekt mit Debug-Informationen kompilierst

mfg Higret

 

[deepthroat]

Hi.

Hi

oder kann es sein, dass du dein Projekt mit Debug-Informationen kompilierst

mfg Higret

Das hat fast keinen Einfluss auf die Laufzeit des Programms, da es lediglich dazu führt das die Datei etwas größer wird und dementsprechend die Ladezeit des Programms höher ist. Bei der Ausführung selbst hat das keinen Nachteil.

Gruß