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

Question

Ne ho visto il secondo nel codice di un altro e suppongo che questo confronto di lunghezza sia stato fatto per aumentare la produttività del codice. È stato usato in un parser per un linguaggio di script con un dizionario specifico: le parole sono lunghe da 4 a 24 lettere con una media di 7-8 lettere, l'alfabeto include 26 lettere latine più "@", "& $;"; e " _ " ;.

Il confronto di lunghezza è stato usato per sfuggire all'operatore == che lavora con stringhe STL, il che ovviamente richiede più tempo del semplice confronto di numeri interi. Ma allo stesso tempo la distribuzione della prima lettera nel dizionario dato è semplicemente più ampia di una distribuzione della dimensione delle parole, quindi due prime lettere di stringhe di confronto saranno generalmente più spesso diverse rispetto alle dimensioni di quelle stringhe. Ciò rende superfluo il confronto delle lunghezze.

Ho eseguito alcuni test ed è quello che ho scoperto: durante il test due milioni di stringhe casuali di confronto, la seconda via è molto più veloce, quindi il confronto della lunghezza sembra essere utile. Ma in un progetto di lavoro funziona ancora più lentamente in una modalità di debug e in modo insufficientemente più veloce in una modalità di rilascio.

Quindi, la mia domanda è: perché il confronto di lunghezza può accelerare il confronto e perché può rallentarlo?

UPD: Non mi piace neanche quel secondo modo, ma era stato fatto per un motivo, suppongo, e mi chiedo, qual è questo motivo.

UPD2: Seriamente, la domanda non è come fare meglio. In questo caso non sto nemmeno più usando le stringhe STL. Non c'è da meravigliarsi che il confronto della lunghezza non sia necessario e sbagliato, ecc. La meraviglia è che tende davvero a funzionare leggermente meglio in un determinato test. Come è possibile?

Answer 1

Nel tuo test casuale le stringhe potrebbero essere state abbastanza lunghe da mostrare il guadagno mentre nel tuo caso reale potresti avere a che fare con stringhe più brevi e il fattore costante di due confronti non è compensato da alcun guadagno nel non eseguire la parte di confronto delle stringhe di il test.

Answer 2

Se ha importanza, supponi che la tua libreria lo abbia già fatto. Non confondere il tuo codice in questo modo per le micro-ottimizzazioni a meno che non contino davvero.

Answer 3

Quando può essere utile il corto circuito

Le ottimizzazioni del corto circuito possono essere utili solo quando:

• il costo del confronto è basso rispetto al costo dell'intero test
• il confronto si traduce spesso in corto circuito

Matematicamente, sia S il costo della condizione di Corto circuito, il costo F della condizione piena e P sia la percentuale dei casi in cui si verifica Cortocircuito (la condizione piena non è necessaria).

Il costo medio del caso originale (nessun corto circuito) è F

Il costo medio dell'ottimizzazione del corto circuito è S + F * (1-P)

Pertanto, se l'ottimizzazione deve avere qualche vantaggio, è necessario applicare quanto segue:

S + F * (1-P) < F

cioè.

S < F * P

Costo del confronto delle stringhe

Inoltre hai scritto:

che ovviamente richiede più tempo del semplice confronto di interi.

Questo non è affatto ovvio. Il confronto delle stringhe termina quando viene rilevata la prima differenza, pertanto, a seconda delle stringhe elaborate, può terminare con il primo o il secondo carattere nella stragrande maggioranza dei casi. Inoltre, il confronto può essere ottimizzato anche per stringhe più lunghe confrontando prima DWORDS (4 caratteri contemporaneamente) purché vi siano dati sufficienti in entrambe le stringhe.

Il tuo caso

La principale differenza tra i dati di test casuali e l'analisi degli script è che i dati reali sono tutt'altro che casuali. Il parser è molto probabilmente deterministico e, una volta abbinato, non si confronta più. Anche i dati dello script non sono casuali: è probabile che alcune parole chiave vengano utilizzate molto più di altre. Se il parser è costruito in modo tale da controllare prima la parola chiave più comunemente usata, un numero sorprendentemente elevato di confronti potrebbe richiedere il confronto completo, poiché il confronto completo deve sempre essere eseguito quando la stringa corrisponde.

Answer 4

Generalmente, dovresti lasciarlo alla STL e non preoccuparti.

Tuttavia, se questa È un'area che devi ottimizzare (di cui dubito seriamente) E se comprendi la distribuzione delle lettere / la distribuzione della lunghezza delle tue stringhe, potresti ricavare una nuova classe dalla stringa e sovraccaricare l'operatore == per eseguire il test di uguaglianza nel modo più efficiente per la tua applicazione. (Lunghezza prima, primo carattere prima, avanti, indietro, qualunque cosa).

Sarebbe meglio che avere l'ottimizzazione sparsa in tutto il codice.

Answer 5

L'implementazione dell'operatore std :: string == non ha modo di sapere se sarebbe più veloce controllare prima la lunghezza o iniziare a controllare i caratteri. Chiaramente controllare la lunghezza è uno spreco per stringhe della stessa lunghezza. Pertanto, è probabile che diverse implementazioni di STL funzionino diversamente.

Inserisci il controllo esplicito della lunghezza come ottimizzazione finale (chiaramente commentato come tale) e solo se il tuo profiler conferma il vantaggio.

Answer 6

il confronto della lunghezza non ha alcun senso per me .. usare l'operatore di confronto è abbastanza

Answer 7

attiva la tua implementazione di STL. Non dovrebbe importare

Answer 8

Il confronto della lunghezza è lì per provare l'ottimizzazione del corto circuito.

Suppongo che il confronto della lunghezza sia più veloce rispetto al confronto completo della stringa, quindi se ciò può eliminare il 99% dei disallineamenti, sarà più veloce del confronto completo della stringa ogni volta.

Il codice eseguirà il confronto della lunghezza, fallirà, quindi ignorerà il confronto completo delle stringhe e salterà il codice.

Answer 9

La lunghezza dello std :: string è molto probabilmente un membro dell'oggetto std :: string. In confronto, il primo personaggio potrebbe benissimo essere sul mucchio. Ciò significa che il confronto della lunghezza della stringa migliora la località di riferimento. Naturalmente, con l'ottimizzazione delle stringhe corte questo diventa ancora più complesso - Lhs [0] potrebbe essere nell'heap mentre Rhs [0] è nello stack.