c++ - leer - string en c
Usar scanf() en programas C++ es más rápido que usar cin? (13)
Acabo de pasar una tarde trabajando en un problema en UVa Online (Factovisors, un problema muy interesante, compruébalo):
Estaba obteniendo TLE (límite de tiempo excedido) en mis envíos. En estos sitios de jueces en línea para la resolución de problemas, tiene un límite de tiempo de 2-3 segundos para manejar potencialmente miles de casos de prueba utilizados para evaluar su solución. Para problemas computacionalmente intensivos como este, cada microsegundo cuenta.
Estaba usando el algoritmo sugerido (leí en los foros de discusión del sitio), pero aún obtenía TLE.
Cambié simplemente "cin >> n >> m" a "scanf ("% d% d ", & n, & m)" y los pocos pequeños "couts" a "printfs", ¡y mi TLE se convirtió en "Aceptado"!
Entonces, sí, puede hacer una gran diferencia, especialmente cuando los límites de tiempo son cortos.
No sé si esto es cierto, pero cuando estaba leyendo las preguntas frecuentes en uno de los sitios que proporcionaban problemas, encontré algo que llamó mi atención:
Verifica tus métodos de entrada / salida. En C ++, usar cin y cout es demasiado lento. Úselos, y garantizará que no podrá resolver ningún problema con una cantidad decente de entrada o salida. Use printf y scanf en su lugar.
¿Alguien puede aclarar esto? ¿Realmente está usando scanf () en programas C ++ más rápido que usando cin >> algo ? Si es así, ¿es una buena práctica usarlo en programas C ++? Pensé que era C específico, aunque solo estoy aprendiendo C ++ ...
Aquí hay una prueba rápida de un caso simple: un programa para leer una lista de números de entrada estándar y XOR todos los números.
Versión iostream:
#include <iostream>
int main(int argc, char **argv) {
int parity = 0;
int x;
while (std::cin >> x)
parity ^= x;
std::cout << parity << std::endl;
return 0;
}
versión de scanf:
#include <stdio.h>
int main(int argc, char **argv) {
int parity = 0;
int x;
while (1 == scanf("%d", &x))
parity ^= x;
printf("%d/n", parity);
return 0;
}
Resultados
Usando un tercer programa, genere un archivo de texto que contiene 33,280,276 números aleatorios. Los tiempos de ejecución son:
iostream version: 24.3 seconds
scanf version: 6.4 seconds
Cambiar la configuración de optimización del compilador no pareció cambiar los resultados en absoluto.
Por lo tanto: realmente hay una diferencia de velocidad.
EDITAR: El usuario clyfish señala a continuación que la diferencia de velocidad se debe principalmente a las funciones de E / S de iostream que mantienen la sincronización con las funciones de CI / O. Podemos desactivar esto con una llamada a std::ios::sync_with_stdio(false); :
#include <iostream>
int main(int argc, char **argv) {
int parity = 0;
int x;
std::ios::sync_with_stdio(false);
while (std::cin >> x)
parity ^= x;
std::cout << parity << std::endl;
return 0;
}
Nuevos resultados:
iostream version: 21.9 seconds
scanf version: 6.8 seconds
iostream with sync_with_stdio(false): 5.5 seconds
C ++ iostream gana! Resulta que esta sincronización / descarga interna es lo que normalmente ralentiza iostream i / o. Si no estamos mezclando cstdio y iostream, podemos desactivarlo, y luego iostream es el más rápido.
El código: https://gist.github.com/3845568
El problema es que cin tiene una gran cantidad de gastos generales involucrados porque le da una capa de abstracción sobre las llamadas scanf() . No debe usar scanf() sobre cin si está escribiendo software C ++ porque quiere que cin sea para. Si desea rendimiento, probablemente no estaría escribiendo E / S en C ++ de todos modos.
Existen implementaciones de stdio ( libio ) que implementan FILE * como streambuf de C ++ y fprintf como analizador de formato de tiempo de ejecución. IOstreams no necesita un análisis de formato de tiempo de ejecución, todo se hace en tiempo de compilación. Entonces, con los backends compartidos, es razonable esperar que iostreams sea más rápido en tiempo de ejecución.
Guau, habla de optimización prematura. Si no es una optimización ridícula. E / S va a embotellar su programa mucho antes de que cin >> x maximice su CPU de cuatro núcleos.
OK, despreocupación: No, no es una buena práctica cambiar <iostream> por <cstdio> . Cuando esté en C ++, use las bibliotecas C ++. No use scanf , no llame a malloc , no pase, no cobre $ 200.
Incluso si scanf fuera más rápido que cin , no importaría. La gran mayoría de las veces, leerá desde el disco duro o el teclado. Obtener los datos brutos en su aplicación lleva órdenes de magnitud más tiempo de lo que tarda scanf o cin para procesarlo.
Las afirmaciones cin y cout en general parecen ser más lentas que scanf y printf en C ++, ¡pero en realidad son MÁS RÁPIDAS!
La cosa es: en C ++, cada vez que utiliza cin y cout , se lleva a cabo un proceso de sincronización de forma predeterminada que garantiza que si usa scanf y cin en su programa, ambos trabajan sincronizados entre sí. Este proceso de sincronización lleva tiempo. Por lo tanto, cin y cout parecen ser más lentos.
Sin embargo, si el proceso de sincronización está configurado para que no ocurra, cin es más rápido que scanf .
Para omitir el proceso de sincronización, incluya el siguiente fragmento de código en su programa justo al principio de main() :
std::ios::sync_with_stdio(false);
Visite este sitio para más información.
Por supuesto, es ridículo usar cstdio sobre iostream. Al menos cuando desarrolles un software (si ya estás usando c ++ sobre c, entonces usa todo el tiempo y usa sus beneficios en lugar de solo sufrir sus desventajas).
Pero en el juez en línea no está desarrollando software, está creando un programa que debería poder hacer cosas. ¡El software de Microsoft tarda 60 segundos en alcanzarse en 3 segundos!
Entonces, en este caso, la regla de oro es como (por supuesto, si no te metes en más problemas al usar java)
- Usa c ++ y usa todo su poder (y pesadez / lentitud) para resolver el problema
- Si obtienes un límite de tiempo, cambia las cins y couts por printfs y scanfs (si te equivocas al usar la cadena de clases, imprime así: printf (% s, mystr.c_str ());
- Si todavía tiene tiempo limitado, intente hacer algunas optimizaciones obvias (como evitar demasiadas funciones embebidas para / while / dowhiles o recursivas). También asegúrese de pasar por objetos de referencia que son demasiado grandes ...
- Si aún tiene tiempo limitado, intente cambiar std :: vectores y conjuntos para c-arrays.
- Si todavía tienes tiempo limitado, entonces pasa al siguiente problema ...
Probablemente scanf es algo más rápido que usar streams. Aunque los flujos proporcionan mucha seguridad de tipo, y no tienen que analizar cadenas de formato en tiempo de ejecución, generalmente tienen la ventaja de no requerir asignaciones de memoria excesivas (esto depende de su compilador y tiempo de ejecución). Dicho esto, a menos que el rendimiento sea tu único objetivo final y te encuentres en el camino crítico, entonces realmente deberías favorecer los métodos más seguros (más lentos).
Hay un artículo muy delicioso escrito aquí por Herb Sutter " The String Formatters of Manor Farm " que detalla mucho el rendimiento de los formateadores de cadenas como sscanf y lexical_cast y qué tipo de cosas los hacían funcionar lenta o rápidamente. Esto es algo similar, probablemente al tipo de cosas que afectarían el rendimiento entre el estilo C IO y el estilo C ++. La principal diferencia con los formateadores tendía a ser el tipo de seguridad y el número de asignaciones de memoria.
Sí iostream es más lento que cstdio.
Sí, probablemente no deberías usar cstdio si estás desarrollando en C ++.
Habiendo dicho eso, hay maneras incluso más rápidas de obtener E / S que scanf si no te importa formatear, escribe seguridad, bla, bla, bla ...
Por ejemplo, esta es una rutina personalizada para obtener un número de STDIN:
inline int get_number()
{
int c;
int n = 0;
while ((c = getchar_unlocked()) >= ''0'' && c <= ''9'')
{
// n = 10 * n + (c - ''0'');
n = (n << 3) + ( n << 1 ) + c - ''0'';
}
return n;
}
Si le interesan tanto el rendimiento como el formato de cadenas, eche un vistazo a la biblioteca FastFormat de Matthew Wilson .
edit - enlace a la publicación Accu en esa biblioteca: http://accu.org/index.php/journals/1539
http://www.quora.com/Is-cin-cout-slower-than-scanf-printf/answer/Aditya-Vishwakarma
El rendimiento de cin / cout puede ser lento porque necesitan mantenerse sincronizados con la biblioteca C subyacente. Esto es esencial si se van a usar tanto C IO como C ++ IO.
Sin embargo, si solo va a usar C ++ IO, simplemente use la línea a continuación antes de cualquier operación IO
std::ios::sync_with_stdio(false);
Para obtener más información sobre esto, consulte los documentos libstdc ++ en este: http://gcc.gnu.org/onlinedocs/libstdc++/manual/io_and_c.html
#include <stdio.h>
#include <unistd.h>
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
static int scanuint(unsigned int* x)
{
char c;
*x = 0;
do
{
c = getchar_unlocked();
if (unlikely(c==EOF)) return 1;
} while(c<''0'' || c>''9'');
do
{
//*x = (*x<<3)+(*x<<1) + c - ''0'';
*x = 10 * (*x) + c - ''0'';
c = getchar_unlocked();
if (unlikely(c==EOF)) return 1;
} while ((c>=''0'' && c<=''9''));
return 0;
}
int main(int argc, char **argv) {
int parity = 0;
unsigned int x;
while (1 != (scanuint(&x))) {
parity ^= x;
}
parity ^=x;
printf("%d/n", parity);
return 0;
}
Hay un error al final del archivo, pero este código C es dramáticamente más rápido que la versión más rápida de C ++.
paradox@scorpion 3845568-78602a3f95902f3f3ac63b6beecaa9719e28a6d6 ▶ make test
time ./xor-c < rand.txt
360589110
real 0m11,336s
user 0m11,157s
sys 0m0,179s
time ./xor2-c < rand.txt
360589110
real 0m2,104s
user 0m1,959s
sys 0m0,144s
time ./xor-cpp < rand.txt
360589110
real 0m29,948s
user 0m29,809s
sys 0m0,140s
time ./xor-cpp-noflush < rand.txt
360589110
real 0m7,604s
user 0m7,480s
sys 0m0,123s
El C ++ original tomó 30 segundos, el código C tomó 2 segundos.