numeros - Cadenas concatenadas en C, ¿qué método es más eficiente?
operaciones con cadenas en c (10)
Aquí hay algo de locura para ti, de hecho fui y lo medí. Maldita sea, imagina eso. Creo que obtuve algunos resultados significativos.
Utilicé un P4 dual core, ejecutando Windows, usando mingw gcc 4.4, construyendo con "gcc foo.c -o foo.exe -std = c99 -Wall -O2".
Probé el método 1 y el método 2 desde la publicación original. Inicialmente mantuve el malloc fuera del ciclo de referencia. El Método 1 fue 48 veces más rápido que el Método 2. Curiosamente, la eliminación de -O2 del comando de compilación hizo que el exe resultante fuera un 30% más rápido (aún no se ha investigado por qué).
Luego agregué un malloc y lo liberé dentro del ciclo. Eso ralentizó el método 1 por un factor de 4.4. El método 2 se ralentizó por un factor de 1.1.
Entonces, malloc + strlen + free NO domina el perfil lo suficiente como para evitar el sprintf.
Aquí está el código que utilicé (aparte de los bucles que se implementaron con <en lugar de! = Pero que rompieron la representación en HTML de esta publicación):
void a(char *first, char *second, char *both)
{
for (int i = 0; i != 1000000 * 48; i++)
{
strcpy(both, first);
strcat(both, " ");
strcat(both, second);
}
}
void b(char *first, char *second, char *both)
{
for (int i = 0; i != 1000000 * 1; i++)
sprintf(both, "%s %s", first, second);
}
int main(void)
{
char* first= "First";
char* second = "Second";
char* both = (char*) malloc((strlen(first) + strlen(second) + 2) * sizeof(char));
// Takes 3.7 sec with optimisations, 2.7 sec WITHOUT optimisations!
a(first, second, both);
// Takes 3.7 sec with or without optimisations
//b(first, second, both);
return 0;
}
Encontré estos dos métodos para concatenar cadenas:
Parte comun:
char* first= "First";
char* second = "Second";
char* both = malloc(strlen(first) + strlen(second) + 2);
Método 1:
strcpy(both, first);
strcat(both, " "); // or space could have been part of one of the strings
strcat(both, second);
Método 2:
sprintf(both, "%s %s", first, second);
En ambos casos, el contenido de both sería "First Second" .
Me gustaría saber cuál es más eficiente (tengo que realizar varias operaciones de concatenación), o si conoces una mejor manera de hacerlo.
Deberían ser más o menos lo mismo. La diferencia no va a importar. Me gustaría ir con sprintf ya que requiere menos código.
La diferencia es poco probable que importe:
- Si tus cadenas son pequeñas, el malloc ahogará las concatenaciones de cadenas.
- Si sus cadenas son grandes, el tiempo que dedique a copiar los datos ahogará las diferencias entre strcat / sprintf .
Como otros carteles han mencionado, esta es una optimización prematura. Concéntrese en el diseño del algoritmo, y solo regrese a esto si el perfil muestra que es un problema de rendimiento.
Dicho eso ... sospecho que el método 1 será más rápido. Hay algunos --- ciertamente pequeños --- sobrecarga para analizar la cadena de formato sprintf . Y strcat es más probable "en línea".
Ninguno es terriblemente eficiente ya que ambos métodos tienen que calcular la longitud de la cadena o escanearla cada vez. En cambio, dado que calcula los strlen () s de las cadenas individuales de todos modos, póngalos en variables y luego simplemente strncpy () dos veces.
No sé si en el caso dos hay una concatenación real. Imprimirlos espalda con espalda no constituye concatenación.
Sin embargo, dime, que sería más rápido:
1) a) copie la cadena A en el nuevo buffer b) copie la cadena B en el buffer c) copie el buffer en el buffer de salida
o
1) copie la cadena A al buffer de salida b) copie la cadena b al buffer de salida
No se preocupe por la eficiencia: haga que su código sea legible y mantenible. Dudo que la diferencia entre estos métodos sea importante en su programa.
Para la legibilidad, yo iría con
char * s = malloc(snprintf(NULL, 0, "%s %s", first, second) + 1);
sprintf(s, "%s %s", first, second);
Si su plataforma admite extensiones de GNU, también puede usar asprintf() :
char * s = NULL;
asprintf(&s, "%s %s", first, second);
Si está atascado con MS C Runtime, debe usar _scprintf() para determinar la longitud de la cadena resultante:
char * s = malloc(_scprintf("%s %s", first, second) + 1);
sprintf(s, "%s %s", first, second);
Lo siguiente probablemente sea la solución más rápida:
size_t len1 = strlen(first);
size_t len2 = strlen(second);
char * s = malloc(len1 + len2 + 2);
memcpy(s, first, len1);
s[len1] = '' '';
memcpy(s + len1 + 1, second, len2 + 1); // includes terminating null
sprintf () está diseñado para manejar mucho más que solo cadenas, strcat () es especialista. Pero sospecho que estás sudando las cosas pequeñas. Las cadenas C son fundamentalmente ineficientes de manera que hacen que las diferencias entre estos dos métodos propuestos sean insignificantes. Lea "Volver a lo básico" de Joel Spolsky para conocer los detalles sangrientos.
Esta es una instancia en la que C ++ generalmente tiene un mejor rendimiento que C. Para el manejo de cadenas de peso pesado, usar std :: string es probable que sea más eficiente y ciertamente más seguro.
[editar]
[2da edición] Código corregido (demasiadas iteraciones en la implementación de cadenas C), los tiempos y la conclusión cambian en consecuencia
Me sorprendió el comentario de Andrew Bainbridge de que std :: string fue más lento, pero no publicó el código completo para este caso de prueba. Modifiqué el suyo (automatizando el tiempo) y agregué una prueba std :: string. La prueba fue en VC ++ 2008 (código nativo) con opciones predeterminadas de "Release" (es decir, optimizadas), Athlon dual core, 2.6GHz. Resultados:
C string handling = 0.023000 seconds
sprintf = 0.313000 seconds
std::string = 0.500000 seconds
Así que aquí strcat () es mucho más rápido (su kilometraje puede variar según el compilador y las opciones), a pesar de la ineficacia inherente de la convención de cadenas C, y admite mi sugerencia original de que sprintf () lleva una gran cantidad de equipaje no requerido para este propósito . Sin embargo, sigue siendo el menos legible y seguro, por lo que cuando el rendimiento no es crítico, tiene poco mérito IMO.
También probé una implementación std :: stringstream, que fue mucho más lenta de nuevo, pero para el formato de cadenas complejas aún tiene mérito.
El código corregido sigue:
#include <ctime>
#include <cstdio>
#include <cstring>
#include <string>
void a(char *first, char *second, char *both)
{
for (int i = 0; i != 1000000; i++)
{
strcpy(both, first);
strcat(both, " ");
strcat(both, second);
}
}
void b(char *first, char *second, char *both)
{
for (int i = 0; i != 1000000; i++)
sprintf(both, "%s %s", first, second);
}
void c(char *first, char *second, char *both)
{
std::string first_s(first) ;
std::string second_s(second) ;
std::string both_s(second) ;
for (int i = 0; i != 1000000; i++)
both_s = first_s + " " + second_s ;
}
int main(void)
{
char* first= "First";
char* second = "Second";
char* both = (char*) malloc((strlen(first) + strlen(second) + 2) * sizeof(char));
clock_t start ;
start = clock() ;
a(first, second, both);
printf( "C string handling = %f seconds/n", (float)(clock() - start)/CLOCKS_PER_SEC) ;
start = clock() ;
b(first, second, both);
printf( "sprintf = %f seconds/n", (float)(clock() - start)/CLOCKS_PER_SEC) ;
start = clock() ;
c(first, second, both);
printf( "std::string = %f seconds/n", (float)(clock() - start)/CLOCKS_PER_SEC) ;
return 0;
}
size_t lf = strlen(first);
size_t ls = strlen(second);
char *both = (char*) malloc((lf + ls + 2) * sizeof(char));
strcpy(both, first);
both[lf] = '' '';
strcpy(&both[lf+1], second);
- strcpy y strcat son opraciones mucho más simples en comparación con sprintf, que necesita analizar la cadena de formato
- strcpy y strcat son pequeños, por lo que los compiladores los incluirán en general, ahorrando incluso una sobrecarga de llamada de función adicional. Por ejemplo, en llvm strcat se marcará usando un strlen para encontrar la posición de inicio de la copia, seguido de una simple instrucción de tienda