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

Question

He visto el segundo en el código de otro y supongo que esta comparación de longitud se ha hecho para aumentar la productividad del código. Se usó en un analizador sintáctico para un lenguaje de script con un diccionario específico: las palabras son de 4 a 24 letras de largo con un promedio de 7-8 letras, el alfabeto incluye 26 letras latinas más '' @ '', '' $ '' y '' _ ''.

La comparación de longitud se utilizó para escapar == operador que trabaja con cadenas STL, lo que obviamente lleva más tiempo que la comparación de enteros simples. Pero al mismo tiempo, la distribución de la primera letra en el diccionario dado es simplemente más amplia que una distribución del tamaño de las palabras, por lo que dos primeras letras de cadenas de comparación serán generalmente más diferentes que los tamaños de esas cadenas. Eso hace innecesaria la comparación de longitud.

He realizado algunas pruebas y eso es lo que he descubierto: al probar dos comparaciones de cadenas aleatorias millones de veces, la segunda forma es mucho más rápida, por lo que la comparación de longitud parece ser útil. Pero en un proyecto en funcionamiento funciona aún más lento en un modo de depuración e insuficientemente más rápido en un modo de lanzamiento.

Entonces, mi pregunta es: ¿por qué la comparación de longitud puede ajustar la comparación y por qué puede ralentizarla?

UPD: Tampoco me gusta esa segunda forma, pero supongo que se hizo por una razón, y me pregunto, ¿cuál es esta razón?

UPD2: En serio, la pregunta no es cómo hacerlo mejor. Ya ni siquiera estoy usando cadenas STL en este caso. No es de extrañar que la comparación de longitud sea innecesaria e incorrecta, etc. La maravilla es que realmente tiende a funcionar un poco mejor en una prueba determinada. ¿Cómo es esto posible?

Answer 1

En su prueba aleatoria, las cadenas podrían haber sido lo suficientemente largas como para mostrar la ganancia, mientras que en su caso real puede tratar cadenas más cortas y el factor constante de comparación dos no se compensa con ninguna ganancia al no realizar la parte de comparación de cadenas de la prueba.

Answer 2

Si importaba, suponga que su biblioteca ya lo hizo. No estropee su código de esta manera para micro optimizaciones a menos que realmente importe.

Answer 3

¿Cuándo puede ser beneficioso el cortocircuito?

Las optimizaciones de cortocircuito pueden ser útiles solo cuando:

• el costo de comparación es bajo en comparación con el costo de la prueba completa
• la comparación a menudo resulta en cortocircuito

Matemáticamente, supongamos que S es el costo de la condición de Cortocircuito, F el costo de la condición completa y P el porcentaje de casos en los que ocurre un Cortocircuito (no es necesaria la condición completa).

El costo promedio de la carcasa original (sin cortocircuito) es F

El costo promedio de la optimización de cortocircuito es S + F * (1-P)

Por lo tanto, si la optimización tiene algún beneficio, debe aplicarse lo siguiente:

S + F * (1-P) < F

es decir

S < F * P

Costo de comparación de cadenas

Además escribiste:

que obviamente lleva más tiempo que la simple comparación de enteros.

Esto no es obvio en absoluto. La comparación de cadenas termina cuando se encuentra la primera diferencia, por lo tanto, dependiendo de las cadenas que procese, puede terminar en el primer o segundo carácter en la gran mayoría de los casos. Además, la comparación puede optimizarse incluso para cadenas más largas comparando primero DWORDS (4 caracteres a la vez) siempre que haya suficientes datos en ambas cadenas.

Tu caso

La principal diferencia entre los datos de prueba aleatorios y el análisis de secuencias de comandos es que los datos reales están lejos de ser aleatorios. Es muy probable que el analizador sea determinista, y una vez que coincide, ya no se compara. Incluso los datos del script no son aleatorios: es probable que algunas palabras clave se usen mucho más que otras. Si el analizador está construido de tal manera que primero verifica la palabra clave más comúnmente utilizada, un número sorprendentemente alto de comparaciones puede necesitar la comparación completa, ya que la comparación completa siempre debe realizarse cuando las cadenas coinciden.

Answer 4

Generalmente, debe dejar esto al STL y no preocuparse por eso.

Sin embargo, si ESTE es un área que necesita optimizar (lo cual dudo seriamente), Y si comprende la distribución de letras / longitud de sus cadenas, podría derivar una nueva clase de la cadena y sobrecargar el operador == para realizar la prueba de igualdad de la manera más eficiente para su aplicación. (Longitud primero, primer carácter primero, adelante, atrás, lo que sea).

Eso sería mejor que tener la 'optimización' dispersa en todo el código.

Answer 5

La implementación del operador std :: string == no tiene forma de saber si sería más rápido verificar primero la longitud o comenzar a verificar los caracteres. Comprobar claramente la longitud es un desperdicio para cadenas de la misma longitud. Por lo tanto, es probable que diferentes implementaciones de STL funcionen de manera diferente.

Solo coloque la verificación de longitud explícita como una optimización final (claramente comentada como tal), y solo si su generador de perfiles confirma el beneficio.

Answer 6

la comparación de longitud no tiene ningún sentido para mí ... usar el operador de comparación es suficiente

Answer 7

dispare su implementación de STL. No debería importar

Answer 8

La comparación de longitud está ahí para probar una optimización de cortocircuito.

Supongo que la comparación de longitud es más rápida que la comparación de cadena completa, por lo que si eso puede eliminar el 99% de las discrepancias, será más rápido que hacer la comparación de cadena completa cada vez.

El código ejecutará la comparación de longitud, fallará, luego ignorará la comparación de cadena completa y omitirá el código.

Answer 9

La longitud de la cadena std :: es muy probable que sea un miembro del objeto std :: string. En comparación, el primer personaje bien podría estar en el montón. Eso significa que comparar la longitud de la cadena mejora la localidad de referencia. Por supuesto, con la optimización de cadena corta esto se vuelve aún más complejo: Lhs [0] podría estar en el montón mientras Rhs [0] está en la pila.