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

    Хочется немного рассказать про оптимизацию С/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);
    }
    

    Share post

    Comments 10

      0
      В итоге, у меня на машине, 60% времени уходит на вызов std::sort().

      Максимальная стоимость постройки дороги — 103. Сортировать дороги надо по стоимости. Очевидный намёк на bucket sort. По-моему, дальше смотреть надо в эту сторону, так как это позволяет получить отсортированный массив рёбер за O(n) вместо O(n log n).

      Я попробовал так сделать, но тогда read_unlocked() читает мусор в m, а если использовать обычные потоки, то, похоже, 98% времени уходит на собственно чтение.
        0
        Вики говорит, что bucket sort деградирует при большом количестве малоотличимых элементов, а они будут при достаточно большом входе, мб на малых входных данных выйгрыш и будет, но не на больших.

        По поводу мусора в m, это да, мой косяк, забыл обнулить переменные, сейчас исправлю
          0
          Bucket sort деградирует если разные элементы попадают в одну корзину. С маленькими весами bucket sort это как раз то, что нужно. В одну корзину будут попадать в точности элементы одного веса.
        +9
        Спецификатор register уже давно как deprecated. И в целом в рассматриваемом примере нет ничего, что касалось бы оптимизации. Выравнивание может незначительно повлиять на std::sort, а для рассматриваемого алгоритма оно не имеет значения. Список инициализации в принципе не является оптимизацией (наоборот, не использование списков инициализации можно считать дурным тоном), к тому же никаким образом не влияет на рассматриваемый алгоритм.
          0
          мб тут не так заметно, но оптимизация есть например в отличии от этого за счет выделения куска памяти без использования new/delete, тем самым оптимизируется работа с кешем. Перемещаться по элементам расположенным подряд эффективнее, чем перемещение по всей памяти, которые могут быть разбросаны изза new/delete
            0
            и использование цельного куска памяти может дать профит, но это уже от компилятора зависит.
          0
          Не совсем верная эвристика сжатия путей. На корень будет указывать только элемент, для которого был вызван find, а должны указывать все элементы в пути до корня.
            0
            зачем? это одна из реализаций неперечислимых множеств, где нужно знать всего 1 факт об элементе: принадлежит этот элемент множеству (если да, то какому) или нет
              0
              Чтобы получить обратную функцию Аккермана в асимптотике, нужно использовать и эвристику сжатия путей, и ранговую эвристику. Но подозреваю, чтобы это проявилось, нужны специально сгенерированные тесты.
            +1
            Про списки инициализации в данном случае пример не очень удачный, потому что если size — это int, а parent — указатель, то ничего по умолчанию инициализироваться не будет. В итоге вариант со списком инициализации и инициализация присваиванием будут делать одно и то же. Скорее всего одинаково по скорости, хотя всякое может быть.

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

            Only users with full accounts can post comments. Log in, please.