Комментарии 27
Круто, что в интернете всегда кто-то неправ. Статьи получаются интересные)
Хорошо когда у людей есть много свободного времени.
Что можно ответить на такой простой, но одновременно завуалированно грубый комментарий?
В сутки вы как минимум находитесь 10 минут в туалете, где у вас руки и голова не заняты, давайте посчитаем 4*30*10=1200 минут или 20 часов в моем случае за 4 месяца. Статью я писал в общей сложности не более чем 10 часов, софт, отладку и всякое сопутствующее пусть еще столько же. Как думаете, пострадало ли моё свободное время ощутимо? Тему можно развивать бесконечно. Например от дома до работы мне 8 минут на самокате, я не стою в пробках, так как у меня нет авто, я не трачу время на то чтобы ухаживать за машиной, сколько это в сутки? 1-2-3 часа? У меня нет собаки, с которой мне бы пришлось регулярно ходить на прогулки. И т.д. и т.п. Предлагаю вам постить такие комментарии на автофорумах вроде Дрома и Авто.ру, там оценят, или на форумах собачников и кошатников.
Если вы напишете сюда свой график жизни за месяц - поверьте, я выкину как минимум 50% из всего того, на что вы тратите время, как абсолютно ненужное и бестолковое занятие. Надеюсь объяснять не нужно почему это именно так?
Я не хожу в бары, не посещаю театры и дискотеки, не хожу на спортивные мероприятия и т.п.
Как думаете, я могу те редкие минуты, что я развлекаю себя логическими задачами, потратить на себя?
Вы же читаете Хабр, а могли бы ... - тут напишете что там у вас входит в список одобряемого времяпровождения (интересно, а вы не думали как на том Хабре, где вы находитесь, появляются статьи, и что будет, если все, опасаясь вашего неодобрения, перестанут эти статьи писать?).
Программирую микроконтроллеры STM32, AVR. Правлю драйвера для Linux для сорвременных СнК на базе ARM. Балуюсь с ПЛИСами. Разрабатываю схемотехнику, трассировку печатных плат в том числе СВЧ и DDR. Разрабатываю дизайн корпусов для РЭА и управляющие программы для многокоординатных ЧПУ. В далеком прошлом — сисоп узла Fidonet и оператор узла IRC сети. Юниксоид с 1996 года. Поддерживаю проект FreeBSD и использую эту ОС на рабочем ноутбуке. Апологет движения Open Source и Open Hardware, в том числе RISC-V.
Кстати такой комментарий от такого человека это весьма странно. Как минимум 50% из перечисленного это просто развлекуха.
как я тестировал для C# — программа повисла на 2 часа и я её закрыл не дожидаясь завершения.
2 часа - потому что тесты прогоняются 1000 раз подряд. Кстати, поэтому точность в наносекундах. Общее время замеряется в микросекундах, но там 1000 прогонов. Значит один занимает это же самое время, но в наносекундах в среднем.
Если отключить всякий вывод и заменить 1000 в коде на 1, то выдает вот такой результат на вашем 810x410 лабиринте:
Clever algo took 280255us Naive algo took 3586856us
Да, на вашем лабиринте ваша оптимизация сработала очень хорошо. Примерно раз в 12.
Если лабиринт попроще, то разница будет сильно меньше.
Всего команд 30832 24370
Разница по количеству команд в решении обусловлена не какими-то свойствами алгоритма, а везением. Мой алгоритм перебирает черепашек в одном порядке, ваш - в другом. И этот ваш порядок принципиально не кажется чем-то лучше.
Но, в целом, признаю вашу правоту. Оптимизация действительно срабатывает сильно лучше, чем мне показалось на маленьких тестах.
2 часа - потому что тесты прогоняются 1000 раз подряд
а, ну вот, я даже не увидел этот кусок кода
for (int i = 0; i < 1000; ++i)Разница по количеству команд в решении обусловлена не какими-то свойствами алгоритма, а везением. Мой алгоритм перебирает черепашек в одном порядке, ваш - в другом. И этот ваш порядок принципиально не кажется чем-то лучше.
Ну у вас перебор всех черепашек, у меня только тех, что остаются после каждой итерации. Мне кажется K == N*M всегда хуже чем K < N*M. Я тестировал и для пустого и для змеевидного и для того, что в коде - всегда у меня черепашек меньше. Думаю можно попробовать создать условия, где черепашки даже исчезая будут уходить в некую ветку, которая будет увеличивать число команд, но мне кажется это какой-то особый вырожденный случай не подходящий под типичные лабиринты. Доказать это не могу, как вариант можно на Daedalus сгенерировать штук 1000 разных лабиринтов и прогнать код. Так сказать пойти от статистики.
Оптимизация действительно срабатывает сильно лучше, чем мне показалось на маленьких тестах.
Спасибо что проверили меня, особенно с вопросом про 1000 итераций, я это упустил.
Ну у вас перебор всех черепашек, у меня только тех, что остаются после каждой итерации.
Не совсем. Я перебираю всех черпашек, прикладываю к ним команды, но, если черепашка вышла из лабиринта, она считается вышедшей. Так ApplyCommands завершается, если черепашка ступила на выход. У вас, кстати, тоже. Потом достраивается пустой путь из конца в конец и никаких новых команд в ответ не добавляется. Поэтому из этих N*M путей некотрая часть будет пустой - для всех черепашек, которых ваше решение выкидывает по пути.
Если вы в вашем решении из множества еще живых черепашек будете брать не первую, а ту, у которой изначальные координаты минимальные - ваше решение выдаст в точности тот же ответ, что и мое. Они эквивалентны.
Не совсем. Я перебираю всех черпашек, прикладываю к ним команды, но, если черепашка вышла из лабиринта, она считается вышедшей
for (int x = 0; x < m.Width(); ++x) {
for (int y = 0; y < m.Height(); ++y) {
if (m.IsWall(x, y)) continue;
int nx = x;
int ny = y;
m.ApplyCommands(nx, ny, commands);
auto c = m.GetPath(nx, ny);
commands.insert(commands.end(), c.begin(), c.end());
}
}покажите в коде где вы учитываете вышедшие черепашки? я вижу только проверку на то стена это у вас или нет, по идее в этом же if должна быть и проверка на то, является ли выбранная черепаха "ранее вышедшей"? (в этом месте я придумал еще одну оптимизацию, нужно будет её проверить, если подтвердится, то я сделаю дополнение к статье)
Потом достраивается пустой путь из конца в конец и никаких новых команд в ответ не добавляется
укажите на код, пока не понимаю о чем вы.
Поэтому из этих N*M путей некотрая часть будет пустой - для всех черепашек, которых ваше решение выкидывает по пути.
Не понимаю, циклы у вас явно N*M без дополнительных условий.
Если вы в вашем решении из множества еще живых черепашек будете брать не первую, а ту, у которой изначальные координаты минимальные - ваше решение выдаст в точности тот же ответ, что и мое. Они эквивалентны.
расшифруйте что означает "изначальные координаты минимальны"?
Блин, не в ту кнопку ткнул, извините. Посмотрите мой ответ ниже.
> расшифруйте что означает "изначальные координаты минимальны"?
Лексикографически минимальны. Минимальный x, а при них равных, минимальный y. Чтобы порядок обработки черепашек был одинаковый.
Лексикографически минимальны. Минимальный x, а при них равных, минимальный y. Чтобы порядок обработки черепашек был одинаковый.
уже на второй итерации это не будет работать
Почему? Сначала были черепашки (1,1), (1,2), (1, 3). Путь для первой переместил ее в выход. Вторая и третья стали (123,434) и (1,1). Если сохранять изначальные координаты и выбирать минимальную по ним, то дальше возмется та, которая была сначала (1,2) как в моем решении.
В обоих решениях порядок, в котором черепашки выводятся из лабиринта не влияет на корректность ответа. Он влияет на длину, но весьма неявно. Возможно, брать черепашку которая сейчас ближе всего к выходу - разумная эвристика. Но это не то что делает ваше или мое решение.
Возможно, брать черепашку которая сейчас ближе всего к выходу - разумная эвристика. Но это не то что делает ваше или мое решение.
я так делал, это хуже, так как меньше черепах выбывает за итерацию. По длине команд не проверял, возможно именно по этому критерию был профит.
Почему? Сначала были черепашки (1,1), (1,2), (1, 3). Путь для первой переместил ее в выход. Вторая и третья стали (123,434) и (1,1). Если сохранять изначальные координаты и выбирать минимальную по ним, то дальше возмется та, которая была сначала (1,2) как в моем решении.
потому что у меня на второй итерации нет уже черепашки (1,2). В теории её там можно оставить например в таком лабиринте
12#.
.##.
...Eгде 1 и 2 это черепашки. В этом случае для набора команд Н, Н, П, П, П вторая черепашка останется на месте.
Если лабиринт поменять
12#.
..#.
...Eто в моем случае после первой итерации вторая черепашка исчезнет (вообще для такого лабиринта исчезнут все.
Список команд и у вас и у меня будет одинаков, просто ваш алгоритм сделает еще 8 итераций и добавит 8 раз пустой набор команд.
Такой вырожденный случай может быть не совсем хорош для объяснения, давайте возьмём вот такой лабиринт
12#3
45#6
7##8
900Eгде 0 - это любой номер после 9
В таком случае после первой итерации у вас будет лабиринт
..#.
.2#.
.##.
...EВсе остальные черепашки покинули лабиринт, таким образом у меня черепашка (1,1), а у вас (1,0), конечный список команд будет идентичный, но это из-за особенностей такого вырожденного лабиринта.
Вот было бы в итоге интереснее получать для лабиринта и в моей и в вашем случае одинаковый по длине набор команд, но этого не происходит. Тогда бы мы говорили исключительно о производительности реализаций, а ответ был бы одинаков, это как сравнение сортировок было бы - результат сортировки одинаков, а скорость разная.
потому что у меня на второй итерации нет уже черепашки (1,2).
Поэтому я и написал "которая была сначала (1,2)". Если вы будете запоминать не только координаты черепашки, но и то, где она была в самом начале, то вы можете брать такой же порядок как у меня и получите тот же самый ответ.
так у нас разные условия выхода черепашек с карты, а значит не получится брать такие же как у вас.
Да нет, все то же самое. У меня пути достраиваются для черепах, которые пока еще не вышли из лабиринта. И у вас тоже. Занумеруйте всех черепах и при дублировании удаляйте черепаху с большим номером из двух.
Если какая-то черепаха удаляется у вас как дубликат, то у меня она автоматически окажется в выходе, потому что та, на которую она наехала - оказалась выведена из лабиринта раньше.
Занумеруйте всех черепах и при дублировании удаляйте черепаху с большим номером из двух.
у меня так и работает сейчас, у каждой черепахи порядковый номер (id) и если черепашка пришла до клетки где уже есть черепашка с меньшим id, то значит это уже походившая черепашка, поэтому та которая только пришла - исчезает вообще без следа.
Если какая-то черепаха удаляется у вас как дубликат, то у меня она автоматически окажется в выходе, потому что та, на которую она наехала - оказалась выведена из лабиринта раньше.
пока не прослеживаю этот момент. Ну вот походила у вас черепаха с (1, 2) на (3, 3) как так получается что (3, 3) вышла раньше если вы до неё еще не дошли даже по циклу?
Значит, наоборот. Это черепаха (3,3) наехала на (1,2). Ведь удаляются черепахи с большими номерами, т.е. те, у которых координаты лексикографически больше.
у меня (1, 2) может удалить только (1, 1) которая уже давно вышла из лабиринта, а (3, 3) никогда не сможет удалить (1, 2)
но я мысль потерял давно о чем же мы пытаемся говорить? ах да, о том, что не получится моих черепашек привязать к вашим, как минимум потому, что мои исчезают с карты в двух случаях, а у вас в одном.
Эти случаи эквивалентны. Вы удляете черепах, если они в процессе дойдут до выхода, или наедут на другую черепаху.
Я "удаляю" их, если они дойдут до выхода. Вернее не удаляю, а получаю пустой путь, что полностью эквивалентно игнорированию черепахи.
Если черепаха в процессе дойдет до выхода у вас, она дойдет до выхода и у меня. И наоборот. Если у вас черепаха удалилась, потому что она дубликат, то представьте, что из всех черепах в данной клетке сейчас вы удаляете всех, кроме той у которой начальная клетка была самая первая. У меня эти черепахи окажутся в конце, потому что они с этого момента двигались бы вместе с той первой, не удаленным дубликтом. Но та черепашка имеет меньший номер и в моем алгоритме обрабатывается перовой, а значит она выводится из лабиринта. И все остальные, которые дальше двигались бы с ней тоже вышли, а значит удалены у и у меня. И наоборот, если я удалил черепаху, потому что она оказалсь в конце, значит она пересеклась с какой-то другой, ранее выведенной черепахой. Может быть в конечной точке, а может и раньше.
покажите в коде где вы учитываете вышедшие черепашки?
void Maze::ApplyCommands(int &x, int &y, const vector<Direction> &commands) const {
int pos = (y+1)*_width + x + 1;
for (auto &c : commands) {
if (pos == _exit) break; // Вот тутПоэтому, если черепашка случайно выйдет из лабиринта из-за путей для других черепашек, она так и останется в клетке выхода. А дальше FindPath из клетки выхода в нее же вернет пустой путь. Не надо никаких дополнительных условий.
Допустим, что в наших решениях черепашки перебираются в одинаковом порядке.
У вас:
1) Составили путь, выводящий черепашку 1.
2) увидели, что черепашка 3 "наехала" на черепашку 2 и удалили ее.
3) Составили путь, выводящий черепашку 2.
У меня:
1) Составили путь, выводящий черепашку 1.
2) Составили путь, выводящий черепашку 2.
3) Когда обрабатываем черепашку 3, получаем, что она в конце после ApplyCommands. А она в выходе, ведь она когда-то в процессе "наехала" на черепашку 2, а путь для черепашки 2 мы выше уже составили. Дописываем в ответ пустой путь, фактически выбрасывая черепашку.
if (pos == _exit) break; // Вот тут
это только окончание обработки команд для конкретной черепахи, так как она вышла из лабиринта, а я спрашиваю о том, где вы в коде учитываете вышедшие черепашки?
Поэтому, если черепашка случайно выйдет из лабиринта из-за путей для других черепашек, она так и останется в клетке выхода. А дальше FindPath из клетки выхода в нее же вернет пустой путь. Не надо никаких дополнительных условий.
тогда я не понимаю о чем вы говорили ранее, это штатный режим работы и он абсолютно не влияет на N*M операций.
Когда обрабатываем черепашку 3, получаем, что она в конце после ApplyCommands. А она в выходе, ведь она когда-то в процессе "наехала" на черепашку 2, а путь для черепашки 2 мы выше уже составили. Дописываем в ответ пустой путь, фактически выбрасывая черепашку.
А N*M тут причем? У вас просто сократится набор команд, но число итераций не изменится. У вас всё равно будут двигаться даже те черепашки, которые выйдут раньше, пока вы не провели её до выхода, вы не знаете будет её набор команд пустым или нет. У меня же наоборот, те черепашки что уничтожаются - они уже не принимают участие в передвижении, я бы сказал в пустом и ненужном исполнении команд.
В вашем списке выше пункт 3 - абсолютно лишние операции, вы обрабатываете то, что обрабатывать вообще не нужно.
я спрашиваю о том, где вы в коде учитываете вышедшие черепашки?
Вот:
vector<Direction> Maze::GetPath(int x, int y) const {
int pos = (y+1)*_width + x + 1;
vector<Direction> commands;
while (pos != _exit) { // вот тут.Для уже вышедшей черепашки вернется пустой путь. 0 новых команд допишется к ответу.
тогда я не понимаю о чем вы говорили ранее, это штатный режим работы и он абсолютно не влияет на N*M операций.
Разговор был про длину ответа. Да, это "лишние" по сравнению с вашим решением вычисления, имено это мы и намеряли таймером. Но эти вычисления не влияют на длину ответа.
В вашем списке выше пункт 3 - абсолютно лишние операции, вы обрабатываете то, что обрабатывать вообще не нужно.
Да, но выкинуть эти лишние операции - не бесплатно. Надо черепашек сравнить, найти дубликаты и выкинуть их. Вопрос в том, какие вычисления займут больше времени. Я думал, что дубликатов не будет так много, что их поиск сделает все медленнее. Был не прав, но такие рассуждения имеют право на жизнь.
Для уже вышедшей черепашки вернется пустой путь. 0 новых команд допишется к ответу.
Это критерий сокращения маршрута, а не учет черепахи при выборе.
Я понял про что вы говорите, возможно из-за специфики образования я не понимаю вас должным образом.
Но эти вычисления не влияют на длину ответа
Почему же количество команд разное? Я в ряде случаев достигал разницы в 40 раз именно по длине команд не в пользу вашего решения.
Да, но выкинуть эти лишние операции - не бесплатно. Надо черепашек сравнить, найти дубликаты и выкинуть их. Вопрос в том, какие вычисления займут больше времени. Я думал, что дубликатов не будет так много, что их поиск сделает все медленнее. Был не прав, но такие рассуждения имеют право на жизнь.
я делал визуализатор, там на первых итерациях практически 80% черепах исчезает.
Сопоставимые команды при относительно пустых лабиринтах и при размещении выхода в любом из углов, там все команды практически всегда уводят черепашку досрочно.
Почему же количество команд разное?
Разный порядок в котором берутся черепахи.
Вот пример:
######
#12E3#
######
1,2,3 - черепахи. Если взять сначала 1 и вывести ее, буть будет "RR". Черепаха 2 выйдет из лабринта случайно. Потом взять черепаху 3, она даст путь "L". Итоговый ответ "RRL". Если же сначала взять черепаху 2, то она даст путь "R". Потом взять черепаху 3, она даст путь "L", потом черепаха 1 даст путь "RR" - итоговый ответ будет "RLRR".
Ясно, надеюсь, почему наши решения дают разный порядок перебора черепах?
Публикации
Черепаха в лабиринте или осенний марафон