Линейное решение задачи с поездами
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization
По поводу моих улучшений. Немного поразмыслив, первая моя мысль - что с маятником тоже можно сделать маленькое улучшение такое же, как и базовое улучшение спидометра. Мы не каждый раз поворачиваем и идем в обратную сторону, а только тогда, когда меняем состояние встретившейся лампочки.
Во всех особых случаях, когда все лампочки либо включены, либо выключены, такое улучшение работает за время х2 от количества вагонов. И в среднем работает в 2 раза быстрее, чем оригинальный маятник, и примерно наравне с оптимизированным спидометром(чуточку хуже).
Но! Кажется на основе оптимизированного спидометра я придумал линейный алгоритм, дающий стабильно O(4n) для совершенно рандомных случаев и во всех особых случаях, когда все лампочки либо включены, либо выключены. И где-то О(8n) в худшем случае для конкретно этого алгоритма.
В чем суть. Для оптимизированного спидометра мы разрешали себе идти дальше, когда на очередном проходе на пути от начального вагона мы в первый раз встретили зажженную лампочку, но только до тех пор, пока не встретим еще одну единичку или не закончатся наши разрешенные шаги. А что если пойти дальше, даже после второй зажженной лампочки? Что если каждый раз когда мы встречаем такую лампочку, то разрешаем себе идти еще в 2 раза дальше? Прям каждый раз. Встретили зажженную лампочку - погасили и может идти дальше на столько же вагонов, сколько мы прошли от начала до только что погашенной нами лампочки. По факту, мы идем вперед всегда, пока нам встречаются зажженные лампочки и мы не уходим слишком далеко от последней погашенной нами. Тогда существует всего 2 варианта - рано или поздно мы погасим начальную лампочку или последняя погашенная не была начальной, но мы так и не дошли до следующей зажженной до того, как истекли наши разрешенные вагоны.
В первом случае мы просто пройдем лишний круг и вернемся обратно. Таким образом пройдя 2 лишних круга.
Во втором случае мы идем обратно и проверяем, была ли последняя выключенная нами лампочка той самой начальной. Если не была, то снова начинаем идти вправо, пока не наткнемся на зажженную лампочку.
Таким образом, если зажженные лампочки достаточно часто встречаются, то мы идем в один проход до конца поезда, потом еще удвоенную его длину и обратно. Получается, что нам понадобится 4 длины поезда, чтобы посчитать количество вагонов.
Но есть у такого алгоритма худший случай. Тогда, когда зажженные лампочки стоят ровно на один вагон дальше, чем нам разрешено пройти. Пример: зажженная лампочка находится в 3-м вагоне. После того, как мы ее погасили, нам разрешается идти еще 2 вагона и искать там зажженные лампочки. То есть последний вагон, который мы можем посмотреть на этой итерации - 5-ый. А вот следующая зажженная лампочка будет в шестом. И мы могли бы всего на один вагончик вперед пройти и встретить ее, но согласно алгоритму мы должны вернуться к изначальному вагону. Если после шестого вагона лампочка будет в 12-м, то мы обязаны будем вернуться назад и снова пройти вперед до 12-ого. И так далее. Думаю, суть вы уловили.
Так вот на таких данных сложность повышается до примерно О(8n). Эту чиселку вывел совершенно экспериментально. Возможно знатоки математики и теории алгоритмов выведут более точную зависимость. Чему я очень буду рад)
Вроде бы звучит разумно и тесты все проходятся прекрасно. И сложность на первый взгляд линейная во всех случаях, что не может не радовать.
Прикреплю в комменты полный файл со всеми сравнениями. Но вот ссылка на годболт кому будет так удобнее.
Критика и замечания приветствуются.
Improve yourself. Stay cool.
#fun #optimization