Вы же покупая вещи в магазине, не в аренду их берете, и не ожидание что завтра к вам прибежит владелец бренда ее отбирать потому ему просто так захотелось?
С развитием "умной" техники примерно это и происходит. Производители окирпичивают устройства. Ограничивают перепродажу (например с машинами такая фигря часто).
Нет. У меня в стиме есть, например, игра про аватара. Лицензия у игроделов истекла и они никак нигде и ни при каких условиях не могут ее больше продавать. А правоторговцы бы с радостью, я думаю, удалили бы игру у всех, у кого могли бы.
Вот обновления, ломающие игры - это да. Но тут стим никак не виноват.
edit: а самый громкий такой скандал был с warcraft 3 refunded - выкатили ремастер, и при этом убили старую версию. При чем, опять же, главная проблема - не файлы у пользователей (говорят, через консоль стима можно скачать и старые версии). Blizzard убили сервера старой версии.
Конкорд - из ряда вон выходящее исключение. Игру отменили спустя несколько дней после выхода, с огромным скандалом. Оставшийся нерабочий мусор на много гигабайт вряд ли кому-то был бы нужен. Очевидно, что 99.9999% людей бы хотело ее рефанднуть.
Справедливости ради, стоит указать, что стим ни разу еще не зашкварился. Даже если издатели выпиливают игру из стима, все купившие игру спокойно могут ее скачать.
Вот то, что всякий мерзопакостный DRM и прочая привязка к онлайн серверам со временем отмирает или издатели выкатывают "обновления" удаляющие из игры контент - это да. Но это не к стиму вопросы, а к издателям. И стим на странице покупки пишет, если игра этой DRM-ом поражена.
график с выбросом показывает отрезок от 2989 до 4989+ по оси OY. Сглаженные графики показывают отрезки 4727-4757 и 4877-4927. Их же невозможно так сравнивать. Стоило привести их к одному масштабу. Если на таких графиках полхо видно, то можно потом приблизить какую-то часть, но опять же, в одном масштабе.
В чем сложность отсортировать набор данных ?
Я с точки зрения вычислений. Сортировка - сильно медленнее и сложнее, чем поддерживать сумму чисел в окне.
У вас на графиках разные точки отсчета. Ну нельзя же так.
А так, медиана лучше исключает выбросы по очевидным причинам, ведь эти выбросы в окне оказываются самыми маленькими или большими и в медиану никак не попадут. Максимум, они сдвинут медиану на соседнее корректное значение. Медиана рабоатет даже для маленьких окон.
Среднее сглаживает выбросы только если окно сильно большое, а выбросы редкие. Ибо каждый выброс изменит ответ на |Error|/N, где Error - размер ошибки, а N - размер окна.
Касаемо кода: какой-нибудь класс Point с переопределенными операциями сложения и хотя бы умножения на скаляр сделал бы ваш код на порядки более читаемым. Еще хорошо бы векторное/скалярные произведения переопределить, например через * и ^. y1 = seg1[1][1] - вообще плохо. Все это вычисление пересечения отрезков становится буквально парой векторых/скалярных произведений. И количество параметров функций делится на 2 и имена будут более понятными.
his_tau , shad_el , iii - вообще непоятные имена переменных. Я пока так и не разобрался, что там происходит.
А так, идея здравая - нанести все точки пересечения на отрезки, пометить их как вхождение внутрь или выход из другого многоугольника, потом выкинуть отрезки целиком внутри, и замкнуть все контура из оставшихся отрезков. Проблема с параллельными накладывающимеся отрезками и пересечениями по вершинам, но тут можно считать, что треугольник на epsilion больше, чем он есть на самом деле и так аккуратно рассмотреть несколько случаев.
Эти случаи эквивалентны. Вы удляете черепах, если они в процессе дойдут до выхода, или наедут на другую черепаху.
Я "удаляю" их, если они дойдут до выхода. Вернее не удаляю, а получаю пустой путь, что полностью эквивалентно игнорированию черепахи.
Если черепаха в процессе дойдет до выхода у вас, она дойдет до выхода и у меня. И наоборот. Если у вас черепаха удалилась, потому что она дубликат, то представьте, что из всех черепах в данной клетке сейчас вы удаляете всех, кроме той у которой начальная клетка была самая первая. У меня эти черепахи окажутся в конце, потому что они с этого момента двигались бы вместе с той первой, не удаленным дубликтом. Но та черепашка имеет меньший номер и в моем алгоритме обрабатывается перовой, а значит она выводится из лабиринта. И все остальные, которые дальше двигались бы с ней тоже вышли, а значит удалены у и у меня. И наоборот, если я удалил черепаху, потому что она оказалсь в конце, значит она пересеклась с какой-то другой, ранее выведенной черепахой. Может быть в конечной точке, а может и раньше.
Значит, наоборот. Это черепаха (3,3) наехала на (1,2). Ведь удаляются черепахи с большими номерами, т.е. те, у которых координаты лексикографически больше.
Да нет, все то же самое. У меня пути достраиваются для черепах, которые пока еще не вышли из лабиринта. И у вас тоже. Занумеруйте всех черепах и при дублировании удаляйте черепаху с большим номером из двух.
Если какая-то черепаха удаляется у вас как дубликат, то у меня она автоматически окажется в выходе, потому что та, на которую она наехала - оказалась выведена из лабиринта раньше.
потому что у меня на второй итерации нет уже черепашки (1,2).
Поэтому я и написал "которая была сначала (1,2)". Если вы будете запоминать не только координаты черепашки, но и то, где она была в самом начале, то вы можете брать такой же порядок как у меня и получите тот же самый ответ.
1,2,3 - черепахи. Если взять сначала 1 и вывести ее, буть будет "RR". Черепаха 2 выйдет из лабринта случайно. Потом взять черепаху 3, она даст путь "L". Итоговый ответ "RRL". Если же сначала взять черепаху 2, то она даст путь "R". Потом взять черепаху 3, она даст путь "L", потом черепаха 1 даст путь "RR" - итоговый ответ будет "RLRR".
Ясно, надеюсь, почему наши решения дают разный порядок перебора черепах?
Почему? Сначала были черепашки (1,1), (1,2), (1, 3). Путь для первой переместил ее в выход. Вторая и третья стали (123,434) и (1,1). Если сохранять изначальные координаты и выбирать минимальную по ним, то дальше возмется та, которая была сначала (1,2) как в моем решении.
В обоих решениях порядок, в котором черепашки выводятся из лабиринта не влияет на корректность ответа. Он влияет на длину, но весьма неявно. Возможно, брать черепашку которая сейчас ближе всего к выходу - разумная эвристика. Но это не то что делает ваше или мое решение.
я спрашиваю о том, где вы в коде учитываете вышедшие черепашки?
Вот:
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 - абсолютно лишние операции, вы обрабатываете то, что обрабатывать вообще не нужно.
Да, но выкинуть эти лишние операции - не бесплатно. Надо черепашек сравнить, найти дубликаты и выкинуть их. Вопрос в том, какие вычисления займут больше времени. Я думал, что дубликатов не будет так много, что их поиск сделает все медленнее. Был не прав, но такие рассуждения имеют право на жизнь.
покажите в коде где вы учитываете вышедшие черепашки?
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 мы выше уже составили. Дописываем в ответ пустой путь, фактически выбрасывая черепашку.
Ну у вас перебор всех черепашек, у меня только тех, что остаются после каждой итерации.
Не совсем. Я перебираю всех черпашек, прикладываю к ним команды, но, если черепашка вышла из лабиринта, она считается вышедшей. Так ApplyCommands завершается, если черепашка ступила на выход. У вас, кстати, тоже. Потом достраивается пустой путь из конца в конец и никаких новых команд в ответ не добавляется. Поэтому из этих N*M путей некотрая часть будет пустой - для всех черепашек, которых ваше решение выкидывает по пути.
Если вы в вашем решении из множества еще живых черепашек будете брать не первую, а ту, у которой изначальные координаты минимальные - ваше решение выдаст в точности тот же ответ, что и мое. Они эквивалентны.
как я тестировал для C# — программа повисла на 2 часа и я её закрыл не дожидаясь завершения.
2 часа - потому что тесты прогоняются 1000 раз подряд. Кстати, поэтому точность в наносекундах. Общее время замеряется в микросекундах, но там 1000 прогонов. Значит один занимает это же самое время, но в наносекундах в среднем.
Если отключить всякий вывод и заменить 1000 в коде на 1, то выдает вот такой результат на вашем 810x410 лабиринте:
Clever algo took 280255us Naive algo took 3586856us
Да, на вашем лабиринте ваша оптимизация сработала очень хорошо. Примерно раз в 12.
Если лабиринт попроще, то разница будет сильно меньше.
Всего команд 30832 24370
Разница по количеству команд в решении обусловлена не какими-то свойствами алгоритма, а везением. Мой алгоритм перебирает черепашек в одном порядке, ваш - в другом. И этот ваш порядок принципиально не кажется чем-то лучше.
Но, в целом, признаю вашу правоту. Оптимизация действительно срабатывает сильно лучше, чем мне показалось на маленьких тестах.
Главное отличие, что тогда не было человеческой цивилизации. Как кто-то отлично сказал "Планета в порядке. Это людям кранты". Можно очень резко и сильно изменить климат и вряд ли биосфера вымрет. Ну, будет очередное массовое вымирание, их было куча. Вот только быть часть этого вымирания никто не хочет.
С развитием "умной" техники примерно это и происходит. Производители окирпичивают устройства. Ограничивают перепродажу (например с машинами такая фигря часто).
Нет. У меня в стиме есть, например, игра про аватара. Лицензия у игроделов истекла и они никак нигде и ни при каких условиях не могут ее больше продавать. А правоторговцы бы с радостью, я думаю, удалили бы игру у всех, у кого могли бы.
Вот обновления, ломающие игры - это да. Но тут стим никак не виноват.
edit: а самый громкий такой скандал был с warcraft 3 refunded - выкатили ремастер, и при этом убили старую версию. При чем, опять же, главная проблема - не файлы у пользователей (говорят, через консоль стима можно скачать и старые версии). Blizzard убили сервера старой версии.
Конкорд - из ряда вон выходящее исключение. Игру отменили спустя несколько дней после выхода, с огромным скандалом. Оставшийся нерабочий мусор на много гигабайт вряд ли кому-то был бы нужен. Очевидно, что 99.9999% людей бы хотело ее рефанднуть.
Справедливости ради, стоит указать, что стим ни разу еще не зашкварился. Даже если издатели выпиливают игру из стима, все купившие игру спокойно могут ее скачать.
Вот то, что всякий мерзопакостный DRM и прочая привязка к онлайн серверам со временем отмирает или издатели выкатывают "обновления" удаляющие из игры контент - это да. Но это не к стиму вопросы, а к издателям. И стим на странице покупки пишет, если игра этой DRM-ом поражена.
график с выбросом показывает отрезок от 2989 до 4989+ по оси OY. Сглаженные графики показывают отрезки 4727-4757 и 4877-4927. Их же невозможно так сравнивать. Стоило привести их к одному масштабу. Если на таких графиках полхо видно, то можно потом приблизить какую-то часть, но опять же, в одном масштабе.
Я с точки зрения вычислений. Сортировка - сильно медленнее и сложнее, чем поддерживать сумму чисел в окне.
У вас на графиках разные точки отсчета. Ну нельзя же так.
А так, медиана лучше исключает выбросы по очевидным причинам, ведь эти выбросы в окне оказываются самыми маленькими или большими и в медиану никак не попадут. Максимум, они сдвинут медиану на соседнее корректное значение. Медиана рабоатет даже для маленьких окон.
Среднее сглаживает выбросы только если окно сильно большое, а выбросы редкие. Ибо каждый выброс изменит ответ на |Error|/N, где Error - размер ошибки, а N - размер окна.
Еще медиану в окне немного сложнее считать.
Касаемо кода: какой-нибудь класс Point с переопределенными операциями сложения и хотя бы умножения на скаляр сделал бы ваш код на порядки более читаемым. Еще хорошо бы векторное/скалярные произведения переопределить, например через * и ^.
y1 = seg1[1][1]- вообще плохо. Все это вычисление пересечения отрезков становится буквально парой векторых/скалярных произведений. И количество параметров функций делится на 2 и имена будут более понятными.his_tau,shad_el,iii- вообще непоятные имена переменных. Я пока так и не разобрался, что там происходит.А так, идея здравая - нанести все точки пересечения на отрезки, пометить их как вхождение внутрь или выход из другого многоугольника, потом выкинуть отрезки целиком внутри, и замкнуть все контура из оставшихся отрезков. Проблема с параллельными накладывающимеся отрезками и пересечениями по вершинам, но тут можно считать, что треугольник на epsilion больше, чем он есть на самом деле и так аккуратно рассмотреть несколько случаев.
Эти случаи эквивалентны. Вы удляете черепах, если они в процессе дойдут до выхода, или наедут на другую черепаху.
Я "удаляю" их, если они дойдут до выхода. Вернее не удаляю, а получаю пустой путь, что полностью эквивалентно игнорированию черепахи.
Если черепаха в процессе дойдет до выхода у вас, она дойдет до выхода и у меня. И наоборот. Если у вас черепаха удалилась, потому что она дубликат, то представьте, что из всех черепах в данной клетке сейчас вы удаляете всех, кроме той у которой начальная клетка была самая первая. У меня эти черепахи окажутся в конце, потому что они с этого момента двигались бы вместе с той первой, не удаленным дубликтом. Но та черепашка имеет меньший номер и в моем алгоритме обрабатывается перовой, а значит она выводится из лабиринта. И все остальные, которые дальше двигались бы с ней тоже вышли, а значит удалены у и у меня. И наоборот, если я удалил черепаху, потому что она оказалсь в конце, значит она пересеклась с какой-то другой, ранее выведенной черепахой. Может быть в конечной точке, а может и раньше.
Значит, наоборот. Это черепаха (3,3) наехала на (1,2). Ведь удаляются черепахи с большими номерами, т.е. те, у которых координаты лексикографически больше.
Да нет, все то же самое. У меня пути достраиваются для черепах, которые пока еще не вышли из лабиринта. И у вас тоже. Занумеруйте всех черепах и при дублировании удаляйте черепаху с большим номером из двух.
Если какая-то черепаха удаляется у вас как дубликат, то у меня она автоматически окажется в выходе, потому что та, на которую она наехала - оказалась выведена из лабиринта раньше.
Поэтому я и написал "которая была сначала (1,2)". Если вы будете запоминать не только координаты черепашки, но и то, где она была в самом начале, то вы можете брать такой же порядок как у меня и получите тот же самый ответ.
Разный порядок в котором берутся черепахи.
Вот пример:
1,2,3 - черепахи. Если взять сначала 1 и вывести ее, буть будет "RR". Черепаха 2 выйдет из лабринта случайно. Потом взять черепаху 3, она даст путь "L". Итоговый ответ "RRL". Если же сначала взять черепаху 2, то она даст путь "R". Потом взять черепаху 3, она даст путь "L", потом черепаха 1 даст путь "RR" - итоговый ответ будет "RLRR".
Ясно, надеюсь, почему наши решения дают разный порядок перебора черепах?
Почему? Сначала были черепашки (1,1), (1,2), (1, 3). Путь для первой переместил ее в выход. Вторая и третья стали (123,434) и (1,1). Если сохранять изначальные координаты и выбирать минимальную по ним, то дальше возмется та, которая была сначала (1,2) как в моем решении.
В обоих решениях порядок, в котором черепашки выводятся из лабиринта не влияет на корректность ответа. Он влияет на длину, но весьма неявно. Возможно, брать черепашку которая сейчас ближе всего к выходу - разумная эвристика. Но это не то что делает ваше или мое решение.
Вот:
Для уже вышедшей черепашки вернется пустой путь. 0 новых команд допишется к ответу.
Разговор был про длину ответа. Да, это "лишние" по сравнению с вашим решением вычисления, имено это мы и намеряли таймером. Но эти вычисления не влияют на длину ответа.
Да, но выкинуть эти лишние операции - не бесплатно. Надо черепашек сравнить, найти дубликаты и выкинуть их. Вопрос в том, какие вычисления займут больше времени. Я думал, что дубликатов не будет так много, что их поиск сделает все медленнее. Был не прав, но такие рассуждения имеют право на жизнь.
Блин, не в ту кнопку ткнул, извините. Посмотрите мой ответ ниже.
> расшифруйте что означает "изначальные координаты минимальны"?
Лексикографически минимальны. Минимальный x, а при них равных, минимальный y. Чтобы порядок обработки черепашек был одинаковый.
Поэтому, если черепашка случайно выйдет из лабиринта из-за путей для других черепашек, она так и останется в клетке выхода. А дальше FindPath из клетки выхода в нее же вернет пустой путь. Не надо никаких дополнительных условий.
Допустим, что в наших решениях черепашки перебираются в одинаковом порядке.
У вас:
1) Составили путь, выводящий черепашку 1.
2) увидели, что черепашка 3 "наехала" на черепашку 2 и удалили ее.
3) Составили путь, выводящий черепашку 2.
У меня:
1) Составили путь, выводящий черепашку 1.
2) Составили путь, выводящий черепашку 2.
3) Когда обрабатываем черепашку 3, получаем, что она в конце после ApplyCommands. А она в выходе, ведь она когда-то в процессе "наехала" на черепашку 2, а путь для черепашки 2 мы выше уже составили. Дописываем в ответ пустой путь, фактически выбрасывая черепашку.
Не совсем. Я перебираю всех черпашек, прикладываю к ним команды, но, если черепашка вышла из лабиринта, она считается вышедшей. Так ApplyCommands завершается, если черепашка ступила на выход. У вас, кстати, тоже. Потом достраивается пустой путь из конца в конец и никаких новых команд в ответ не добавляется. Поэтому из этих N*M путей некотрая часть будет пустой - для всех черепашек, которых ваше решение выкидывает по пути.
Если вы в вашем решении из множества еще живых черепашек будете брать не первую, а ту, у которой изначальные координаты минимальные - ваше решение выдаст в точности тот же ответ, что и мое. Они эквивалентны.
2 часа - потому что тесты прогоняются 1000 раз подряд. Кстати, поэтому точность в наносекундах. Общее время замеряется в микросекундах, но там 1000 прогонов. Значит один занимает это же самое время, но в наносекундах в среднем.
Если отключить всякий вывод и заменить 1000 в коде на 1, то выдает вот такой результат на вашем 810x410 лабиринте:
Clever algo took 280255us Naive algo took 3586856us
Да, на вашем лабиринте ваша оптимизация сработала очень хорошо. Примерно раз в 12.
Если лабиринт попроще, то разница будет сильно меньше.
Разница по количеству команд в решении обусловлена не какими-то свойствами алгоритма, а везением. Мой алгоритм перебирает черепашек в одном порядке, ваш - в другом. И этот ваш порядок принципиально не кажется чем-то лучше.
Но, в целом, признаю вашу правоту. Оптимизация действительно срабатывает сильно лучше, чем мне показалось на маленьких тестах.
Просто продайте свой дом у моря, какие проблемы, да? Кому продать-то? Ихтиандрам?
Во-вторых, а их там ждут в этих местах, где более благоприятные условия? Миллиард беженцев - не самое приятное для цивилизации событие.
Главное отличие, что тогда не было человеческой цивилизации. Как кто-то отлично сказал "Планета в порядке. Это людям кранты". Можно очень резко и сильно изменить климат и вряд ли биосфера вымрет. Ну, будет очередное массовое вымирание, их было куча. Вот только быть часть этого вымирания никто не хочет.