Geschwindigkeit QString::replace() - lohnt ein contains()?

[oberschlingel]

Hallo,

ich hätte mal eine Geschwindigkeitsfrage und hoffe es kennt sich jemand damit aus:
Ich muss regelmäßig einen String aktualisieren und dabei unter Umständen (flag) das deutsche scharfe S (Eszett: ß) durch ein Doppel-S (Schweiz) ersetzen. Allerdings kommt so ein scharfes S sehr selten vor, so dass ich mich frage, ob es sinnvoller ist

Code: Alles auswählen

if (flag && textOutputSub.contains(QChar(0x223), Qt::CaseSensitive)) {
    textOutputSub.replace(QChar(0x223), "ss", Qt::CaseSensitive);
}

zu schreiben, oder direkt

Code: Alles auswählen

if (flag) {
    textOutputSub.replace(QChar(0x223), "ss", Qt::CaseSensitive);
}

???

Der Aktualisierungvorgang sollte so schnell wie möglich ablaufen. Welcher Code ist wohl schneller?

Tausend Dank!!

[Zandru]

das kommt ganz drauf an, wie oft wirklich ersetzt werden muss. wenn nichts ersetzt wird, ist contains() deutlich schneller. andererseits wirds halt zusätzlich aufgerufen, wenn dann doch mal ersetzt werden muss.

ich würde grundsätzlich aber nichts optimieren, außer dein Programm ist nicht performant genug - und dann würde ich systematisch nach den größten "Zeitfressern" suchen.

Grundsätzlich "optimierten" Code zu schreiben stört nur bei der Verständlichkeit.

[oberschlingel]

Beim genauer darüber nachdenken hast Du natürlich völlig Recht.

Vielen Dank für die Antwort!

[buhrmi]

??

contains() benötigt lineare Zeit für das durchlaufen des Strings, und replace() benötigt auch lineare Zeit für das durchlaufen.

Ich verstehe nicht, was das contains() an Geschwindigkeit bringen soll? Kann mir nicht vorstellen, dass contains() und replace() sich großartig in der Geschwindigkeit unterscheiden (beide O(n)), es sei denn es ist grausig implementiert.

[macman]

Ein contains macht keinen replace und hört auch beim ersten Auftreten auf, kann also durchaus schneller sein. Kann, in den meisten Fällen wird es aber kaum was bringen. Je nach dem wie oft etwas ersetzt werden soll, würde es sogar bremsen.

[Zandru]

schau mal in den source rein, contains ist z.B. für das suchen nach einzelnen chars optimiert, replace hat diese optimierung nicht mehr.

aber wie gesagt, ich würde "überoptimierung" vermeiden, lieber den Source so einfach und lesbar wie möglich lassen.

[neuschi]

Hallo zusammen,

meiner Meinung nach kann diese Optimierung nicht viel bringen:

Gegeben: ein String mit n Zeichen.

Fall 1: Der String enthält das gesuchte Zeichen nicht:

ohne "Optimierung":
replace() sucht ein Vorkommen des zeichens, muss dazu n Zeichen vergleichen.

mit "Optimierung":
contains() vergleicht n Zeichen, replace() wird nicht aufgerufen.

in diesem Fall ist der Aufwand identisch.


Fall 2: Der String enthält das Zeichen mindestens einmal.

In diesem Fall sind die Kosten für replace() vernachlässigbar, weil es ja auf jeden Fall ausgeführt werden muss.

mit der "Optimierung" kommen aber noch die Kosten für die Suche von contains() hinzu, die im Mittel bei n/2 liegen.

Damit führt diese "Optimierung" eher zu mehr Aufwand. Wenn replace() vernünftig implementiert wurde (wovon auszugehen ist), dann gewinnst du mit einem vorgeschalteten "contains()" nichts.

\Ralf

[Zandru]

ich hab mir den source von replace angeschaut

contains ist tatsächlich "optimierter" als replace (für den Fall dass nichts gefunden wird; oder auch für den Fall, daß der Suchbegriff nur 1 char ist)

aber das ganze ist echt akademisch. solange kein Optimierungsbedarf besteht, würde ich nicht optimieren.

[neuschi]

Hallöchen,

ich hab das gerade mal mit Hilfe von "Rational Quantify" ausprobiert:

bei 200000 Texten, in denen bei ca. 5% der gesuchte Buchstabe vorkommt, bekomme ich folgendes Ergebnis:

ohne Optimierung: 83003765 Prozessorzyklen
mit Optimierung: 14003685 Prozessorzyklen

Damit ist die Optimierung tatsächlich sinnvoll, die Routine ist um den Faktor 5-6 schneller!

Details:

ohneOptimierung():

Code: Alles auswählen

200000 times (76.87%) QString::replace()
200000 times (12.05%) QString::QString()
200000 times (7.95%) QString::~QString()
200000 times (1.20%) QChar::QChar()

mitOptimierung():

Code: Alles auswählen

200000 times (40.83%) QString::contains()
 10023 times (31.01%) QString::replace()
210023 times (40.83%) QChar::QChar()
200000 times (5.71%) QBool::operator const * (void) const
 10023 times (3.58%) QString::QString()
 10023 times (2.36%) QString::~QString()

Offenbar ist der Kopieraufwand, der durch replace() verursacht wird hier der Schuldige für die schlechtere Performance.

Hope this helps...

\Ralf

[Zandru]

hihi, schau doch einfach kurz in den Source

das liegt nicht am "Kopieraufwand" denn wenn nix zu replacen ist, kopiert replace nix.

Das liegt einfach daran, daß replace nicht zusätzlich für bestimmte Fälle optimiert ist, die im contains() (bzw. indexOf()) gesondert behandelt werden.

trotz dem gezeigtem Performancegewinn würde ich aber weiter davon abraten, grundsätzlich vor replace ein if(contains(...)) hinzuschreiben, denn das bringt nur was wenn das replace wirklich selten was zu tun hat, und macht den Code halt nicht lesbarer.

[neuschi]

hihi, schau doch einfach kurz in den Source

das liegt nicht am "Kopieraufwand" denn wenn nix zu replacen ist, kopiert replace nix.

Falsch!
Du kannst an den Werten oben sehen, dass ohne das "contains()" der Konstruktor von QString() genauso oft aufgerufen wird wie replace() selber, auch wenn es nichts zu replacen gibt! Das meine ich mit "Kopieren".
Das ist aber auch logisch, da replace() einen QString zurückliefert. (Aber was war da nochmal mit implicit sharing?! hmm. muss doch mal in den Code gucken),

Allein der Verzicht auf diese Operationen bringt schon erhebliche Geschwindigkeitsvorteile.

\Ralf

[buhrmi]

Damit ist die Optimierung tatsächlich sinnvoll, die Routine ist um den Faktor 5-6 schneller!

hui das hätt ich nicht einmal im traum vermutet

[Zandru]

hmm. muss doch mal in den Code gucken

hehe, aye, besser das

die zusätzlichen QString() Aufrufe kommen daher, dass es keine "richtige" Version vom ::replace für QChar als Suchbegriff gibt, und daher der QChar jedesmal erstmal in einen QString umgewandelt wird...

[neuschi]

die zusätzlichen QString() Aufrufe kommen daher, dass es keine "richtige" Version vom ::replace für QChar als Suchbegriff gibt, und daher der QChar jedesmal erstmal in einen QString umgewandelt wird...

Hab jetzt mal nachgeguckt, du hast recht:

Code: Alles auswählen

QString& QString::replace(QChar ch, const QString &after, Qt::CaseSensitivity cs)
{
    return replace(QString(ch), after, cs);
}

Das erklärt die schwache Performance und damit ist klar, dass sich das "contains()" vorher lohnt.

\Ralf