c++ if(str1== str2) versus if(str1.length()== str2.length() && str1== str2)




strncmp (8)

Ich habe das zweite im Code eines anderen gesehen, und ich nehme an, dass dieser Längenvergleich durchgeführt wurde, um die Code-Produktivität zu erhöhen. Es wurde in einem Parser für eine Skriptsprache mit einem bestimmten Wörterbuch verwendet: Wörter sind 4 bis 24 Buchstaben lang mit dem Durchschnitt von 7-8 Buchstaben, Alphabet enthält 26 lateinische Buchstaben plus "@", "$" und "_".

Der Längenvergleich wurde verwendet, um den == Operator zu bearbeiten, der mit STL-Strings arbeitet, was offensichtlich mehr Zeit benötigt als der einfache Ganzzahlvergleich. Aber gleichzeitig ist die Verteilung des ersten Buchstabens in dem gegebenen Wörterbuch einfach weiter als eine Verteilung der Wörtergröße, so dass zwei erste Buchstaben des Vergleichens von Zeichenfolgen im Allgemeinen häufiger anders sind als die Größen dieser Zeichenfolgen. Das macht Längenvergleich unnötig.

Ich habe ein paar Tests durchgeführt und das habe ich herausgefunden: Während man zwei zufällige Zeichenfolgen millionenfach testet, ist der zweite Weg viel schneller, so dass der Längenvergleich hilfreich erscheint. Aber in einem Arbeitsprojekt läuft es im Debug-Modus noch langsamer und im Release-Modus zu wenig.

Also, meine Frage ist: Warum Längenvergleich kann den Vergleich zu befestigen und warum kann es verlangsamen?

UPD: Ich mag auch diesen zweiten Weg nicht, aber es war aus einem bestimmten Grund getan worden, und ich frage mich, was ist dieser Grund?

UPD2: Ernsthaft, die Frage ist nicht, wie es am besten geht. Ich benutze in diesem Fall nicht einmal mehr STL-Strings. Es ist kein Wunder, dass Längenvergleich unnötig und falsch ist usw. Das Wunder ist - es neigt dazu, in einem bestimmten Test wirklich etwas besser zu funktionieren. Wie ist das möglich?


Im Allgemeinen sollten Sie dies der STL überlassen und sich nicht darum kümmern.

Wenn dies jedoch ein Bereich ist, den Sie optimieren müssen (was ich ernsthaft bezweifle), UND wenn Sie die Verteilung / Länge der Zeichenfolgen Ihrer Strings verstehen, können Sie eine neue Klasse aus string ableiten und den Operator == überladen, um die Gleichheitstest auf die effizienteste Weise für Ihre Anwendung. (Länge zuerst, erstes Zeichen zuerst, vorwärts, rückwärts, was auch immer).

Das wäre besser, als die "Optimierung" in Ihrem Code verstreut zu haben.


Längenvergleich macht für mich keinen Sinn. Die Verwendung des Vergleichsoperators ist ausreichend


Der Längenvergleich dient dazu, eine Kurzschlussoptimierung zu versuchen.

Ich gehe davon aus, dass der Längenvergleich schneller ist als der vollständige String-Vergleich, wenn also 99% der Fehlanpassungen eliminiert werden können, ist es schneller, als jedesmal den vollständigen String-Vergleich durchzuführen.

Der Code führt den Längenvergleich aus, es wird fehlschlagen, dann ignoriert er den vollständigen Stringvergleich und überspringt den Code.


Die Länge der std :: string ist sehr wahrscheinlich ein Mitglied des std :: string-Objekts. Im Vergleich dazu könnte das erste Zeichen sehr gut auf dem Heap liegen. Das bedeutet, dass der Vergleich der String-Länge den Referenzort verbessert. Natürlich wird dies mit der Short-String-Optimierung noch komplexer - Lhs[0] könnte sich auf dem Heap befinden, während Rhs[0] auf dem Stack ist.


Wenn es darauf ankommt, nehmen Sie an, dass Ihre Bibliothek es bereits getan hat. Verwende deinen Code nicht für Mikrooptimierungen, außer es ist wirklich wichtig.


Wann kann Short Circuiting von Vorteil sein?

Kurzschluss-Optimierungen können nur hilfreich sein, wenn

  • Die Vergleichskosten sind im Vergleich zu den Kosten des vollständigen Tests niedrig
  • der Vergleich führt oft zu Kurzschlüssen

Mathematisch sei S die Kostenbedingung für den Kurzschluß, F die Vollkostenbedingung und P der Prozentsatz der Fälle, in denen Kurzschlüsse auftreten (Vollzustand ist nicht erforderlich).

Die durchschnittlichen Kosten des ursprünglichen Falles (kein Short Circuit) sind F

Die durchschnittlichen Kosten der Short Circuit-Optimierung betragen S + F * (1-P).

Wenn die Optimierung überhaupt einen Nutzen haben soll, muss folgendes gelten:

S + F * (1-P) <F

dh

S <F * P

String Vergleichskosten

Weiter hast du geschrieben:

was offensichtlich mehr Zeit in Anspruch nimmt als ein einfacher ganzzahliger Vergleich.

Dies ist überhaupt nicht offensichtlich. Der Zeichenfolgenvergleich wird beendet, wenn die erste Differenz gefunden wird. Daher kann es in Abhängigkeit von den von Ihnen bearbeiteten Zeichenfolgen in den meisten Fällen beim ersten oder zweiten Zeichen enden. Darüber hinaus kann der Vergleich selbst für längere Zeichenfolgen optimiert werden, indem zuerst DWORDS (4 Zeichen gleichzeitig) verglichen werden, solange in beiden Zeichenfolgen genügend Daten vorhanden sind.

Dein Fall

Der Hauptunterschied zwischen zufälligen Testdaten und Scripting-Parsing ist, dass die echten Daten nicht zufällig sind. Der Parser ist höchstwahrscheinlich deterministisch, und wenn er einmal übereinstimmt, wird er nicht mehr verglichen. Sogar die Skriptdaten sind nicht zufällig - einige Schlüsselwörter werden wahrscheinlich viel häufiger verwendet als andere. Wenn der Parser so konstruiert ist, dass er das am häufigsten verwendete Schlüsselwort zuerst prüft, kann eine überraschend hohe Anzahl von Vergleichen den vollständigen Vergleich erfordern, da ein vollständiger Vergleich immer durchgeführt werden muss, wenn die Zeichenfolge übereinstimmt.


feuern Sie Ihre Implementierung von STL. Es sollte nicht wichtig sein


In Ihrem Zufallstest könnten die Strings lang genug gewesen sein, um die Verstärkung anzuzeigen, während Sie in Ihrem echten Fall mit kürzeren Strings arbeiten können und der konstante Faktor von zwei Vergleichen nicht durch einen Gewinn kompensiert wird, wenn der Stringvergleichstest nicht durchgeführt wird.





stdstring