¿Por qué la comparación de enteros es más rápida que la comparsión de cadenas?

Encontré comentarios sobre cómo evitar cadenas para la comparación de valores (especialmente en loops) en algunos libros porque la comparación de cadenas es mucho más lenta (usando std :: string). Pero, ¿por qué exactamente es eso?¿Por qué la comparación de enteros es más rápida que la comparsión de cadenas?

¿Se debe a que las unidades enteras de la CPU funcionan más rápido?

Las cadenas deberían estar en byte, supongo, ¿así que una comparación de bytes no haría el trabajo por igual?

Gracias!

Fuente

2011-02-05 MisterQuestion

Con un número entero, existen instrucciones en el nivel de la máquina que pueden realizar una comparación en un ciclo.

Una cadena, sin embargo, consta de una gran cantidad de caracteres. Para comparar cadenas, usted, en el peor de los casos, tiene que ver cada carácter de las cuerdas.

De hecho, cuando compara cadenas, lo más probable es que utilice una comparación de números enteros para cada carácter de la cadena. Probablemente pueda ver cómo esto rápidamente puede convertirse en una gran cantidad de comparaciones en comparación con la comparación de dos enteros.

Ejemplo: Si se quiere comparar con 1073741822 1073741823.

comparación de cadenas: Hay que comparar cada uno de los dígitos uno por uno. Esto es 10 comparaciones, ya que los enteros solo difieren en el último dígito.
comparación de enteros: puede hacer esto en una comparación, guardando 9 comparaciones en comparación con la comparación de cadenas.

Esto es un poco simplificado, naturalmente, pero con suerte lo explica todo.

Fuente

2011-02-05 00:16:20

Actualmente dos comparaciones por personaje (frente a la otra cadena, y contra NUL para cadenas terminadas, o contra la longitud para cadenas contadas). Pero SSE puede realizar 16 de esas comparaciones en el tiempo de una comparación de enteros. –

@Voigt: Olvidé la comparación '\ 0', pero sí, creo que lo dejo así. No quiero ser demasiado específico y perder el panorama general. :) –

El problema es que una comparación de cadenas no es solo una comparación, es una secuencia completa de ellas en un ciclo. ¿Qué espera que suceda si compara dos cadenas de 10001 caracteres cada una y las primeras 9000 son iguales?

BTW SSE hace que la cadena se compare MUCHO más rápido que con un carácter a la vez, pero nunca puede alcanzar la velocidad de una comparación de enteros.

Fuente

2011-02-05 00:15:28

... mientras que las comparaciones int se pueden hacer en _significativamente_ menos instrucciones. –

El compilador puede optimizar las comparaciones de enteros para que ocurran directamente dentro de los registros de la CPU.

Fuente

2011-02-05 00:16:50

Hablando de forma vaga, la comparación de cadenas requiere n número de comparaciones enteras donde n es el tamaño de la cadena, mientras que la comparación entera es solo una comparación si se piensa en relación. ¡Es una idea aproximada de lo que podría estar pasando al comparar cadenas!

Así que, obviamente, la comparación de cadenas sería un proceso más lento, ya que es n número de comparaciones enteras (aprox.).

Fuente

2011-02-05 00:18:08 Nawaz

'strlen + 1' es un límite superior, y cuando tienes una unidad SIMD se necesitarán menos comparaciones. Sin embargo, es O (N). –

Entero son generalmente -bytes.

Cuerdas son en cualquier lugar entre y infinito * bytes.

* Oye, entiendes lo que quiero decir, ¿no?

Fuente

2011-02-05 00:26:24

¿Por qué la comparación de enteros es más rápida que la comparsión de cadenas?

Respuesta

Cuestiones relacionadas