Алгоритмы на графах (осень 2015)


#22

А можно input 67-го теста?


#23

Ошибка вполне понятна. Константный вектор сам по себе в вектор на преобразуется. Если хотите узнать в чем ошибка, укажите компилятор, который использует “у меня”.

Ваше определение графа просто убийственно. Зачем Вам вектор траля-ля указателей на вектор??? Храните в graph число i соответствующее arcs[i]. Дальше даже смотреть не стал, боюсь голова треснет. Пожалейте меня и переделайте.


#24

Ловите 067.7z (388,8 КБ)

Это может быть недостатком.


#25

67й тест является перемешанной копией одного из предыдущих тестов.

В силу не совсем ясных особенностей, почти все решения на 67м тесте работают в 12 раз медленнее, чем в таком же, но не перемешанном.

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

Справится с 67м тестом можно, понизив константу или обойдя кешпромахи.


#26

@Ivan_Ivanov пооптимизуруйте код, в частности, передачу параметров в функциях, и главное работу с памятью.


#27

Функция поиска лексикографически минимального пути работает раз в 300 быстрее, чем функця поиска самих путей, и где-то в 180 раз быстрее, чем функция поиска максимальной пропускной способности пути, ускорить которые нет никакой возможности. Попытка резервировать память под дуги заранее, избавление от передачи аргументов в функции не дали никакого ускорения. За одну секунду я успеваю обработать только 28 дней из 100 на 67 тесте, возможности добиться более быстрой работы нет.


#28

Откуда такие точные оценки? Как это измерялось?


#29

Я так скажу, если мне покажется, что прохождение 67 теста требует каких-то особых знаний об устройстве памяти или еще что, то тест уберем. Но пока заявления в стиле “оптимизировать некуда” не принимаются, хотя бы потому что есть два принципиально разных правильных решения.


#30

http://rghost.ru/7T5Kyt45b.view


#31

1)Я не очень понял, чем плохо мое представление графа? Каждая вершина это вектор из пар( смежная вершина, указатель на дугу(которая представлена вектором arcs)). 2)“У меня” - это MSVS. Что мне делать с этой ситуацией? Я не понимаю ошибки, я нигде не использую константных векторов.


#32

Юра, константные вектора появляются при выведении типов шаблонов STL. Почему MS VC молчит, это вопрос к MS. А про указатели,я уже сказал. Они элементарно заменяются на индексы и с ними меньше мороки.


#33

Юра, я пошел посмотреть снова на Ваш код и теперь хочу пару слов добавить. Вы же на STL ходили и задачу первую сделали. Компаратор должен удовлетворять концепции Compare. Вспоминается? Сигнатура функции-компаратора какая?


#34

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

Еще вектор, хранящий максимальные пропускные способности, является локальным в блоке цикла. На каждой итерации он разрушается и пересоздается (а в нем почти 10^5 элементов).

Сыграть на увеличение времени может многое. Но, но поиск сначала графа всех путей, а потом поиск пути в нем, наверноее, играет больше всего.

Можно закооментировать этот кусок и проверить: отработает ли меньше, чем за секунду или нет.


#35

Графа всех путей наибольшей пропускной способности.


#36

Спасибо, я нашёл, где у меня было излишнее.


#37

Случайной перенумерацией вершин 67го теста можно добиться того, что даже самое хитро работающее решение будет отрабатывать около секунды. Часто больше секунды.

Все именно из-за кеш-промахов. Причем сортировки входных данными тут уже не помогают.

Прикладываю модифицированный 67й тест (только входные данные).067_modified.in.7z (306,6 КБ)

Challenge: придумать магическую обработку входных данных так, чтобы они с очень хорошей вероятностью удачно располагались в памяти. Либо предложить магический обход вершин, минимизирующий кол-во кеш-промахов, но приводящий к правильному ответу.

Этого теста НЕТ на ejudge и вряд ли он там появится. (это совсем издевательство будет)

Если решение не заходит по TL на ejudge, но укладывается на этом тесте - значит, надо еще подумать.

Чтобы оценить, на какое время работы надо ориентироваться на своей машине: посмотрите время работы 67го теста на ejudge и у себя. И отмасштабируйте 1 секунду.


#38

Подтверждаю. Не появится.


#39

Изи. Никаких отсечений и магической обработки входных данных.

В 1.8 раз дольше 67й теста, а 67й на ejudge у меня за 367мс проходит. 367*1.8 = 660 = accepted! =)


#40

А можно, пожалуйста, input’ы 13-го и 54-го тестов?


#41

Если это быстрейшее из тех решений, что я видел, то взлетает со скрипом: прогонял его на стороне ejudge - 0.94сек :slight_smile:

Интересно, можно ли перемешать еще более неудачно?