Pull to refresh

Оптимизация кода на C++ (C++11) на примере конкретной задачи

C++
Хочется немного рассказать про оптимизацию С/C++ программ, ибо в интернете довольно мало информации. В посте будут объяснения некоторых оптимизаций на примере задачи, которую мне дали решить в институте (задача реализована на С++11, объяснение дается только для 64 битных систем).
В первую очередь статья писалась, чтобы больше узнать про оптимизацию, советы по которой, я надеюсь, вы оставите в комментариях.

Условие задачи и цель

Задача довольно тривиальна:
В городе M строятся N новых микрорайонов, между которыми запланировано M магистральных дорог. Каждая дорога имеет свою стоимость строительства Pij. В прошлом году из этих M дорог муниципалитет успел построить K штук. К сожалению, в этом году финансирование строительства решено было сократить, и теперь из запланированных, но не построенных M-K дорог нужно оставить такие, чтобы из любого микрорайона в любой другой существовал хотя бы один путь, но при этом стоимость их строительства была минимальной (гарантируется, что такой набор существует).
Какова минимальная стоимость P завершения строительства дорожной сети по новому плану, и сколько новых дорог по нему предстоит построить?

ввод/вывод
Формат ввода:
Первая строка содержит через пробел два числа:
N (2 ≤ N ≤ 10^5) — число строящихся микрорайонов,
M (1 ≤ M ≤ min(N(N — 1), 2 * 10^6)) — число запланированных дорог.
Следующие M строк описывают запланированные дороги, отсортированные по паре номеров своих концов, и каждая содержит через пробел три целых числа:
i (1 ≤ i < N) — номер микрорайона, в котором дорога начинается,
j (i < j ≤ N) — номер микрорайона, в котором дорога заканчивается,
Pij (0 ≤ Pij ≤ 103) — стоимость строительства дороги. 0, если дорога уже построена.

Формат вывода:
Вывод должен содержать два числа через пробел: минимальную стоимость P завершения строительства дорожной сети по новому плану и L — число дорог, которые предстоит по нему построить.

и решается алгоритмом Крускала (построение минимального остовного дерева). Изначально в контесте были ограничения в 2 секунды на исполнение и 24 мб памяти. Не серьезно. Перед собой я поставил цель максимально оптимизировать программу и уложиться в 100мс для самого сложного теста, хочу заметить, что использовать можно только STL библиотеку и фиксированные настройки компилятора (как никак это задача из контеста). Поставленная задача была выполнена не до конца — я уложился в 122 мс и 11мб памяти. Для самых нетерпеливых привожу код программы:
Код программы
#include <iostream>
#include <vector>
#include <algorithm>

/*
 * Данная структура обусловлена форматом входных данных
 */
template <class T>
struct Triplet {
    T first;   // Город, в котором дорога начинается
    T second;  // Город, в котором дорога заканчивается
    T third;   // Цена строительства дороги
};

/*
 * Каждый элемент UnionFind это множество
 */
template <class T>
class UF_element {
public:
    T parent;   // представитель множества
    T size;     // размер множества

    UF_element() {}

    UF_element(T id)
            : size(1)
            , parent(id)
    {
    }
};

template <class T>
class UnionFind {
private:
    std::vector<UF_element<T>> Elements;
public:
/*
 * Сначала город состоит из микрорайонов, не соединенных дорогами
 */
    UnionFind(T n)
            : Elements(n + 1)
    {
        for (register T i = 1; i < n + 1; ++i) {
            Elements[i] = UF_element<T>(i);
        }
    }

/*
 * При первом вызове поиска родителя сокращаем путь до него. 
 *     первый поиск за О(log n),
 *     последующие вызовы за O(1)
 */
    T find(T id){
        UF_element<T>& current = Elements[id];

        while (current.parent != Elements[current.parent].parent){
            current.parent = Elements[current.parent].parent;
        }
        return current.parent;
    }

    void merge(T a, T b) {
        UF_element<T>& UF_elem_A = Elements[find(a)];
        UF_element<T>& UF_elem_B = Elements[find(b)];

        if(UF_elem_A.parent == UF_elem_B.parent)
            return;

        if(UF_elem_A.size < UF_elem_B.size) {
            UF_elem_A.parent = b;
            UF_elem_B.size += UF_elem_A.size;
        } else {
            UF_elem_B.parent = a;
            UF_elem_A.size += UF_elem_B.size;
        }
    }
};

template <typename T>
bool comp(const Triplet<T>& a, const Triplet<T>& b) {
    return (a.third < b.third);
}

template <typename T>
void kruskal(std::vector<Triplet<T>>& data, size_t& cost, size_t& count, const size_t& n) {
    UnionFind<T> N(n);

    for (size_t i = 0; i < data.size(); ++i) {
        if (N.find(data[i].first) != N.find(data[i].second)) {
            if (data[i].third) {         // если стоимость дороги не 0 (т.е дорога еще не построена)
                cost += data[i].third;   // увеличиваем стоимость постройки дорог
                ++count;                 // увеличиваем количество дорог, которые надо построить
            }

            N.merge(data[i].first, data[i].second);
        }
    }
}

/*
 * Парсер для любых неотрицательных целочисленных типов
 */
template <typename T>
void read_unlocked(T &out) {
    T c = getchar_unlocked();

    for (; '0' <= c && c <= '9' ; c = getchar_unlocked()) {
        if (c == ' ' || c == '\n')
            return;
        out = out * 10 + c - '0';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);

    size_t count = 0, cost = 0;
    // Не забывайте обнулять переменные. Спасибо @ilammy
    unsigned int n = 0, m = 0;

    read_unlocked(n);
    read_unlocked(m);

    std::vector<Triplet<unsigned int>> input(m);

    for (size_t i = 0; i < m; ++i) {
        read_unlocked(input[i].first);
        read_unlocked(input[i].second);
        read_unlocked(input[i].third);
    }

    std::sort(input.begin(), input.end(), comp<unsigned int>);
    kruskal(input, cost, count, n);

    std::cout << cost << " " << count << '\n';
}


Выравнивание данных

Подробнее узнать, что такое выравнивание данных, можно тут, я лишь поясню на конкретных примерах. К сожалению, в моем коде это нигде явно не используется, но давайте посмотрим на такую структуру:
struct A {
    char a;
    long int b;
    int c;
};

Эта структура занимает 24 байта (для этого выведем на экран результат sizeof(A)).
Теперь рассмотрим такую структуру:
struct B {
    char a;
    int c;
    long int b;
};

Она занимает всего 16 байт. Почему так? Дело в том, что на 64 битной ОС память считывается кусками по 8 байт и для ускорения обработки процессором идет выравнивание данных, конкретно для класса А структура расположения в памяти выглядит так:
(1 байт под a + 7 пустых байт) + (8 байт под b) + (4 байта под c + 4 пустых байта) = 24 байта.
Не очень экономно, правда? Для класса B занимаемая память выглядит так:
(1 байт под a + 3 пустых байта + 4 байта под c) + (8 байт под b) = 16 байт.
На такую мелочь стоит обращать внимание, потому что перемещение данных «туда-сюда» стоит времени, и чем меньше данных перемещается, тем сильнее ускоряется ваша программа, да и потом, поменять местами пару строчек не самая сложная оптимизация.

Списки инициализации

Почему конструктор должен выглядеть так:
UF_element(T id)
        : size(1)
        , parent(id)
{
}

А не так:
UF_element(T id) {
    size = 1;
    parent = id;
}

можно почитать тут. При использовании списков инициализации происходив вызов конструктора с переданными значениями, в отличии от второго случая, когда вызывается конструктор по умолчанию для полей класса и в теле конструкторе класса производится присваивание.

Спецификатор register

Немножко теории:
register — спецификатор автоматического класса памяти. Применяется к объектам, по умолчанию располагаемым в локальной памяти. Представляет из себя «просьбу»(необязателен к исполнению) к компилятору о размещении значений объектов, объявленных со спецификатором register в одном из доступных регистров, а не в локальной памяти.

В своем коде я использовал такую конструкцию:
for (register T i = 1; i < n + 1; ++i) {
    idElements[i] = UF_element<T>(i);
}

Использовать этот спецификатор надо грамотно.
Если надо забить массив числами от 1 до n (почти как у меня в примере выше), то использование спецификатора даст прибавку в скорости, если тело цикла не такое тривиальное, то скорее всего register не только не изменит производительность, но может и уменьшить его, выделив под переменную регистр.

Работа с памятью

Очень коротко и хорошо написано тут. Вообще, когда начинаешь разбираться как программа использует память и, в особенности, ищешь утечки, вырабатываются некоторые правила.

Для себя я уяснил одно: до тех пор, пока программист не в состоянии с ходу сказать когда и где освобождается память, выделенная с помощью оператора new и насколько удобно будет менеджеру памяти обращаться к освободившейся памяти после вызова delete, его надо бить ссанными тряпками за использование new/delete. Поэтому, чтобы не быть побитым, я избавился от использования этих операторов архитектурно:
 UnionFind(T n)
            : Elements(n + 1) // тут я выделяю нужный мне кусок памяти
    {
        for (register T i = 1; i < n + 1; ++i) {
            Elements[i] = UF_element<T>(i); // тут его заполняю
        }
    }


Ввод и вывод данных

Руководствуясь этой статьей, был значительно ускорен ввод. Так как в данной задаче выводятся только 2 числа, то использование putchar (putchar_unlocked) большого профита не приносит, но для тех кто не поверит, пока не проверит, привожу ниже реализацию вывода с использованием putchar_unlocked.
Функция вывода
/*
 * Подходит для всех неотрицательных целочисленных типов:
 *     первый параметр - это число, которое необходимо вывести
 *     второй параметр - это символ, который надо добавить после числа
 */
template <typename T>
void write_unlocked(T inp, char last=' ') {
    if (!inp) {
        putchar_unlocked('0');
        putchar_unlocked(last);
        return;
    }

    T out = 0;
    unsigned char sz_inp = 0;
    // переворачиваем число
    for (; inp; inp /= 10, ++sz_inp) {
        out = (out << 3) + (out << 1) + inp % 10;
    }
    // печатаем число
    for (; out; out /= 10, --sz_inp) {
        putchar_unlocked(out % 10 + '0');
    }
    // выводим нули, если они были в числе
    for (;sz_inp; --sz_inp) {
        putchar_unlocked('0');
    }

    putchar_unlocked(last);
}

Tags:с++
Hubs: C++
Total votes 19: ↑8 and ↓11 -3
Views24.4K
Программист С++
from 150,000 ₽SDTМоскваRemote job
Разработчик С++
from 100,000 ₽Enaza GroupПермьRemote job
Программист С++ Senior
from 300,000 ₽Альфа-ФорексМосква
Старший программист С++
to 300,000 ₽АбордажЧелябинск
Программист С++
to 80,000 ₽СтилсофтRemote job

Top of the last 24 hours