C++ utilizando limitadores precalculados en los bucles

Question

En lenguajes de programación como PHP tener un bucle como este sería una muy mala idea:

string s("ABCDEFG"); 
int i; 
for(i = 0; i < s.length(); i ++) 
{ 
    cout << s[ i ]; 
} 

Este es un ejemplo, no soy la construcción de un programa como este. (Para los chicos que se sienten como si tuvieran que dime por qué esta pieza de código < insertar malo de aquí>)

Si esto C ejemplo ++ fue traducido a un script PHP similar, la longitud de la cadena sería calculado cada ciclo de ciclo. Eso causaría una enorme pérdida de rendimiento en los scripts realistas.

Pensé que lo mismo se aplicaría a los programas de C++, pero cuando eché un vistazo a los tutoriales, varias bibliotecas de código abierto y otras partes de código, veo que el limitador del ciclo no se calcula previamente.

• ¿Debo precalcular la longitud de la cadena s?
• ¿Por qué el limitador no siempre se calcula previamente? (visto esto en tutoriales y ejemplos)
• ¿Hay algún tipo de optimización realizada por el compilador?

Answer 1

es todo relativo.

PHP se interpreta, pero si s.length gotas en una parte compilada del intérprete PHP, no será lento. Pero incluso si es lento, ¿qué pasa con el tiempo pasado en s[i], y ¿qué pasa con el tiempo pasado en cout <<?

Es muy fácil enfocarse en la cabeza del loop mientras se inunda con otras cosas.

Como si escribieras esto en C++, y cout estuvieses escribiendo en la consola, ¿sabes lo que dominaría? cout sería, de lejos, porque ese operador de apariencia inocente << invoca una enorme pila de código de la biblioteca y rutinas del sistema.

Answer 2

El optimizador puede de hecho ser capaz de optimizar la llamada a length de inmediato si él es capaz de determinar que su valor no cambiará - sin embargo, estás en el lado seguro si precalcular ella (en muchos casos, sin embargo, la optimización no será posible porque no está claro para el compilador si la variable de condición podría cambiarse durante el ciclo).

En muchos casos, simplemente no importa porque el bucle en cuestión no es relevante para el rendimiento. Usar el clásico for(int i=0; i < somewhat(); ++i) es menos laborioso de escribir y más fácil de leer que for(int i=0,end=somewhat(); i < end; ++i.

Tenga en cuenta que el compilador de C++ usualmente incluirá pequeñas funciones, como length (que normalmente recuperaría una longitud precalculada del objeto de cadena). Los lenguajes de scripting interpretados generalmente necesitan una búsqueda de diccionario para una llamada de función, por lo que para C++ la sobrecarga relativa de la verificación redundante una vez por iteración de bucle es probablemente mucho menor.

Answer 3

1. Probablemente.
2. Para lectura.
3. A veces. Depende de cuán bueno es detectar que la longitud no cambiará dentro del ciclo.

Answer 4

Bueno, ya que este es un escenario muy común, la mayoría de los compiladores precalcularán el valor. Especialmente cuando se realiza un bucle a través de matrices y tipos muy comunes, la cadena podría ser una de ellas.

Además, la introducción de una variable adicional podría destruir algunas otras optimizaciones de bucle: realmente depende del compilador que utilice y podría cambiar de una versión a otra.
Por lo tanto, en algunos casos, la "optimización" podría ser contraproducente.

Si el código no es un "punto caliente" real donde cada tic del rendimiento sí importa, debe escribirlo como lo hizo: Sin precalculación "manual".

¡La legibilidad también es muy importante al escribir el código!
¡Las optimizaciones deben hacerse con mucho cuidado y solo después de un perfil intensivo!

Answer 5

Está en lo cierto, s.length() normalmente se evaluará en cada iteración de bucle. Es mejor que escriba:

size_t len = s.length(); 
for (size_t i = 0; i < len; ++i) { 
    ... 
} 

En lugar de lo anterior. Dicho esto, para un ciclo con solo algunas iteraciones, realmente no importa la frecuencia con la que se realizará la llamada a length().

Answer 6

std::string.length() devuelve una variable fija, que se almacena en el contenedor. Ya se calculan previamente

Answer 7

Se podría precalcular la longitud de la cuerda sólo si SABE la cadena siempre no va a cambiar dentro del bucle.

No sé por qué se hace así en los tutoriales. Algunas conjeturas:
1) Para acostumbrarte a la práctica, así no te mancharán cuando cambies el valor de la cuerda dentro del ciclo.
2) Porque es más fácil de entender.

Sí, el optimizador intentará mejorar esto, si se puede determinar si la cadena no va a cambiar

Answer 8

Depende de cómo se implementa el string.

En cadenas con terminación nula, debe calcular el tamaño en cada iteración.

std::string es un contenedor y el tamaño debería ser devueltos en O (1) el tiempo,
que depende (de nuevo) sobre la aplicación.

Answer 9

Respuesta breve, porque hay situaciones en las que desea que se le llame cada vez. La explicación de

otra persona: http://bytes.com/topic/c/answers/212351-loop-condition-evaluation

Answer 10

El compilador puede ser capaz de guardar el resultado de la llamada y optimizar la distancia todas las llamadas a funciones adicionales, pero puede que no. Sin embargo, el costo de la llamada a la función será bastante bajo ya que todo lo que tiene que hacer es devolver un int. Además de eso, hay una buena posibilidad de que esté en línea, eliminando el costo de la llamada de función por completo.

Sin embargo, si realmente le importa, debe perfilar su código y ver si el cálculo previo del valor lo hace más rápido. Pero no estaría de más elegir simplemente precalcularlo de todos modos. No le costará nada. Sin embargo, en la mayoría de los casos, las probabilidades son que no importe. Hay algunos contenedores, como la lista, donde size() podría no ser una operación O (1) y, a continuación, precalcular sería una buena idea realmente, pero para la mayoría probablemente no importe demasiado, especialmente si el contenido de su ciclo es suficiente para abrumar el costo de una llamada a función tan eficiente. Para std :: string, debería ser O (1), y será probablemente optimizado, pero tendrías que probar para estar seguro - y por supuesto cosas como el nivel de optimización que compilas podrían cambiar los resultados .

Es más seguro precalcular pero a menudo no es necesario.

Answer 11

En este caso particular, std::string.length() es generalmente (pero no necessarily) una operación de tiempo constante y generalmente bastante eficiente.

Para el caso general, la condición de terminación de bucle puede ser cualquier expresión, no solo una comparación de la variable de índice de bucle (de hecho, C/C++ no reconoce ningún índice en particular, solo una expresión de inicializador, una expresión de prueba de bucle y una expresión contador de bucle (que acaba se ejecuta cada vez a través). El C/C++ para el bucle es básicamente azúcar sintáctico para una declaración do/while compuesto.

Answer 12

std::sting::length() devuelve un valor precalculado. Otros contenedores STL volver a calcular su tamaño cada vez que se llama al método size() por ejemplo

• std::list::size() vuelve a calcular el tamaño y
• std::vector::size() devuelve un valor precalculado

Depende de cómo el almacenamiento interno de la contenedor está implementado. std::vector es una matriz con capacidad 2^ny std::list es una lista vinculada.

Answer 13

Debería aprender a justificar un código más simple. Intente convencerse de que tarde o temprano reemplazará la implementación de string :: length por una más optimizada. (Aunque es probable que su proyecto pierda todos los plazos, y la optimización de la longitud de la cadena será el menor de sus problemas). Este tipo de pensamiento lo ayudará a enfocarse en las cosas que realmente importan, aunque no siempre es fácil ...

Answer 14

Solo para información, en mi computadora, g ++ 4.4.2, con -O3, con el fragmento de código dado, la función std::string::length() const se llama 8 veces.

Acepto que se calculó previamente y es muy probable que la función esté en línea. Aún es muy interesante saber cuándo estás usando tus propias funciones/clase.

Answer 15

Si su programa realiza muchas operaciones en cadenas todo el tiempo como copiar cadenas (con memcpy), entonces tiene sentido almacenar en caché la longitud de la cadena.

Un buen ejemplo de esto que he visto en el código de código abierto es redis.

En sds.h (Simple dinámica Cuerdas) vistazo a la estructura sdshdr:

struct sdshdr { 
    long len; 
    long free; 
    char buf[]; 
}; 

Como se puede ver que almacena en caché la longitud (en len campo) de la matriz de caracteres buf y también el espacio libre disponible (en campo libre) después del carácter nulo.

Así que la memoria total asignada a buf es

len + free 

Esto ahorra un realloc en caso de que el buf necesita ser modificado y que encaja en el espacio ya disponible.

Answer 16

No sé php pero puedo decir lo que c++ hace. Considere:

std::string s("Rajendra"); 
for (unsigned int i = 0; i < s.length(); i++) 
{ 
    std::cout << s[i] << std::endl; 
} 

Si vas para levantar la definición de length() (clic derecho en length() y haga clic en "Ir a definición") o si está utilizando Visual Assist X a continuación, colocar el cursor en length() y pulse Alt+G , se dará cuenta de lo siguiente:

size_type __CLR_OR_THIS_CALL length() const 
    { // return length of sequence 
    return (_Mysize); 
    } 

Dónde _Mysize es de tipo int, que revela claramente que la longitud de la cadena es calculada de antemano y sólo valor almacenado se está volviendo cada llamada a length().

Sin embargo, IMPO (en mi opinión personal), este estilo de codificación es malo y debería evitarse. Yo preferiría siguiente:

std::string s("Rajendra"); 
int len = s.length(); 
for (unsigned int i = 0; i < len; i++) 
{ 
    std::cout << s[i] << std::endl; 
} 

esta manera, se ahorrará la sobrecarga de llamar length() función igual a la longitud del número de serie de veces, lo que ahorra empujando y haciendo estallar del marco de pila. Esto puede ser muy costoso cuando su cadena es grande.
Espero que ayude.