Первая дуэль. , Наичистейший С++ vs С++ + stl + boost

[Flex Ferrum]

Цитата nvm @ 22.09.05, 15:41

Flex Ferrum, ты, наверное, жестко ограничиваешь использование памяти?

Да. Пока что память используется по минимуму. Но это ненадолго.

[nvm]

Цитата Flex Ferrum @ 22.09.05, 16:46

Цитата nvm @ 22.09.05, 15:41

Flex Ferrum, ты, наверное, жестко ограничиваешь использование памяти?

Да. Пока что память используется по минимуму. Но это ненадолго.

Ничего, я тоже оставил резерв для будущей оптимизации

Добавлено 22.09.05, 17:21
А ты усложнения внес только, чтобы ловить циклы, или обнаружил, что алгортм Дейкстры в непосредственном виде неприменим и без циклов?

Добавлено 22.09.05, 17:49
Вроде бы Дейкстра не должен сработать на таком примере:
6 6 5
0 1 110 120
0 2 100 100
1 3 0 120
2 3 0 100
3 4 0 150
4 5 0 150

[Flex Ferrum]

Цитата nvm @ 22.09.05, 17:03

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

Посуди сам. Алгоритм Дейкстры основан на том предположении, что веса ребер и дуг фиксированы, а потому мы действительно можем уложиться во время O(n²). В нашем случае ситуация осложняется тем, что, как правильно заметил Sazabis, мы можем придти в какую-то из вершин графа с "оставанием" от предыдущего резульата, но на большей скорости. Таким образом получается, что вектор минимальных "расстояний" в чистом виде не применим, а вместе с ним и весь Дейкстра.

[Sazabis]

Цитата Flex Ferrum @ 22.09.05, 20:40

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

Ну это вы загнули. Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость) и, как я подумал по дороге на работу, еще и метку "проехал" или нет. Тоесть если добавить метку "уже проехал" помимо (время/скорость), то НЕ получим фиксирование циклов, а если эту метку убрать, то получим нахождение с учетом "разгонных" циклов.

Цитата nvm @ 22.09.05, 15:41

Sazabis, а у тебя есть "эталонный" алгоритм решения задачи (тот, который использовался при просчете тестов) ?

эталона нету, могу положить свой .exe, без кода, так как он ужасен )) , я писал на время. Если в выходные будет время подредактирую выложу код.

[Sazabis]

смотрите на время и память.
Прикреплённый файлl9porshe.rar (103.44 Кбайт, скачиваний: 167)

[Flex Ferrum]

Цитата Sazabis @ 23.09.05, 07:06

Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость) и, как я подумал по дороге на работу, еще и метку "проехал" или нет. Тоесть если добавить метку "уже проехал" помимо (время/скорость), то НЕ получим фиксирование циклов, а если эту метку убрать, то получим нахождение с учетом "разгонных" циклов.

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

[nvm]

Цитата Flex Ferrum @ 22.09.05, 20:40

Посуди сам. Алгоритм Дейкстры основан на том предположении, что веса ребер и дуг фиксированы, а потому мы действительно можем уложиться во время O(n²).

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

Мне задача представляется полиномиально неразрешимой, поэтому я сразу затеял использовать рекурсивный алгоритм.

-юсртыхэю 23.09.05, 09:58

Цитата Sazabis @ 23.09.05, 07:06

.. без кода, так как он ужасен ))

Не стесняйся - все свои
..Екзешник в 300кб - это тоже ужасно (в данном случае).

-юсртыхэю 23.09.05, 10:16

Цитата Flex Ferrum @ 23.09.05, 07:49

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

Если комбинировать идею Дейкстры с ограниченным перебором, то, наверное, можно сильно ускорить поиск, но алгоритм получается сильно "развесистый".
..Как-то лень связываться с алгоритмической оптимизацией, но если напишешь более быстрый вариант, то и мне придется.

Сообщение отредактировано: nvm - 23.09.05, 10:16

[Sazabis]

Цитата nvm @ 23.09.05, 09:34

Екзешник в 300кб - это тоже ужасно (в данном случае).

оттуда можно много выкинуть к тому же это вроде дебаг сборка

Добавлено 23.09.05, 10:21

Цитата nvm @ 23.09.05, 09:34

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

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Добавлено 23.09.05, 10:23
у nvm выделение памяти через new прямо в рекурсивном цикле, нельзя было за ранее чтоли продумать. Там столько вызовов этой процедуры на большом графе.

[Flex Ferrum]

Цитата Sazabis @ 23.09.05, 07:06

Ну это вы загнули. Просто тут в качестве метки вершины надо использовать не метку (был/небыл) а пару (время/скорость)

Да даже если и так - по каким криетриям сравнивать эту пару? По каким критериям выбирать очередной узел (если использовать идею Дейкстры)? По минимальному времени? По максимальной скорости?

Добавлено 23.09.05, 10:35

Цитата Sazabis @ 23.09.05, 10:17

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Сделал. И что? 0-ые дуги помещаются вначало (отсортированные по расстоянию), помеченные - в конец.

[nvm]

Цитата Sazabis @ 23.09.05, 10:17

блин сделайте сортировку, ( вроде ее у вас не видно ) Ничего там развесистого нету.

Пока мой алгоритм быстрее, чем у Flex Ferrum-а, нет стимула модернизировать.

Цитата

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

Выделение памяти обычно первый кандидат на оптимизацию (тем более, когда 100Мб выделяются кусочками по 30б), но пока, как ни странно, не это узкое место (скорость приращения используемой программой памяти существенно падает со временем, что означает, что не в памяти дело).

[Sazabis]

Цитата Flex Ferrum @ 23.09.05, 10:33

Сделал. И что? 0-ые дуги помещаются вначало (отсортированные по расстоянию), помеченные - в конец.

имхо, сортировка ветвей должна быть по времени при попадании в узел. А не один раз в начале. Это же эвристический показатель крутости ветви. Он постоянно меняеться в зависимости от того, когда вы пришли в узел. Двигаясь сразу по наиболее быстрой траектории мы получаем давольно сностное время прохождения, которое потом нам поможет отсеить большенство ветвей еще на середине прохождения. Можно сортировать по скорости, опять таки при попадании в узел. На разных задачках эти два подхода обратно пропорциональны. Можно конечно коэфициэнт крутости взять исходя из скорости (некий знак, +,* ...) времени прохождения.
Но если сортировать по времени, по на больших графах получаете выйгрыш при выходе из цикла по первому достижению макс времени, без сортировки вам приходиться проверять весь граф.
Не считаю ЭТО алгоритмической трудностью, это естественный подход для решения подобной задачи. Надо еще заметить, что я был в курсе, что придеться сортировку реализовывать

Сообщение отредактировано: Sazabis - 23.09.05, 11:07

[nvm]

Новая версия программы для демонстрации бесполезности stl+boost.
Время работы на всех задачах меньше секунды.
Код не до конца причесан, но бывает хуже.
Прикреплённый файлMinTime.rar (5.67 Кбайт, скачиваний: 186)

[Sazabis]

вот это уже заявка на победу. Ждемсъ Flex Ferrum.

а, nvm, причеши пока свой код, и пояснения к алгоритму напиши, а то крыша едет.

[Flex Ferrum]

Цитата Sazabis @ 23.09.05, 14:29

Ждемсъ Flex Ferrum.

Блин. У меня засада - не могу догнать идею алгоритма.

[nvm]

Цитата Sazabis @ 23.09.05, 14:29

а, nvm, причеши пока свой код, и пояснения к алгоритму напиши, а то крыша едет.

Пояснения напишу, а причесывать - не уверен в целесообразности, так как вряд ли его кто будет использовать, а общая идеология и так понятна.

..Свой вариант все же тоже выложи.