Снова сравниваем решения задачи с поездами

Кто забыл или не в теме, вот эта задача. В прошлом мы уже сравнивали два решения: условный маятник и спидометр. Лучше освежить в памяти контекст, чтобы понятнее был предмет разговора. Однако наша подписчица @tigrisVD сделала несколько улучшений алгоритма спидометра. Вот ее сообщение с пояснениями и кодом.

Первое - базовое улучшение. Вместо того, чтобы возвращаться назад на каждом шаге(что очень расточительно), мы возвращаемся назад, только, если встретили единичку и поменяли ее на ноль. Только в этом случае мы могли поменять самую первую лампочку.
Это уже улучшение уполовинило количество шагов. И сравняло его с маятником.

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

Там есть некоторые проблемы с тем, что оптимизированные алгоритмы спидометра зависят от входных данных. И в худшем случае, когда в поезде включены все лампочки, последний оптимизированный алгоритм работает лишь в 2 раза лучше базового спидометра. В лучшем случае, когда все лампочки выключены - сложность алгоритмов линейно зависит от количества вагонов, а не квадратично, как у базового спидометра. Базовое улучшение - нужно пройти всего х2 от количества вагонов. А оптимизированный вариант- х4(я там одну ошибочку нашел в коде при подсчете пройденных вагонов, поэтому не в 3, а в 4). Но в рандомных случаях оптимизированный вариант примерно в 2 раза быстрее базового улучшенного и в 4 раза быстрее оригинального спидометра.

Позапускать ее код и посмотреть на цифры можно тут

Спасибо вам, @tigrisVD, за такие интересные решения!

Но ваши улучшения натолкнули и меня на размышления и улучшения, о которых я расскажу завтра.

Impove yourself. Stay cool.

#fun #optimization