Leistung - mit Zeichenfolgekonstruktor vs mit Verkettung

Ich bin relativ neu in C++. Ich habe ein Codierungsproblem geübt und es war damit verbunden, eine Zeichenkette in Palindrom umzuwandeln.Leistung - mit Zeichenfolgekonstruktor vs mit Verkettung

I wurde Speichern der Zählung Alphabete in einem Vektor und später die palindrome wie diese Erzeugung -

string palindrome_string; 
for (short i = 0; i < 26; ++i) { 
    alphabet_count[i] /= 2; 
    for (short j = 0; j < alphabet_count[i]; ++j) 
     palindrome_string += string(1, static_cast<char>('a' + i)); 
}

Aber für einen bestimmten Testfall (input enthaltend 2,10^5 e s only), das Programm übersteigt wurde das Speicherlimit von 256 MB. Dann habe ich die innere Schleife nur mit dieser Aussage ersetzt -

und das Programm lief gut mit nur etwa 2,4 MB.

Also ich möchte fragen, ob dies mit der Leistung mit der Verwendung von Verkettung vs die Konstruktorfunktion verbunden ist, und wenn ja, was ist/sind die möglichen Grund/s?

Wenn es darauf ankommt, habe ich das Programm mit MS VC++ kompiliert 2010

Wenn es hilft, hier sind die Einreichungen (der Code) - the failed one (Testfall: 10) und the successful one.

Quelle

2017-07-09 PalashV

Wenn Sie den Zusatz wie folgt ausführen, erhalten Sie möglicherweise jede Iteration eine neue Zuweisung. Wahrscheinlich ist das Zuweisen eines etwas größeren Stücks jedes Mal ein schlechter Fall für Ihren Zuordner. Es ist immer noch überraschend, dass es so schlimm wird. – zch

@zch Einverstanden. String wird beim Konstruieren mit etwas Speicherplatz vorbelegt. OP kann versuchen, die String-Konstruktion durch ein einfaches Zeichen zu ersetzen: palindrome_string + = 'a' + i; – texasbruce

Es gibt eigentlich keinen Sinn, eine temporäre Zeichenfolge zu konstruieren. 'palindrome_string.append (static_cast ('a' + i), alphabet_count [i])' würde das gleiche tun. – VTT

std::string sollte Speicher in einer Art und Weise zuweisen, um amortisierte konstante Zeit zu erreichen. Eine einfache Implementierung wäre es, jedes Mal um einen Faktor 2 zu wachsen, wenn mehr Platz benötigt wird, wie here angegeben ist.

Es besteht die Möglichkeit, dass jedes Mal, wenn Sie etwas zu Ihrem palindrome_string in der inneren Schleife addieren, diese Zeichenfolge Speicher neu zuordnet. Allerdings verstehe ich nicht, wie das so schrecklich aussieht. Ich meine, selbst wenn die einfache Implementierung, die oben erwähnt wurde, den Speicher bei einer Iteration Ihrer inneren Schleife verdoppelt, dann müsste sie in vielen der nächsten Iterationen den Speicherplatz nicht erneut zuweisen.

Quelle

2017-07-09 20:36:36 gsamaras

Ich dachte zunächst, dass ein 'char' 1 Byte ist und da die Frage garantiert ein max. von 2,10^5 Zeichen, ich nahm an, es sollte nicht mehr als ~ 200 KB nehmen, aber anscheinend funktioniert es nicht so, und wie ist es überhaupt in MBs dazu gekommen, es verwirrt mich immer noch. – PalashV

Ich sah, dass Sie Ihre Frage beantwortet, gute Nachrichten @ PalashV ~ – gsamaras

Danke. Ich konnte es für die nächsten 2-3 Tage nicht herausfinden, und die Frage erhielt keine Antworten, aber eines Tages klickte es nur, dass die Schleife fehlerhaft sein könnte. Ich las es erneut und es war die ganze Zeit, ich war schuld.:( Danke für Ihre Zeit aber. :) – PalashV

Das Problem ist nicht die Leistung, es war die innere Schleife. j ist vom Typ short, während alphabet_count[i] vom Typ long ist, deshalb ist es passiert.

Quelle

2017-07-12 14:16:17 PalashV

Leistung - mit Zeichenfolgekonstruktor vs mit Verkettung

Antwort

Verwandte Themen