He perfilado un programa de C ++ pesadamente computacional en Linux usando cachegrind. Sorprendentemente, resulta que el cuello de botella de mi programa no está en ningún método de clasificación o computacional ... está en la lectura de la entrada.

Aquí hay una captura de pantalla de cachegrind, en caso de que esté interpretando mal los resultados del generador de perfiles (ver scanf()):

Espero tener razón al decir esoscanf() está tomando el 80,92% de mi tiempo de ejecución.

Leo entrada usandocin >> int_variable_here, al igual que:

std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities;
cin >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];

for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;    

    cin >> cityA;
    //scanf("%d", &cityA);    // scanf() and cin are both too slow
    cin >> cityB;
    //scanf("%d", &cityB);
    cin >> length;
    //scanf("%d", &length);

    Roads[i] = Road(cityA, cityB, length);
}

Si no encuentra ningún problema con este código de lectura de entrada, ¿podría recomendar una manera más rápida de leer la entrada? Estoy pensando en intentarlogetline() (trabajando en ello mientras espero respuestas). Mi conjetura es que getline () puede ejecutarse más rápido porque tiene que hacer menos conversiones y analiza el flujo un número total de veces menos (solo mi conjetura, aunque eventualmente también tendría que analizar las cadenas como enteros).

Lo que quiero decir con "demasiado lento" es que esto es parte de una tarea más grande que se agota después de un cierto período de tiempo (creo que es de 90 segundos). Estoy bastante seguro de que el cuello de botella está aquí porque comenté a propósito una parte importante del resto de mi programa y aún se agota. No sé qué casos de prueba ejecuta el instructor a través de mi programa, pero debe ser un archivo de entrada enorme. Entonces, ¿qué puedo usar para leer la entrada más rápido?

El formato de entrada es estricto: 3 enteros separados por un espacio para cada línea, para muchas líneas:

Entrada de muestra:

7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16

Necesito hacer unRoad Fuera de los enteros en cada línea.

También, por favor, no que la entrada sea redirigida a mi programa a la entrada estándar (myprogram < whatever_test_case.txt). No estoy leyendo un archivo específico. Acabo de leercin.

Actualizar

UtilizandoDe Slava método:

La lectura de entrada parece estar tomando menos tiempo, pero su tiempo de espera está inactivo (puede que ya no se deba a la lectura de entrada). El método de Slava se implementa en elRoad() ctor (2 abajo demain). Así que ahora toma 22% del tiempo en comparación con 80%. Estoy pensando en optimizarSortRoadsComparator() Como se llama 26,000,000 veces.

Código comparador:

// The complexity is sort of required for the whole min() max(), based off assignment instructions
bool SortRoadsComparator(const Road& a, const Road& b)
{
    if (a.Length > b.Length) 
        return false;

    else if (b.Length > a.Length) 
        return true;

    else
    {
        // Non-determinism case
        return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) ||
            (
            (min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB)                                     
            )
            );
    }
}

Utilizandode enhzflep método

Considerando resuelto

Voy a considerar este problema resuelto porque el cuello de botella ya no está en la entrada de lectura. El método de Slava fue el más rápido para mí.