Я профилировал вычислительную программу на C ++ для Linux с использованием cachegrind. Удивительно, но оказывается, что узким местом моей программы является не какой-либо сортировка или вычислительный метод ... это чтение входных данных.

Вот скриншот cachegrind, на случай, если я неправильно интерпретирую результаты профилировщика (видеть scanf()):

Я надеюсь, что я правильно сказалscanf() занимает 80,92% моего бега.

Я читаю ввод, используяcin >> int_variable_here, вот так:

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);
}

Если вы не обнаружите никаких проблем с этим кодом чтения ввода, не могли бы вы порекомендовать более быстрый способ чтения ввода? Я думаю о попыткеgetline() (работаю над этим, пока жду ответов). Я предполагаю, что getline () может работать быстрее, потому что он должен выполнять меньше преобразований, и он анализирует поток меньшее общее количество раз (просто мое предположение, хотя в конечном итоге мне бы тоже пришлось анализировать строки как целые числа).

Под «слишком медленным» я подразумеваю то, что это часть более крупного домашнего задания, которое истекает по истечении определенного времени (я считаю, что это 90 секунд). Я вполне уверен, что узкое место здесь, потому что я специально закомментировал основную часть остальной части моей программы, и она все еще истекла. Я не знаю, какие тестовые случаи инструктор выполняет через мою программу, но это должен быть огромный входной файл. Итак, что я могу использовать для быстрого чтения ввода?

Формат ввода строгий: 3 целых числа, разделенных одним пробелом для каждой строки, для многих строк:

Пример ввода:

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

Мне нужно сделатьRoad из целых чисел в каждой строке.

Также, пожалуйста, не делайте, чтобы ввод перенаправлялся в мою программу на стандартный ввод (myprogram < whatever_test_case.txt). Я не читаю конкретный файл. Я только что прочиталcin.

Обновить

С помощьюСлавины метод:

Кажется, что чтение входных данных занимает меньше времени, но его время все еще истекло (возможно, это не связано с чтением входных данных). Метод Славы реализован вRoad() ctor (2 вниз отmain). Так что теперь это занимает 22% времени, а не 80%. Я думаю об оптимизацииSortRoadsComparator() как это называется 26 000 000 раз.

Код компаратора:

// 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)                                     
            )
            );
    }
}

С помощьюenhzflep-х метод

Считая решенным

Я собираюсь считать эту проблему решенной, потому что узкое место больше не в чтении ввода. Метод Славы был самым быстрым для меня.