Привет, Хабр! Меня зовут Игорь Батулин, я руководитель группы разработки виртуального хостинга в Рунити. Эта статья — не просто рассказ о том, как я люблю рогейн, а пример того, как можно за несколько итераций и в условиях ограниченных ресурсов создать полезный инструмент, действительно помогающий команде принимать решения. Мой рассказ также подскажет, как можно применять Agile-подходы в реальных задачах.
Навигация по тексту
Четвертая итерация («спринт 4»): добавляем параметры на картинку — FAIL?
Седьмая итерация («спринт 7»): поиск замкнутого не пересекающегося маршрута
О рогейне
Я с семьей уже лет 10 лет увлекаюсь спортивным ориентированием в варианте «рогейн». Это командный вид спорта, сочетающий стратегию и тактику, навигацию на местности и физическую выносливость. Рогейн и другие мероприятия проводятся в рамках туристического слета. Это когда в живописный лес приезжают 300–500 человек с палатками и живут там 2–3 дня как в туристическом лагере. За это время проводится комплекс семейных соревнований — гонки на катамаранах, лазанье по веревке, стрельба в тире, преодоление скалодрома, гонки на беговелах.
Но меня больше всего увлекает сам рогейн. Это двухчасовой забег с картой по пересеченной местности. Тут важно всё: и стратегия, и физическая подготовка, и умение ориентироваться. Обычно бежит группа (семья), и часто с детьми.
За час-два до забега нам выдают карту местности с отмеченными точками для поиска. Каждая точка оценивается в определенное количество баллов. Участникам нужно разработать маршрут для забега. Выигрывает тот, кто наберет больше баллов в своей категории (например, семья с детьми 6-9 лет). Младшему участнику (которого часто тащат на руках, если он устает) навешивается чип. Так что, помимо маршрута, надо еще хорошо бегать, носить груз, уметь ориентироваться и искать точки.
Получаются три условные соревновательные части, комбинация которых позволяет достичь хороших результатов и преимуществ команды:
интеллектуальная, где нужно составить наилучший маршрут по карте;
спортивная, где нужно пробежать — чем быстрее, тем лучше;
ориентирование — найти такие, часто замаскированные, точки.
Больше всего меня интересует «интеллектуальная» часть, когда надо спроектировать маршрут, продумав все моменты: где возникнут проблемы поиска, как лучше двигаться, сколько точек получится найти, какое расстояние удастся пробежать и какие варианты, если не успеваем. И здесь есть немного Agile, особенно в части завершения маршрута. Ведь проектируя, ты не можешь точно оценить, сколько времени и сил займет маршрут, поэтому для завершающей трети пути нужно иметь 3–4 варианта для разных условий: не хватает времени, не хватает сил, осталось время и силы, остались силы.
Обычно маршрут составляют «на глаз»: рисуют варианты, считают баллы и расстояние. Более продвинутые участники пользуются булавками и ниткой — втыкая булавки в точки и натягивая нитку (он же маршрут), либо вообще курвиметрами и аналогичными приборами. Вероятно, есть и другие методы, но мы не интересовались.
Вообще, мы с семьей бегаем для удовольствия, всё равно до результатов спортсменов нам далеко.
Пару лет назад получилось так, что я не смог участвовать в очередном рогейне. Но мне всегда очень нравилось разрабатывать маршрут, и я хотел помочь с этим. Мы договорились, что ребята из нашей команды скинут мне фотку карты, а я помогу им составить маршрут. Обычно на подготовку и проработку маршрута дается два часа: в 10:00 команды получают карту, а в 12:00 начинается старт.
До соревнования было еще несколько дней, и я задумался о поиске маршрута не вручную, а с помощью компьютера. Понимал, что уже наверняка существуют такие готовые инструменты и приложения, возможно, даже бесплатные. Но быстрый поиск показал, что конкретно того, что нужно мне, нет, либо это не совсем то, что нужно. Но мне была интересна задача и самому хотелось решить ее, тем более здесь предполагалась еще и польза — немного поизучаю новый язык. Так я приступил к разработке, затрачивая по паре часов в свободные вечера. Как всегда, работал по излюбленному Agile-принципу.
Что такое Agile и предыстория моего проекта
Начав писать статью про Agile, я понял, что надо бы снабдить ее хорошими, понятными примерами. И как раз один из них разросся в этот самостоятельный материал.
Agile — итеративный последовательный подход в разработке (да и не только), при котором идет постепенное движение к итоговому варианту небольшими приращениями. Цели и задачи могут сильно меняться в процессе. В этом формате я разрабатываю ПО уже более 20 лет.
Кратко, как это выглядит: я вношу небольшую правку и смотрю, как она поменяла функционал, заодно тестирую. В любой момент могу поменять как решение, так и саму задачу, иногда даже цель. Обычно мог менять задачу в больших пределах. Уже не помню, почему так сложилось, но либо заказчики доверяли мне, либо я не соглашался на другие проекты. Может, потому что я часто был в роли менеджера проекта, владельца продукта — сам координировал и определял работы. Хотя у меня был опыт постановки ТЗ и управления командой, я и сам обычно реализовывал ключевую (или просто интересную) часть. В душе я всегда оставался разработчиком, поэтому мне всегда было интересно делать что-то руками и видеть результат своих трудов.
Во всех моих проектах (даже с командой из 30 человек) я следовал принципу Agile. Тогда это называлось итерационной разработкой и не было в фаворе — в приоритете был классический «водопад». Как только появился тренд на Agile, я сразу принял его, но рассматривал через призму своего опыта разработки. Понятно, что в Agile есть множество других элементов методологии, особенно для командной разработки:
выработка гипотез (мозговой штурм, кайдзен, RICE);
проверка (АБ-тесты, MVP, интерактивные мокапы, тестовые группы, опросы);
оценка (стори поинты, покер-планинг);
процессы («доска», дейлики, ретроспективы, груминг).
Но их пока не затрагиваю, про это будет отдельная статья. Здесь я решил остановиться именно на основах — «гибкости», и показать процесс на наглядном примере, но с некоторыми отличиями от традиционной разработки:
работу делает один человек (вместо команды разработчиков);
оценка и постановка задач тоже полностью собственная (а обычно это делает команда совместно с продукт-оунером);
спринты (итерации) размером от нескольких минут до пары часов (вместо традиционных недели-двух);
клиентам не показываем промежуточные результаты, так как клиент — я сам, и могу оценить большинство моментов самостоятельно.
Конечно, можно масштабировать мой пример до группы разработчиков, но получившиеся искажения сильно помешают пониманию.
Цель и что хотел получить в идеале
Я представлял свое решение в виде мобильного приложения — фотографируешь карту, а спустя несколько секунд рисуется оптимальный маршрут. Это в идеале. Но целью было более наглядно и удобно получить несколько вариантов решений.
При этом я знал, что для полноценной реализации у меня не хватило бы времени и сил. Потому решил делать что получится за ограниченное время, либо пока не пропадет мотивация.
Тут следует отметить, что в реальных проектах, особенно поискового типа (новый продукт или новая функциональность) у продакт-менеджеров, UI-дизайнеров и маркетологов всегда есть сомнения. Часто они не могут выделить много ресурсов — людей, времени, бюджета — на проверку гипотезы или апробацию продукта. Для этого обычно ищут кратчайшие пути, чтобы, по принципу Парето, за 20% усилий сделать 80% функционала и проверить свои предположения. Так, чтобы урезать «идеальный» функционал, требуется хорошая работа менеджеров, аналитиков, архитекторов, тимлидов и техлидов. Ведь решение должно быть масштабируемое, расширяемое, и его компоненты должны легко заменяться полноценными, если в итоге проект «выстрелит», и бизнес «даст добро» (точнее, выделит ресурсы) на его полноценное развитие. |
За 12 лет работы в коммерческой продуктовой разработке вижу, что примерно половина проектов развивается таким путем. Я очень люблю этот подход — и решил делать так же. До соревнований оставалась неделя, а у меня было несколько свободных вечеров. Сколько успею — столько успею, но минимальный рабочий продукт должен быть всегда. Он будет просто постоянно улучшаться. Мысленно я для себя зафиксировал следующее:
декомпозировал задачу;
определился с вариантами MVP;
определил критические функции;
продумал варианты упрощения, если что-то не будет получаться.
Исходными данными должен быть файл — фотография карты и параметры настроек (сколько баллов нужно, сколько пробегает команда, добавлять ли в маршрут сложные точки и др.). Я рассматривал разные варианты реализации, например:
мобильное приложение с фотографированием на WebView (нативный вариант даже не рассматривал ввиду сложности);
веб-сайт, которым ограничусь в более простом варианте (если не успею с приложением), куда будет загружаться карта с выбором настроек в HTML-форме — фактически только внутренности WebView для приложения;
Telegram-бот с похожей логикой;
офлайн-программа (в более простом варианте), в которую передаются файл, параметры и генерируется ответ — перечень точек текстом или картинка.
В любом случае последний вариант всё равно пришлось бы делать, чтобы интегрировать в вышестоящие «обертки». Эти все варианты были совместимые.
Такой модульный подход я использовал всегда. Все предыдущие хобби-приложения реализовывал в виде модульных программ и скриптов на хостинге, к которым уже подключались:
сайты;
боты в Telegram/Discord;
роботы-парсеры;
мобильные приложения с интерфейсом в WebView;
обработчики еmail и Google-форм;
сторонние API типа ChatGPT.
Кстати, тогда ChatGPT и прочие ИИ были еще в зачаточном состоянии и ошибались даже в примитивной математике. У меня и мыслей не было, что он сможет сам всё обработать. Единственное, тогда я экспериментировал с его API для классификации текстов по категориям, например, когда писал бота для анализа денежных трат. Сейчас, вероятно, возможен полный цикл: от распознавания картинки карты и сбора рекомендаций до поиска и отображения маршрута. Или даже лучше — если ИИ напишет готовую программу, которая будет всё это делать.
В этом проекте я понимал, что в процессе всегда столкнешься с каким-нибудь «подводным камнем», который затянет очевидную часть задачи на порядок и выше. Для меня такими проблемами представлялись:
эффективный алгоритм поиска оптимального маршрута — сложная математическая проблема, не решаемая пока точно для большого количества точек;
«сканирование» и распознавание изображения в приложении — этого я еще не делал в приложениях, потому слегка пугало.
Но на этот случай в голове вертелось несколько вариантов приемлемой замены для сложных частей.
Первая итерация («спринт 1»): просто считаем
Обычно вся разработка по Agile делается итерациями. Их сейчас называют спринтами. Но тот же Стив Макконнелл (программист и автор руководства «Совершенный код») в старых версиях своей книги называл их просто итерациями. И я сохраню этот термин, так как, на мой взгляд, итерация подразумевает только одну правку. Современные методологии, типа Scrum, стали «напихивать» в спринт кучу задач, подменив само понятие и суть итеративного подхода. Именно поэтому я буду использовать «итерации», хотя по сути это будет соответствовать спринту (и будет меняться существенная часть продуктового функционала).
Итак, поехали. В моем случае проект был простой, можно было даже не продумывать архитектуру, а сразу говнокодить писать код. Также можно было сделать маленький интервал между итерациями, а сами итерации — короткими (прямо как в TDD, только без тестов).
Важный момент для понимания: итерации — это не кусочки кода и функционала, а готовые сильно упрощенные версии работающего продукта. При этом версии продукта отличаются (пусть и слегка) от одной итерации к другой. И это не обязательно видимый для клиентов элемент — это может быть и внутренняя техническая часть, например, замена одной БД на другую. |
Между итерациями заказчик (в данном случае я) видел изменения функционала итогового продукта, что позволяло принять решение по дальнейшему движению далее, либо по доработке существующей части. У меня была старая карта с прошлого рогейна, и я решил на ней потренироваться. Терпения было немного (для бизнеса аналог «терпения» — количество выделенных ресурсов, а их всегда мало), потому надо было получить хоть какой-то работающий результат за одну итерацию (за вечер, час-два).
Решил, что для начала буду просто считать длину уже известного маршрута. Почему на первой итерации отказался от поиска оптимального маршрута? Во-первых, обычно делаю это с удовольствием, но тут была известная сложная алгоритмическая задача — сомневался, что сделаю алгоритм лучше готового или хотя бы на уровне. Потому решил, что в итоговой программе, скорее всего, буду использовать известный алгоритм. Во-вторых, поискав готовые решения, понял что идеального нет — надо выбрать и доработать подходящее. В-третьих, я ведь долго буду интегрировать в код, а это тянет на отдельную итерацию, потому лучше сделаю это позже (на каком-то следующем шаге).
Обращаю внимание, что при исследовании задачи я сразу понял, что быстро добавить алгоритм поиска не получится, потому отложил это на потом (декомпозировал задачу и вынес сложную часть на другой «спринт»). Это очень важный момент! В Scrum это делается чуть ранее: при оценке задачи (на планит-покере) или на декомпозиции, а изредка даже на груминге. В канбане часто это обнаруживают уже в процессе работы (и тогда выделяют отдельной задачей), либо совсем ранее — на этапе анализа и разработки архитектуры. |
Итого, принял следующие допущения на первый шаг:
программа скрипт — на входе номера точек, на выходе тоже;
перечислю сам перечень точек маршрута;
сканировать не буду, а вручную занесу в массив координаты точек с карты, например, отмерив их от угла листа в миллиметрах (грубо X и Y), и добавлю «вес» точки в баллах;
расстояние в метрах пока не нужно, пусть оно пока будет в условных цифрах — почитаю его геометрически, как корень суммы квадратов.
Так для первой итерации я пока не стал имплементировать вообще никакого алгоритма, а просто перечислил точки маршрута. В итоге получилось очень похоже на задачу из LeetCode: на входе — пара массивов чисел, на выходе — массив.
Примерно через полчаса «набросал» решение, которое в цикле считало параметры маршрута: длину и сумму баллов. При этом на написание кода ушло, наверное, минут 5, а остальную часть — отмерял точки (на карте, в миллиметрах), заносил в массив координаты этих точек и вес в баллах примерно в таком виде:
point X Y |
В каждой строке — запись информации об одной точке: координаты и номер. Сам номер точки, например «31», состоит из двух частей: первая цифра («3») — это сложность точки (то есть ее ценность для итогового балла), а вторая цифра («1») — просто номер по порядку. Хотя это и было избыточно для целевой задачи, но это было удобно для меня.
Обычно Agile-разработка идет примерно аналогично: добавляются части функционала, которые будут потом выброшены, но которые удобны в моменте. |
Такой формат входных данных мне был удобен для загрузки, тестирования и дальнейшей поддержки. Фактически он формализовывал протокол взаимодействия между частями программы, утверждал некий контракт (API). По итогу такие части могли разрабатываться отдельно и независимо, в разное время и даже разными разработчиками. Части приложения также можно было обновлять независимо. Уже более 20 лет я практикую модульную реализацию проектов: программы, утилиты, модули и микросервисы. Подобная концепция используется в Unix, когда атомарные программы делают что-то свое, а их объединение позволяет обеспечить огромную гибкость.
Здесь я подразумевал, что отдельная программа/сприпт/микросервис (а теперь, наверное, и ChatGPT) сможет из картинки карты сделать такой текстовый файл с точками. Вторая программа (или часть программы) — найти по файлу маршрут. А третья часть — отобразить итог красивой картинкой. Ну и «нулевая» часть обеспечит удобный интерфейс загрузки карты и выбора параметров.
Слегка доработав код, запустил его и получил расстояние в условных пикселях и сумму баллов. Это было уже что-то.
Вторая итерация («спринт 2»): проверяем
Получив абстрактные числа, я порадовался, но не долго. Нормально «поиграться» с этим не получалось, да и цифры были не наглядные. И я решил проверить свою логику по распечатке нашего прошлого маршрута. Обычно по итогам рогейна собирают чипы с участников и распечатывают «чеки» — там есть время, взятые точки, набранные баллы, когда на какой точке были и какие расстояния.
Сравнение с таким «чеком» показало бы, правильно ли я считаю. Потому еще около 15 минут потратил на внесение точек нашего прошлого маршрута. В итоге после запуска увидел знакомые 69 баллов. Расстояние, понятно, было в пикселях, вместо метров. Но визуально цифры выглядели пропорциональными, как будто всё нормально!
Итерация 2.1: масштаб
Посчитав пропорцией масштаб по первому отрезку, я поправил код, добавив коэффициент масштаба, и получил наш прошлый маршрут. Он совпал практически до метров, но были и ошибки — понял, что неправильно измерил на рисунке пару точек. Помимо этого, погрешность в миллиметрах на карте приводила к метрам в реальности. Ну это ладно, не так важно, главное — основа была готова. Но хотелось большего.
Третья итерация («спринт 3»): рисуем линии
В тот же день решил добавить графики. Как-то раньше я рисовал на картинках в какой-то библиотеке, и это было очень просто. Но ту библиотеку я не вспомнил, зато нашел другую. В качестве подготовки сфотографировал карту более-менее в прямоугольном виде и сохранил файлом. Пришлось еще несколько раз вращать рисунок в графическом редакторе, чтобы корректно совместить оси координат. Плюс пропорция опять поменялась.
В итоге по паре реперных точек (точки, на которых основывается шкала измерений) я выровнял графическую карту по точкам из массива. Но в файле их пришлось всё равно немного исправлять — фото в файле немного отличалась от того, что я измерил линейкой по бумажной карте. Это заняло время.
А вот дописать код с самим рисованием линий было делом нескольких строк и нескольких минут. Порадовало, что библиотека повела себя предсказуемо и нарисовала линии. Наконец, я вывел карту с ними на экран. Большим удивлением для меня стало то, что линии идеально попадали в нужные точки. Это показалось настоящей магией! Хотя тут, конечно, ничего удивительного. Единственное, в получившемся коде сделал линию потолще. На этой счастливой ноте день закончился.
Четвертая итерация («спринт 4»): добавляем параметры на картинку — FAIL?
На следующий день решил быстренько добавить на график значения суммы баллов и расстояния, чтобы было удобно отправить друзьям картинку в мессенджер без какого-либо пояснения. Это казалось просто и красиво. Очень хотелось показать ребятами, что работа идет. Но часа два я провозился со шрифтами, кодировками, размером, толщиной текста — это как раз был непредсказуемый «подводный камень».
Причина — неудобная библиотека. Но менять ее уже не хотелось, потому что графики рисовались уже в ней. В итоге даже пришлось отказаться от подписей на русском языке, а сделать по-английски (какая-то проблема с TTF-шрифтом, которую можно, конечно, решить, но жалко времени). И вот я увидел на изображении две надписи: расстояние в метрах и сумму баллов. В этот день я уснул расстроенный — почти 2 часа потратил на какую-то ерунду.
Пятая итерация («спринт 5»): распознавание — FAIL
На этот раз я решил по фотографии распознавать круги с точкой внутри, указывающие на пункты. Также надо было читать номера пунктов (вес в баллах), написанные рядом. Знал, что существует множество готовых библиотек для этого, в том числе таких, для которых требуется предварительное обучение, но которые лучше находят результат. Попробовал несколько таких, но застопорился на распознавании цифр — круги с точками библиотеки находились хорошо, а вот с цифрами была совсем засада. Я понял, что если цифры понадобится вводить руками и сопоставлять с координатами, то это упрощения мне не даст. Возиться с библиотеками, дополнительно их переобучать и надеяться, что карта сильно не изменится к новому соревнованию — такое себе. В итоге потратил целый вечер, но решил, что делать этого не буду. Ну, или пока не буду.
Шестая итерация («спринт 6»): поиск перебором — FAIL
К вопросу графики я решил больше не возвращаться, тем более была более интересная и полезная задача — поиск маршрута. Такие задачи относятся к классу NP-hard (которые не решаются за разумное время), в то время как для небольшого количества точек решение находится полным перебором. Но с ростом количества задача усложняется, и даже мощные суперкомпьютеры не могут их точно решить за приемлемое время. На современном компьютере типовые алгоритмы предлагают быстрые решения для 15–20 точек.
Мне казалось, что этого мало, ведь на карте 35 точек, а хотелось получить «идеальное» решение. Тем не менее для теста хватало бы и типового алгоритма. Но, прежде чем брать готовый метод, я решил попробовать обычный перебор. Быстро понял, что даже для семи точек надо перебрать 35*34*33*32*31*30 вариантов, и это будет очень медленно (а типовой маршрут был на 15–20 точек). В итоге сделал с перебором. Остановился на 5–6 точках, и это было катастрофически медленно. Требовалось более эффективное решение.
Седьмая итерация («спринт 7»): поиск замкнутого непересекающегося маршрута
Поразмыслив, понял, что надо решить две алгоритмических подзадачи. Наверняка, полноценный эффективный поиск решает эти подзадачи совместно, но мне было проще решать по отдельности:
отбор 15–20 точек, которые планируется посетить;
поиск оптимального маршрута для этих точек.
Что касается первого этапа, то здесь я решил пока так и оставить, когда точки маршрута задаются мной вручную, а сам отбор сделать в следующей итерации. Такое допущение позволило настраивать и тестировать остальные части приложения. Потому я занялся вторым алгоритмом.
Изучив предлагаемые варианты, достаточно быстро выбрал приемлемый алгоритм для построения оптимального маршрута по указанным точкам — это метод 2-opt (подробнее о нем смотрите здесь). Алгоритм работал следующим образом:
вначале из точек строил замкнутую линию, например вида 1-2-3-4-5-6-7-1;
далее брал любое пересечение линий пути и устранял его, переставляя порядок посещения точек.
В итоге после нескольких циклов получалась некая замкнутая непересекающаяся линия. Алгоритм был эвристическим и искал локальный минимум. Но практически не достигал оптимума всего на 1–5%. Я посчитал это достаточным. Закодировав алгоритм, убедился в его работоспособности — маршрут рисовался из произвольного набора точек. Это выглядело очень неплохо.
Восьмая итерация («спринт 8»): выбор точек
Стоит заметить, что алгоритм 2-opt, выбранный на предыдущем шаге, лишь искал маршрут через указанные точки. Но прежде чем начать поиск оптимального маршрута, надо выбрать сами точки, которые мы хотим посетить. На карте всего 35 доступных точек, а надо выбрать 13–15, в которые мы успеем. Понятно, что спортсмены пробегают все 35. Но мы с детьми (особенно неся их на спине под конец маршрута) не особо быстрые, потому наш маршрут ограничивается 10 км за 2 часа (с учетом поиска точек), а реально — вообще 6–7 км. Кажется, мало, но это потому что поиск съедает львиную часть времени. В один из первый рогейнов мы искали одну точку 40 минут! Понятно, что их поиск на местности тоже можно оптимизировать, но это совсем другая задача.
Обычно мы двигаемся в определенной локации, и чаще всего маршрут напоминает овал или круг. Но это всё эвристика, а хотелось научное точное решение. В любом случае, зная, что мы пробегаем не более 10 км в идеале, я понял — надо брать в расчет точки только в 5 км от старта (ведь нам надо вернуться на точку старта). А реально, скорее всего, вообще в круге 4 км, так как оптимальный маршрут вряд ли будет по прямой. Это упрощало задачу. Выписал точки, лежащие в этом круге, но их получилось всё равно много — 25 штук.
Все-таки, как отобрать точки для посещения? Надо было как-то «отбросить» лишние 10. Изучать теорию было долго — несколько часов, что никак не укладывалось в итерацию. Потому до поиска нормального алгоритма я решил пойти эмпирическим путем. Самый примитивный вариант, который лез в голову — это 10 раз исключить по какой-то точке. Но оценка количества вариантов не давала оптимизма. Получалась классическая комбинаторная задача: C(25,15) ~ 3 млн вариантов. Учитывая, что по каждому варианту потребовалась бы еще 2-opt оптимизации для поиска расстояния, то было совсем грустно.
Тогда я решил упростить. Вручную исключил сложные и неудобные точки (их сразу выбрасываем), а также вручную добавил те, которые точно хотим посетить (которые не надо выбрасывать). В итоге осталось выбросить 3–4 точки — а это уже решил перебором.
Как это работало? Из исходных частично вручную отобранных 19 точек алгоритм отбрасывает 4 и считает оптимальный маршрут. Потом опять возвращается к 19 точкам и отбрасывает 4 другие и так же аналогично. В итоге программа работала достаточно быстро и выводила подходящие маршруты. Но замечу, что при этом перебиралось почти 4000 вариантов. Если выбрасывать 3 точки, то количество вариантов для перебора уменьшалось на порядок. Осталось отсортировать рассчитанные варианты по количеству баллов и длине, выбрать тройку лучших, сделать их картинки и скинуть на рассмотрение в команде. Напомню, что это было еще до старта соревнований, и я отлаживал код на карте забега прошлого года.
Как говорят, «хорошо было на бумаге, но забыли про овраги». Гипотеза была хорошая, но оказалось, что моя реализация работала быстро лишь до 10–11 точек. Этого не хватало даже до нашего типового маршрута в 15 пунктов! Требовалось что-то улучшить. Потому я решил — лучше начать с оптимизации алгоритма.
Девятая итерация («спринт 9»): кеш расстояний
Посмотрев на код и частично отладив его, понял, что очень много времени тратится на расчет расстояния между точками (через корень от суммы квадратов). Причем одни и те же расстояния считаются десятки и сотни раз. Тут решения были очевидны: либо рассчитанные заранее расстояния, либо кеш. Я пошел по второму пути — через кеш. Когда функция обращалась к подсчету расстояния, она искала вначале в кеше (ассоциативный массив с двумя координатами и расстоянием). А вот если точки в кеше не было, то функция считала и сохраняла в кеш. Пошло быстрее.
Алгоритм быстро считал уже до 14–15 точек, отобранных из 17. Понятно, что можно было бы его еще немного ускорить, используя обычный массив и предварительный расчет, но было жалко времени, а выигрыш казался незначительным. Несмотря на улучшения, я добавлю максимум еще 1–2 точки к расчету, а мне хотелось больше. Так что это оставалось подходящим только для нормального алгоритма, а не для моей эмпирической поделки.
Итерация 9.1: проверка на известных результатах
Когда я задавал точки вручную, уже сразу подумал, что можно использовать наши прошлые маршруты с прошлогодних соревнований. Когда сделал поиск маршрута, то сразу захотел проверить наши старые маршруты, и каково было мое удивление, когда в итоге обнаружил еще более оптимальный и короткий вариант для наших точек! Вариант конечно был слегка сомнительный — требовалось бежать через лес без ориентиров, но путь был точно короче.
Я пошел дальше — у меня вообще возникли сомнения, что мы выбирали тогда наилучшие точки для посещения. И точно! Добавив несколько соседних точек к перебору и запустив свой код, нашел еще 3 маршрута, которые либо набирали больше баллов, либо были короче. Предварительный анализ показал, что среди них был один вариант точно лучше нашего — с удобными ориентирами, более короткий, и был на 1 балл больше. А мы его тогда проморгали. Это меня окрылило. Программа работала! Скинул ребятам карту с маршрутом и расчет, мы обсудили. Все согласились, что это действительно был хороший вариант, которого мы не заметили в прошлый раз!
Итог и реальная работа
К сожалению, дальше у меня были другие дела и не хватало свободного времени дорабатывать программу. Потому к соревнованию она осталась в вышеуказанном виде. Меня больше всего смущало, что я не подобрал нормальный алгоритм и не встроил его в программу. Оценочно, на это нужен был минимум целый день (мои условные 4 итерации по 2 часа). Также очень хотелось бы, чтобы программа распознавала точки, и не надо было их координаты вводить руками. На это тоже нужен был еще минимум день. Этого времени не было. Но текущая эмпирическая упрощенная версия все-таки работала, и была надежда, что она поможет.
Когда началось соревнование, ребята скинули мне фотографию карты. Я загрузил карту в программу и внес вручную те точки, что были в радиусе 5 км от точки старта и финиша. Опять-таки точек оказалось слишком много, пришлось исключить заведомо неподходящие.
По итогу — программа построила несколько вариантов маршрутов. Один из них был близок к тому, что ребята спланировали вручную самостоятельно параллельно. Я скинул им картинки ближайших похожих вариантов с расчетами, и ребята чуть скорректировали свой маршрут. Конечно, они взяли тот, что был очень похож на их вариант. Но при похожей длине и сложности (по сравнению с их маршрутом), мой вариант выигрывал 2 балла! Это было существенно. Были и другие — лучшие варианты, которые давали либо сокращение пути, либо дополнительные баллы. Но ребята уже были не готовы их анализировать и перестраиваться на них, потому что при разработке пути нужны не только длина маршрута и количество баллов, но и ориентиры, дороги, местность, сложность поиска точек и многое другое. Это долго и сложно. Перепланировать всё для совсем нового маршрута уже не хватало времени. В забеге они пробежали маршрут, пропустив лишь одну точку — не смогли её найти. Предполагаю, моя работа добавила к их результату 2–3 балла!
Что далее?
Рогейны проводятся 2 раза в год — в конце весны и в начале осени. Обычно мы участвуем в обоих, но последнее время пропускали. Теперь мы побежим опять, только в новой категории — «малышок, от 0 до 2 лет», а, может, и в категории «многоножки, от 3 детей и более» 🙂.
Что касается приложения, то планирую его дорабатывать. Раз уж все интерфейсы и протоколы взаимодействия разрабатывались гибко, я хочу опять что-то доделать, чтобы улучшить функционал. Вероятно, это будет что-то из перечисленного:
распознавание картинки;
Telegram-бот;
веб-сайт;
мобильное приложение.
Возникает вопрос: как, например, в Telegram-боте сделать всё по Agile-методу, последовательно, итерациями, но чтобы без распознавания картинки? Думаю, будет запрашиваться карта и вручную отмеренные на ней точки текстовым списком. Неудобно, да. Но зато это быстро сделать, и всё будет работать.
Потом можно «прикрутить» распознавание и всё остальное, что захочется: хоть отправку по email или push-уведомление в мобильном приложении, когда посчитает маршруты. Ну и нормальное решение алгоритмом — надо учесть, что по лесу бежать на ~70% тяжелее, а по дороге на ~50% легче, да и то, что точки искать удобнее у ориентиров. В общем, перспектив для развития много!
Выводы
В результате за ограниченное время я создал готовый рабочий инструмент, который:
помог команде оптимизировать маршрут;
показал инсайты (наши прежние маршруты не оптимальные);
спроектирован так, чтобы легко расширяться (интерфейс, алгоритмы, графика)
создан в короткие сроки (по моим оценкам, за 10–14 часов);
показал важность Agile-подхода в задачах с неопределенностью.
Важно не только правильно писать код, но и эффективно достигать целей. Работая пару лет в сфере информационной безопасности, я понял, что там нет абсолютно правильного решения — всегда есть оценка рисков и выбор одного из вариантов: предположительно оптимально сбалансированного.
Для разработчиков обычных программ и приложений также важен баланс продуктовой и технической части. Многие этого не понимают, когда делают «строго по ТЗ», а значит теряют гибкость и эффективность. Более того, бизнес часто не доволен результатом, так как контекст у всех разный (менеджеры думали одно, когда составляли ТЗ, а разработчики прочитали его по-другому и реализовали другое). Даже часто на уровне терминов и понятий. И Agile в этом случае — инструмент снижения рисков, издержек, особенно для сложных непонятных проектов, когда часто меняется бизнес-логика и задачи.