resueltos - Gran diferencia(x9) en el tiempo de ejecución entre código casi idéntico en C y C++

estadistica elemental solucionario

Question

Intenté resolver este ejercicio desde www.spoj.com: FCTRL - Factorial

Realmente no tienes que leerlo, solo hazlo si tienes curiosidad :)

Primero lo implementé en C ++ (aquí está mi solución):

#include <iostream>
using namespace std;

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from https://stackoverflow.com/a/22225421/5218277)

    cin >> num_of_inputs;

    while (num_of_inputs--)
    {
        cin >> fact_num;

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        cout << num_of_trailing_zeros << "/n";
    }

    return 0;
}

Lo cargué como la solución para g ++ 5.1

El resultado fue: Tiempo 0.18 Mem 3.3M

Pero luego vi algunos comentarios que afirmaban que su tiempo de ejecución fue inferior a 0.1. Como no podía pensar en un algoritmo más rápido, intenté implementar el mismo código en C :

#include <stdio.h>

int main() {
    unsigned int num_of_inputs;
    unsigned int fact_num;
    unsigned int num_of_trailing_zeros;

    scanf("%d", &num_of_inputs);

    while (num_of_inputs--)
    {
        scanf("%d", &fact_num);

        num_of_trailing_zeros = 0;

        for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
            num_of_trailing_zeros += fact_num/fives;

        printf("%d", num_of_trailing_zeros);
        printf("%s","/n");
    }

    return 0;
}

Lo cargué como la solución para gcc 5.1

Esta vez el resultado fue: Tiempo 0.02 Mem 2.1M

Ahora el código es casi el mismo , agregué std::ios_base::sync_with_stdio(false); al código C ++ como se sugirió here para desactivar la sincronización con los buffers stdio de la biblioteca C. También dividí el printf("%d/n", num_of_trailing_zeros); para printf("%d", num_of_trailing_zeros); printf("%s","/n"); printf("%d", num_of_trailing_zeros); printf("%s","/n"); para compensar la doble llamada del operator<< en cout << num_of_trailing_zeros << "/n"; .

Pero aún vi un rendimiento x9 mejor y un menor uso de memoria en el código C vs. C ++.

¿Porqué es eso?

EDITAR

Arreglé unsigned long a unsigned int en el código C. Debería haber sido unsigned int y los resultados que se muestran arriba están relacionados con la nueva versión ( unsigned int ).

Answer 1

Ambos programas hacen exactamente lo mismo. Usan el mismo algoritmo exacto y, dada su baja complejidad, su rendimiento está principalmente vinculado a la eficiencia del manejo de entrada y salida.

escanear la entrada con scanf("%d", &fact_num); por un lado y cin >> fact_num; por otro lado no parece muy costoso de ninguna manera. De hecho, debería ser menos costoso en C ++ ya que el tipo de conversión se conoce en tiempo de compilación y el compilador de C ++ puede invocar directamente el analizador correcto. Lo mismo vale para la salida. Incluso puede escribir una llamada separada para printf("%s","/n"); , pero el compilador de C es lo suficientemente bueno como para compilar esto como una llamada a putchar(''/n''); .

Entonces, mirando la complejidad tanto de E / S como de cómputo, la versión C ++ debería ser más rápida que la versión C.

Deshabilitar completamente el almacenamiento en búfer de stdout ralentiza la implementación de C a algo aún más lento que la versión de C ++. Otra prueba de AlexLop con una fflush(stdout); después de la última printf produce un rendimiento similar al de la versión C ++. No es tan lento como deshabilitar completamente el almacenamiento en búfer porque la salida se escribe en el sistema en pequeños fragmentos en lugar de un byte a la vez.

Esto parece apuntar a un comportamiento específico en su biblioteca de C ++: sospecho que la implementación de cin y cout su sistema cout la salida a cout cuando se solicita la entrada de cin . Algunas bibliotecas C también hacen esto, pero generalmente solo cuando leen / escriben desde y hacia la terminal. La evaluación comparativa realizada por el sitio www.spoj.com probablemente redirige la entrada y salida hacia y desde los archivos.

AlexLop hizo otra prueba: leer todas las entradas a la vez en un vector y posteriormente calcular y escribir todas las salidas ayuda a comprender por qué la versión C ++ es mucho más lenta. Aumenta el rendimiento al de la versión C, esto prueba mi punto y elimina la sospecha sobre el código de formato C ++.

Otra prueba realizada por Blastfurnace, que almacena todas las salidas en std::ostringstream y la descarga que en una explosión al final, mejora el rendimiento de C ++ al de la versión básica de C. QED

El entrelazado de entrada de cin y salida a cout parece causar un manejo de E / S muy ineficiente, lo que anula el esquema de búfer de flujo. Reducir el rendimiento en un factor de 10.

PD: su algoritmo es incorrecto para fact_num >= UINT_MAX / 5 porque fives *= 5 se desbordará y se > fact_num antes de que se convierta en > fact_num . Puede corregir esto haciendo que los fives unsigned long o unsigned long unsigned long long si uno de estos tipos es más grande que unsigned int . También use %u como formato scanf . Tienes suerte de que los chicos de www.spoj.com no sean demasiado estrictos en sus puntos de referencia.

EDITAR: Como se explica más adelante por vitaux, este comportamiento es obligatorio por el estándar C ++. cin está vinculado a cout por defecto. Una operación de entrada de cin para la cual el búfer de entrada necesita rellenarse hará que cout vacíe la salida pendiente. En la implementación del OP, cin parece cout sistemáticamente, lo cual es un poco excesivo y visiblemente ineficiente.

Ilya Popov proporcionó una solución simple para esto: cin se puede desatar de cout lanzando otro hechizo mágico además de std::ios_base::sync_with_stdio(false); :

cin.tie(nullptr);

También tenga en cuenta que este enjuague forzado también ocurre cuando se usa std::endl lugar de ''/n'' para producir un final de línea en cout . Cambiando la línea de salida a la cout << num_of_trailing_zeros << endl; más idiomática e inocente de C ++ cout << num_of_trailing_zeros << endl; degradaría el rendimiento de la misma manera.

Answer 2

El problema es que, citando cppreference :

cualquier entrada de std :: cin, salida a std :: cerr o terminación del programa fuerza una llamada a std :: cout.flush ()

Esto es fácil de probar: si reemplaza

cin >> fact_num;

con

scanf("%d", &fact_num);

y lo mismo para cin >> num_of_inputs pero mantenga cout obtendrá aproximadamente el mismo rendimiento en su versión C ++ (o, más bien, la versión IOStream) que en C one:

Lo mismo sucede si mantiene cin pero reemplaza

cout << num_of_trailing_zeros << "/n";

con

printf("%d", num_of_trailing_zeros);
printf("%s","/n");

Una solución simple es desatar cout y cin como lo menciona Ilya Popov:

cin.tie(nullptr);

Las implementaciones de bibliotecas estándar pueden omitir la llamada al vaciado en ciertos casos, pero no siempre. Aquí hay una cita de C ++ 14 27.7.2.1.3 (gracias a chqrlie):

Clase basic_istream :: sentry: Primero, si is.tie () no es un puntero nulo, la función llama a is.tie () -> flush () para sincronizar la secuencia de salida con cualquier flujo C externo asociado. Excepto que esta llamada se puede suprimir si el área de colocación de is.tie () está vacía. Además, se permite que una implementación difiera la llamada para vaciar hasta que ocurra una llamada de is.rdbuf () -> underflow (). Si no se produce dicha llamada antes de que se destruya el objeto centinela, la llamada al vaciado puede eliminarse por completo.

Answer 3

Otro truco para hacer iostream s más rápido cuando usa cin y cout es llamar

cin.tie(nullptr);

Por defecto, cuando ingresas cualquier cosa desde cin , se vacía cout . Puede dañar significativamente el rendimiento si realiza entradas y salidas intercaladas. Esto se hace para los usos de la interfaz de línea de comandos, donde muestra algún mensaje y luego espera datos:

std::string name;
cout << "Enter your name:";
cin >> name;

En este caso, desea asegurarse de que la solicitud se muestre antes de comenzar a esperar la entrada. Con la línea de arriba se rompe esa corbata, cin y cout vuelven independientes.

Desde C ++ 11, una forma más de lograr un mejor rendimiento con iostreams es usar std::getline junto con std::stoi , de esta manera:

std::string line;
for (int i = 0; i < n && std::getline(std::cin, line); ++i)
{
    int x = std::stoi(line);
}

De esta manera puede acercarse al estilo C en rendimiento, o incluso superar scanf . El uso de getchar y especialmente getchar_unlocked junto con el análisis escrito a mano aún proporciona un mejor rendimiento.

PD. He escrito una publicación comparando varias formas de ingresar números en C ++, útil para jueces en línea, pero solo en ruso, lo siento. Sin embargo, los ejemplos de código y la tabla final deben ser comprensibles.