String Verkettung Komplexität in C++ und Java

Question

dieses Stück Code vor:

public String joinWords(String[] words) { 
    String sentence = ""; 
    for(String w : words) { 
     sentence = sentence + w; 
    } 
    return sentence; 
} 

Auf jeder Verkettung eine neue Kopie der Zeichenfolge erstellt wird, so dass die Gesamtkomplexität O(n^2) ist. Glücklicherweise konnten wir dies in Java mit einer StringBuffer lösen, die O(1) Komplexität für jeden Anhang hat, dann wäre die Gesamtkomplexität O(n).

Während in C++ std::string::append() hat Komplexität von O(n), und ich bin nicht klar über die Komplexität von stringstream. In C++ gibt es Methoden wie die in StringBuffer mit der gleichen Komplexität?

Answer 1

C++ - Zeichenfolgen sind veränderbar und so dynamisch wie ein StringBuffer. Im Gegensatz zu Java würde dieser Code nicht jedes Mal eine neue Zeichenfolge erstellen. Es hängt nur an den aktuellen.

std::string joinWords(std::vector<std::string> const &words) { 
    std::string result; 
    for (auto &word : words) { 
     result += word; 
    } 
    return result; 
} 

Dies läuft in linearer Zeit, wenn Sie die Größe reserve Sie vorher benötigen. Die Frage ist, ob das Schleifen über den Vektor zum Erhalten von Größen langsamer ist als das automatische Ändern der Größe der Zeichenkette. Das kann ich dir nicht sagen. Zeit es. :)

Wenn Sie nicht aus irgendeinem Grund std::string verwenden möchten (und Sie sollten es in Betracht ziehen; es ist eine absolut respektable Klasse), C++ hat auch String-Streams.

#include <sstream> 
... 

std::string joinWords(std::vector<std::string> const &words) { 
    std::ostringstream oss; 
    for (auto &word : words) { 
     oss << word; 
    } 
    return oss.str(); 
} 

Es ist wahrscheinlich std::string nicht effizienter als die Verwendung, aber es ist ein bisschen flexibler in anderen Fällen - Sie fast jede primitive Art mit ihm, sowie jede Art stringify kann, die eine operator <<(ostream&, its_type&) Überschreibung angegeben hat .

Answer 2

Als ein Beispiel für eine sehr einfache Struktur, die O(n) Komplexität in C++ 11 hat:

template<typename TChar> 
struct StringAppender { 
    std::vector<std::basic_string<TChar>> buff; 
    StringAppender& operator+=(std::basic_string<TChar> v) { 
    buff.push_back(std::move(v)); 
    return *this; 
    } 
    explicit operator std::basic_string<TChar>() { 
    std::basic_string<TChar> retval; 
    std::size_t total = 0; 
    for(auto&& s:buff) 
     total+=s.size(); 
    retval.reserve(total+1); 
    for(auto&& s:buff) 
     retval += std::move(s); 
    return retval; 
    } 
}; 

Verwendung:

StringAppender<char> append; 
append += s1; 
append += s2; 
std::string s3 = append; 

Dies geschieht O (n), wobei n die Anzahl von Charakteren.

Schließlich, wenn Sie wissen, wie lang alle Strings sind, macht nur reserve mit genügend Platz append oder += insgesamt O (n) Zeit. Aber ich stimme zu, dass das peinlich ist.

Verwendung von std::move mit dem oben StringAppender (dh sa += std::move(s1)) erhöht sich die Leistung erheblich für nicht-kurze Strings (oder die Verwendung mit XValues ​​etc)

Ich weiß nicht, die Komplexität der std::ostringstream, aber ostringstream ist für Pretty Print formatierte Ausgabe oder Fälle, in denen hohe Leistung nicht wichtig ist. Ich meine, sie sind nicht schlecht, und sie können sogar Skript-/Interpretierungs-/Bytecode-Sprachen ausführen, aber wenn Sie in Eile sind, brauchen Sie etwas anderes.

Wie üblich müssen Sie profilieren, da konstante Faktoren wichtig sind.

Ein rvalue-reference-to-this-Operator + könnte auch ein guter sein, aber nur wenige Compiler implementieren rvalue-Referenzen zu diesem.

Answer 3

Dies ist etwas tangential zu Ihrer Frage, aber dennoch relevant. (Und zu groß für einen Kommentar!)

Bei jeder Verkettung wird eine neue Kopie der Zeichenfolge erstellt, so dass die Gesamtkomplexität O (n^2) ist.

In Java, die Komplexität von s1.concat(s2) oder s1 + s2 ist O(M1 + M2) wo M1 und M2 sind die jeweiligen Streichlängen. Dies in die Komplexität einer Folge von Verkettungen umzuwandeln, ist im Allgemeinen schwierig. Allerdings, wenn Sie annehmen, N Verkettungen von Strings der Länge M, dann ist die Komplexität in der Tat O(M * N^2) was entspricht, was Sie in der Frage gesagt haben.

Zum Glück in Java wir dies mit einem StringBuffer lösen könnte, die für jede append O(1) Komplexität hat, dann ist die Gesamtkomplexität O(n) wäre.

Im StringBuilder Fall amortisieren die Komplexität von N Anrufe sb.append(s) für Streicher von Größe MO(M*N) ist. Das Schlüsselwort hier ist amortisiert. Wenn Sie Zeichen an StringBuilder anhängen, muss die Implementierung möglicherweise das interne Array erweitern. Die Expansionsstrategie besteht jedoch darin, die Größe des Arrays zu verdoppeln. Und wenn Sie die Mathematik machen, werden Sie sehen, dass im Durchschnitt jedes Zeichen im Puffer während der gesamten Folge von append Aufrufen eine zusätzliche Zeit kopiert wird. Die gesamte Sequenz funktioniert also immer noch als O(M*N) ... und so ist M*N die gesamte Stringlänge.

So ist Ihr Endergebnis korrekt, aber Ihre Aussage über die Komplexität eines einzelnen Anrufs zu append ist nicht korrekt. (Ich verstehe, was du meinst, aber so, wie Sie es sagen, ist facially nicht korrekt.)

Schließlich würde ich beachten, dass in Java Sie StringBuilder statt StringBuffer es sei denn, Sie Notwendigkeit der Puffer sein Thread-sicher verwenden sollten .