if (str1 == str2) versus if (str1.length () == str2.length () & amp; & amp; & amp; str1 == str2)

Question

J'ai vu la seconde dans le code d'un autre et je suppose que cette comparaison de longueur a été effectuée pour augmenter la productivité du code. Il a été utilisé dans un analyseur syntaxique pour une langue de script avec un dictionnaire spécifique: les mots ont une longueur de 4 à 24 lettres et une moyenne de 7 à 8 lettres, l’alphabet comprend 26 lettres latines, plus "@", "$". et "_".

La comparaison de longueur a été utilisée pour échapper à l'opérateur == travaillant avec des chaînes STL, ce qui prend évidemment plus de temps que la simple comparaison d'entiers. Mais dans le même temps, la distribution des premières lettres dans le dictionnaire donné est simplement plus large que la distribution de la taille des mots. Par conséquent, les deux premières lettres des chaînes de comparaison seront généralement plus souvent différentes de la taille de ces chaînes. Cela rend la comparaison de longueur inutile.

J'ai effectué quelques tests et c'est ce que j'ai découvert: lors de la comparaison de millions de fois de chaînes de caractères aléatoires, la seconde méthode est beaucoup plus rapide, donc la comparaison de longueur semble être utile. Mais dans un projet opérationnel, cela fonctionne encore plus lentement en mode débogage et plus rapidement en mode relâchement.

Alors, ma question est la suivante: pourquoi la comparaison de longueurs peut-elle accélérer la comparaison et pourquoi peut-elle la ralentir?

UPD: Je n'aime pas cette deuxième façon non plus, mais cela a été fait pour une raison, je suppose, et je me demande quelle est cette raison.

UPD2: Sérieusement, la question n'est pas de savoir comment faire au mieux. Je n'utilise même plus les chaînes STL dans ce cas. Il n’est pas étonnant que la comparaison de longueur soit inutile ou fausse, etc. L’émerveillement est que cela a tendance à fonctionner un peu mieux dans un test donné. Comment est-ce possible?

Answer 1

Dans votre test aléatoire, les chaînes ont peut-être été suffisamment longues pour indiquer le gain, alors que dans votre cas réel, vous pouvez traiter des chaînes plus courtes et le facteur constant de la comparaison à deux n'est compensé par aucun gain en ne réalisant pas la partie comparaison de chaînes de le test.

Answer 2

Si cela importait, supposez que votre bibliothèque l’ait déjà fait. Ne gâchez pas votre code de cette façon pour les micro-optimisations sauf si cela compte vraiment.

Answer 3

Dans quels cas le court-circuit peut-il être bénéfique

Les optimisations de court-circuit ne peuvent être utiles que lorsque:

• le coût de la comparaison est faible comparé au coût du test complet
• la comparaison aboutit souvent à un court-circuit

Mathématiquement, notons S le coût de la condition de court-circuit, F le coût de la condition complète et P le pourcentage de cas où un court-circuit se produit (la condition complète n’est pas nécessaire).

Le coût moyen du boîtier d'origine (pas de court-circuit) est de F

Le coût moyen de l'optimisation du court-circuit est de S + F * (1-P)

Par conséquent, si l'optimisation doit présenter un avantage quelconque, les éléments suivants doivent être appliqués:

S + F * (1-P) < F

c'est-à-dire

S < F * P

Coût de la comparaison de chaînes

Vous avez également écrit:

qui prend évidemment plus de temps qu'une simple comparaison d'entiers.

Cela n’est pas évident du tout. La comparaison de chaînes se termine lorsque la première différence est trouvée. Par conséquent, en fonction des chaînes que vous traitez, elle peut se terminer au premier ou au deuxième caractère dans la grande majorité des cas. De plus, la comparaison peut être optimisée même pour des chaînes plus longues en comparant d'abord DWORDS (4 caractères à la fois) tant qu'il y a suffisamment de données dans les deux chaînes.

Votre cas

La principale différence entre les données de test aléatoires et l'analyse de script est que les données réelles sont loin d'être aléatoires. L'analyseur est très probablement déterministe, et une fois qu'il correspond, il ne fait plus la comparaison. Même les données de script ne sont pas aléatoires - certains mots clés sont susceptibles d'être utilisés beaucoup plus que d'autres. Si l'analyseur syntaxique est construit de telle sorte qu'il vérifie d'abord le mot clé le plus couramment utilisé, un nombre étonnamment élevé de comparaisons peut nécessiter une comparaison complète, la comparaison complète devant toujours être effectuée lorsque les chaînes correspondent.

Answer 4

En général, vous devriez laisser cela à la STL et ne vous en préoccupez pas.

Toutefois, si c’est un domaine que vous devez optimiser (ce dont je doute sérieusement), ET si vous comprenez la distribution des lettres / la longueur de vos chaînes, vous pouvez dériver une nouvelle classe de chaîne et surcharger l’opérateur ==. effectuer le test d'égalité de la manière la plus efficace pour votre application. (Longueur en premier, premier caractère en premier, en avant, en arrière, peu importe).

Ce serait mieux que d'avoir "l'optimisation" dispersée dans votre code.

Answer 5

L'implémentation de l'opérateur std :: string == n'a aucun moyen de savoir s'il serait plus rapide de vérifier la longueur en premier ou de commencer à vérifier les caractères. Vérifier clairement la longueur est un gaspillage de chaînes de même longueur. Par conséquent, différentes implémentations de STL auront probablement des performances différentes.

Ne placez la vérification de longueur explicite que comme optimisation finale (clairement commentée en tant que telle), et uniquement si votre profileur confirme l'avantage.

Answer 6

la comparaison de longueur n'a aucun sens pour moi .. utiliser l'opérateur de comparaison est suffisant

Answer 7

Lancez votre implémentation de STL. Cela ne devrait pas avoir d'importance

Answer 8

La comparaison de longueur est là pour essayer une optimisation de court-circuit.

Je suppose que la comparaison de longueur est plus rapide que la comparaison de chaîne complète, donc si cela peut éliminer 99% des incohérences, ce sera plus rapide que de faire la comparaison de chaîne complète à chaque fois.

Le code exécutera la comparaison de longueur, il échouera, puis il ignorera la comparaison de chaîne complète et ignorera le code.

Answer 9

La longueur de std :: string est très probablement un membre de l'objet std :: string. En comparaison, le premier caractère pourrait très bien être sur le tas. Cela signifie que comparer la longueur de la chaîne améliore la localité de référence. Bien sûr, avec l'optimisation des chaînes courtes, cela devient encore plus complexe - Lhs [0] peut être sur le tas alors que Rhs [0] est sur la pile.