Fl0pZz May 4 2015 at 23:06

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

6 min

28K

C++*

-3

Comments 10

ilammy May 5 2015 at 01:13

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

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

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

Fl0pZz May 5 2015 at 07:09

Вики говорит, что bucket sort деградирует при большом количестве малоотличимых элементов, а они будут при достаточно большом входе, мб на малых входных данных выйгрыш и будет, но не на больших.

По поводу мусора в m, это да, мой косяк, забыл обнулить переменные, сейчас исправлю

arseny30 May 5 2015 at 11:20

Bucket sort деградирует если разные элементы попадают в одну корзину. С маленькими весами bucket sort это как раз то, что нужно. В одну корзину будут попадать в точности элементы одного веса.

Eivind May 5 2015 at 01:19

Спецификатор register уже давно как deprecated. И в целом в рассматриваемом примере нет ничего, что касалось бы оптимизации. Выравнивание может незначительно повлиять на std::sort, а для рассматриваемого алгоритма оно не имеет значения. Список инициализации в принципе не является оптимизацией (наоборот, не использование списков инициализации можно считать дурным тоном), к тому же никаким образом не влияет на рассматриваемый алгоритм.

Fl0pZz May 5 2015 at 07:35

мб тут не так заметно, но оптимизация есть например в отличии от этого за счет выделения куска памяти без использования new/delete, тем самым оптимизируется работа с кешем. Перемещаться по элементам расположенным подряд эффективнее, чем перемещение по всей памяти, которые могут быть разбросаны изза new/delete

Fl0pZz May 5 2015 at 07:46

и использование цельного куска памяти может дать профит, но это уже от компилятора зависит.

arseny30 May 5 2015 at 11:07

Не совсем верная эвристика сжатия путей. На корень будет указывать только элемент, для которого был вызван find, а должны указывать все элементы в пути до корня.

Fl0pZz May 5 2015 at 11:19

зачем? это одна из реализаций неперечислимых множеств, где нужно знать всего 1 факт об элементе: принадлежит этот элемент множеству (если да, то какому) или нет

arseny30 May 5 2015 at 11:41

Чтобы получить обратную функцию Аккермана в асимптотике, нужно использовать и эвристику сжатия путей, и ранговую эвристику. Но подозреваю, чтобы это проявилось, нужны специально сгенерированные тесты.

Biga May 5 2015 at 14:59

Про списки инициализации в данном случае пример не очень удачный, потому что если size — это int, а parent — указатель, то ничего по умолчанию инициализироваться не будет. В итоге вариант со списком инициализации и инициализация присваиванием будут делать одно и то же. Скорее всего одинаково по скорости, хотя всякое может быть.

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

Show the best of all time