В первую очередь статья писалась, чтобы больше узнать про оптимизацию, советы по которой, я надеюсь, вы оставите в комментариях.
Условие задачи и цель
Задача довольно тривиальна:
В городе 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);
}
Комментарии (10)
Eivind
05.05.2015 01:19+9Спецификатор register уже давно как deprecated. И в целом в рассматриваемом примере нет ничего, что касалось бы оптимизации. Выравнивание может незначительно повлиять на std::sort, а для рассматриваемого алгоритма оно не имеет значения. Список инициализации в принципе не является оптимизацией (наоборот, не использование списков инициализации можно считать дурным тоном), к тому же никаким образом не влияет на рассматриваемый алгоритм.
Fl0pZz Автор
05.05.2015 07:35мб тут не так заметно, но оптимизация есть например в отличии от этого за счет выделения куска памяти без использования new/delete, тем самым оптимизируется работа с кешем. Перемещаться по элементам расположенным подряд эффективнее, чем перемещение по всей памяти, которые могут быть разбросаны изза new/delete
arseny30
05.05.2015 11:07Не совсем верная эвристика сжатия путей. На корень будет указывать только элемент, для которого был вызван find, а должны указывать все элементы в пути до корня.
Fl0pZz Автор
05.05.2015 11:19зачем? это одна из реализаций неперечислимых множеств, где нужно знать всего 1 факт об элементе: принадлежит этот элемент множеству (если да, то какому) или нет
arseny30
05.05.2015 11:41Чтобы получить обратную функцию Аккермана в асимптотике, нужно использовать и эвристику сжатия путей, и ранговую эвристику. Но подозреваю, чтобы это проявилось, нужны специально сгенерированные тесты.
Biga
05.05.2015 14:59+1Про списки инициализации в данном случае пример не очень удачный, потому что если size — это int, а parent — указатель, то ничего по умолчанию инициализироваться не будет. В итоге вариант со списком инициализации и инициализация присваиванием будут делать одно и то же. Скорее всего одинаково по скорости, хотя всякое может быть.
Для сложных типов здесь разница может быть, но тогда должен возникать другой вопрос, а не надо ли упростить сам класс, если он так часто создаётся.
ilammy
В итоге, у меня на машине, 60% времени уходит на вызов std::sort().
Максимальная стоимость постройки дороги — 103. Сортировать дороги надо по стоимости. Очевидный намёк на bucket sort. По-моему, дальше смотреть надо в эту сторону, так как это позволяет получить отсортированный массив рёбер за O(n) вместо O(n log n).
Я попробовал так сделать, но тогда read_unlocked() читает мусор в m, а если использовать обычные потоки, то, похоже, 98% времени уходит на собственно чтение.
Fl0pZz Автор
Вики говорит, что bucket sort деградирует при большом количестве малоотличимых элементов, а они будут при достаточно большом входе, мб на малых входных данных выйгрыш и будет, но не на больших.
По поводу мусора в m, это да, мой косяк, забыл обнулить переменные, сейчас исправлю
arseny30
Bucket sort деградирует если разные элементы попадают в одну корзину. С маленькими весами bucket sort это как раз то, что нужно. В одну корзину будут попадать в точности элементы одного веса.