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

Вот скриншот 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-х метод

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

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