Accelerate Your Code 2012 - оптимизации

draft

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

Хорошая ассимптотика алгоритма еще не гарантирует эффективности программы. Зачастую много времени тратится в самых неожиданных местах. Профилирование исходного решения, данного участникам организаторами конкурса, показало следующие результаты - больше всего времени тратилось на ввод, его разбор и различные операции со строками. Поэтому первым делом мы переписали эту часть кода.

Ввод. Вместо чтения непосредственно файла мы отобразили файл в память (функция mmap) и читали уже оттуда.

Строки. Вместо С++-строк (std::string) мы использовали C-строки (char*). Все строки считываются в большой буфер, а указатели на них сохранятся в специальном пуле, причем, если попадаются одинаковые строки, то сохраняется указатель только на первую из них. После этого, если где-то в программе есть две одинаковые строки, то они лежат по одному адресу, и их можно сравнивать, просто сравнивая указатели.

Время. Также неожиданно долго работало преобразование времени из формата epoch, а именно функция mktime, которая вызывалась довольно много раз. Мы решили кешировать ее вызовы для годов и месяцев а дни, часы, минуты и секунды добавлять вручную. То есть, если нужно проеобразовать дату 21.10.2012 11:47:20, то из кеша доставался результат для 1.10.2012 00:00:00 (если такой есть, если же нет, то вызывали mktime и сохраняли в кеш), а к нему уже добавляли оставшееся время. Так как разброс по годам небольшой, то вызывов функции mktime стало очень мало.

Построение графа. Сначала граф строился для каждого разбираемого случая отдельно - для Work Hard и для каждого города отдыха из Play Hard. Потом мы заметили, что графы получаются очень похожие - отличаются они только городом, по которому связываются слои. Тогда мы построили два графа (один для случая дом->конференция->отдых, другой для дом->отдых->конференция), в которых не было связи по городу отдыха. Затем при решении каждой подзадачи мы копировали эти графы и связывали слои по рассматриваемому городу. Стало работать заметно быстрее. Замеры времени показали, что копирование графа, все же, занимет большую часть времени при решении каждой подзадачи. Пытались придумать, как копировать быстрее, но ничего не придумали. Потом было замечено, что изменеия, вносимые в графы при решении подзадач, довольно малы по сравнению с размерами самих графов. Поэтому попробовали не копировать графы, а использовать уже готовые (при этом их приходилось немного изменять), а потом откатывать их к начальному состоянию. На больших тестах это уменьшило время работы в два раза.

Categorías:
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.