Effiziente String -Verkettung in C ++

StackOverflow https://stackoverflow.com/questions/611263

Frage

Ich hörte ein paar Leute, die sich Sorgen um den "+" -Operator in Std :: String und verschiedene Problemumgehungen zum Ausdruck bringen, um die Verkettung zu beschleunigen. Sind eine davon wirklich notwendig? Wenn ja, was ist der beste Weg, um Saiten in C ++ zu verkettet?

War es hilfreich?

Lösung

Die zusätzliche Arbeit lohnt sich wahrscheinlich nicht, es sei denn, Sie brauchen wirklich Effizienz. Sie werden wahrscheinlich viel bessere Effizienz haben, indem Sie Operator += stattdessen verwenden.

Jetzt nach diesem Haftungsausschluss werde ich Ihre tatsächliche Frage beantworten ...

Die Effizienz der STL -String -Klasse hängt von der Implementierung von STL ab, die Sie verwenden.

Sie könnten Effizienz garantieren und mehr Kontrolle haben selbst durch die Verkettung manuell über C-integrierte Funktionen.

Warum Operator+ nicht effizient ist:

Schauen Sie sich diese Schnittstelle an:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Sie können sehen, dass ein neues Objekt nach jedem +zurückgegeben wird. Das bedeutet, dass jedes Mal ein neuer Puffer verwendet wird. Wenn Sie eine Menge zusätzlicher + Operationen ausführen, ist dies nicht effizient.

Warum Sie es effizienter machen können:

  • Sie garantieren die Effizienz, anstatt einem Delegierten zu vertrauen, um dies effizient für Sie zu tun
  • Die STD :: String -Klasse weiß nichts über die maximale Größe Ihrer Saite oder wie oft Sie sich damit verkettet. Möglicherweise haben Sie dieses Wissen und können Dinge basierend auf diesen Informationen tun. Dies wird zu weniger Neuallokationen führen.
  • Sie werden die Puffer manuell kontrollieren, damit Sie sicher sein können, dass Sie die gesamte Zeichenfolge nicht in neue Puffer kopieren, wenn Sie nicht möchten, dass dies geschieht.
  • Sie können den Stapel für Ihre Puffer anstelle des Haufens verwenden, was viel effizienter ist.
  • Der String + -Operator erstellt ein neues String -Objekt und gibt es daher mit einem neuen Puffer zurück.

Überlegungen zur Umsetzung:

  • Behalten Sie die Saitenlänge im Auge.
  • Halten Sie einen Zeiger am Ende der Zeichenfolge und am Start oder nur am Start und verwenden Sie die Länge als Offset, um das Ende der Zeichenfolge zu finden.
  • Stellen Sie sicher, dass der Puffer, in dem Sie Ihre Zeichenfolge speichern
  • Verwenden Sie Strcpy anstelle von StrCat, damit Sie nicht über die Länge der Zeichenfolge iterieren müssen, um das Ende der Zeichenfolge zu finden.

Seildatenstruktur:

Wenn Sie wirklich schnelle Verkettungen benötigen, sollten Sie a verwenden Seildatenstruktur.

Andere Tipps

Reservieren Sie Ihren endgültigen Speicherplatz vorher und verwenden Sie dann die Anhangmethode mit einem Puffer. Angenommen, Sie erwarten, dass Ihre endgültige Zeichenfolge 1 Million Zeichen beträgt:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Ich würde mich darüber keine Sorgen machen. Wenn Sie es in einer Schleife tun, werden die Saiten immer das Speicher vorbereiten, um die Reallokationen zu minimieren. Verwenden Sie einfach operator+= In diesem Fall. Und wenn Sie es manuell tun, so etwas oder länger

a + " : " + c

Anschließend erzeugt es Zeiträume - auch wenn der Compiler einige Rückgabewertkopien beseitigen könnte. Das liegt daran, dass in einem nacheinander genannten genannten operator+ Es weiß nicht operator+ Aufruf. Ich würde mir lieber keine Sorgen machen, bevor ich nicht zuerst profiliert habe. Aber lassen Sie uns ein Beispiel dafür nehmen, das zu zeigen. Wir stellen zuerst Klammern ein, um die Bindung klar zu machen. Ich habe die Argumente direkt nach der Funktionserklärung eingesetzt, die für Klarheit verwendet wird. Darunter zeige ich, was der daraus resultierende Ausdruck dann ist:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Nun, in dieser Ergänzung, tmp1 ist das, was durch den ersten Anruf an den Operator+ mit den gezeigten Argumenten zurückgegeben wurde. Wir gehen davon aus, dass der Compiler wirklich klug ist und die Rückgabewertkopie optimiert. Wir haben also eine neue Zeichenfolge, die die Verkettung von enthält a und " : ". Nun, das passiert:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Vergleichen Sie das mit folgenden:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Es verwendet die gleiche Funktion für eine temporäre und für eine benannte Zeichenfolge! Also der Compiler hat Um das Argument in eine neue Zeichenfolge zu kopieren und sich daran anzuhängen und es aus dem Körper von der Leiche zurückzugeben operator+. Es kann nicht die Erinnerung an einen vorübergehenden und angehängt. Je größer der Ausdruck ist, desto mehr Kopien von Saiten müssen durchgeführt werden.

Das nächste Visual Studio und GCC unterstützen C ++ 1x Semantik bewegen (ergänzen Kopieren Sie die Semantik) und RValue -Referenzen als experimentelle Addition. Dadurch wird herausgefunden, ob der Parameter vorübergehend verweist oder nicht. Dies macht solche Ergänzungen erstaunlich schnell, da alle oben genannten "Add-Pipeline" ohne Kopien enden.

Wenn sich herausstellt, dass es sich um einen Engpass handelt, können Sie es trotzdem tun

 std::string(a).append(" : ").append(c) ...

Das append Anrufe fügen das Argument an *this und dann einen Verweis auf sich selbst zurück. Dort erfolgt also kein Kopieren von Zeiträumen. Oder alternativ die operator+= Kann verwendet werden, aber Sie würden hässliche Klammern benötigen, um Vorrang zu beheben.

Für die meisten Anwendungen ist es einfach keine Rolle. Schreiben Sie einfach Ihren Code, ohne sich zu bewusst, wie genau der + Operator funktioniert, und nehmen Sie nur die Sache selbst in die Hand, wenn er zu einem offensichtlichen Engpass wird.

Im Gegensatz zu .Net System.Strings, C ++ Std :: Strings sind Veränderlich und kann daher durch einfache Verkettung genauso schnell aufgebaut werden wie mit anderen Methoden.

Vielleicht Std :: Stringstream stattdessen?

Aber ich stimme dem Gefühl zu, dass Sie es wahrscheinlich nur aufrechterhalten und verständlich halten und dann profilieren sollten, um zu sehen, ob Sie wirklich Probleme haben.

Im Imperfect C ++, Matthew Wilson präsentiert a dynamisch String-Concatenator, die die Länge der endgültigen Zeichenfolge vormontiert, um nur eine Zuordnung zu haben, bevor alle Teile verkettet werden. Wir können auch einen statischenokatenator implementieren, indem wir mit spielen Ausdrucksvorlagen.

Diese Art von Idee wurde in STLPORT STD :: STRING -Implementierung implementiert - die aufgrund dieses genauen Hacks nicht dem Standard entspricht.

std::string operator+ Zuteilt eine neue Zeichenfolge und kopiert jedes Mal die beiden Operanden. Wiederholen Sie viele Male und es wird teuer, o (n).

std::string append und operator+= Auf der anderen Seite steigen Sie die Kapazität jedes Mal um 50% um 50%, wenn die Saite wachsen muss. Dies reduziert die Anzahl der Speicherzuweisungen und Kopiervorgänge erheblich, o (log n).

Für kleine Saiten spielt es keine Rolle. Wenn Sie große Saiten haben, sollten Sie sie besser aufbewahren, da sie sich in Vektor oder in einer anderen Sammlung als Teile befinden. Fügen Sie Ihren Algorithmus hinzu, um mit solch einer Datenmenge anstelle der einen großen String zu arbeiten.

Ich bevorzuge STD :: ostringstream für eine komplexe Verkettung.

Wie bei den meisten Dingen ist es einfacher, etwas nicht zu tun, als es zu tun.

Wenn Sie einer GUI große Zeichenfolgen ausgeben möchten, kann es sein, dass alles, was Sie ausgeben, die Saiten in Teilen besser als eine große Zeichenfolge verarbeiten können (z. B. den Text in einem Texteditor - normalerweise als separates Zeilen aufbewahren Strukturen).

Wenn Sie in eine Datei ausgeben möchten, streamen Sie die Daten, anstatt eine große Zeichenfolge zu erstellen und diese auszugeben.

Ich habe nie die Notwendigkeit gefunden, die Verkettung schneller zu machen, wenn ich unnötige Verkettung aus langsamem Code entfernt habe.

Eine einfache Array von Zeichen, die in einer Klasse eingekapselt ist, die die Arraygröße und die Anzahl der zugewiesenen Bytes im Auge behält, ist am schnellsten.

Der Trick besteht darin, zu Beginn nur eine große Zuteilung durchzuführen.

bei

https://github.com/pedro-vicente/table-string

Benchmarks

Für Visual Studio 2015, X86 -Debug -Build, Substanzverbesserung gegenüber C ++ Std :: String.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |

Wahrscheinlich die beste Leistung, wenn Sie in der resultierenden Zeichenfolge (Reserve-) Platz vor dem Allocalclocation-Bereich vorhanden sind. 

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Verwendungszweck:

std::string merged = concat("This ", "is ", "a ", "test!");
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top