Мудрый человек не тот, кто много знает, а тот, кто знает, где использовать.

Привет, меня зовут Валерий Антонов, я руковожу направлением Java в Уральском банке реконструкции и развития (УБРиР). Сегодня расскажу, как я смог переложить систему алгоритмов на, казалось бы никак с этим не связанное хобби, - рыбалку.

Проблема

Сидел долгими зимними вечерами у камина, глядел на всполохи огня, похожие на солнечных зайчиков, и вспоминал летние рыбалки... Ляпота... Но где-то в глубине сознания червячок сомнения точит подкорку вопросами о прошедшем Performance Review. Вспоминаются слова коллег про раздел PR c вопросами про алгоритмы. Их спичи были примерно такими:

• Это всё справочная информация!

• Всё это хранение красных резиновых шаров!

• Зачем мне это? 

• Зачем мне захламлять чердак?  

Действительно, когда и какой алгоритм вы учили и применяли последний раз? Десять лет назад на подвластном мне игровом сервере стрелялок-бродилок я реализовывал один из старейших алгоритмов машинной графики, алгоритм Брезенхэма (название я вспомнил, только перекопав интернет). Может, сейчас уже нет места подвигу? Может, ну его, лучше про рыбалку…

Итак, поехали...

Вернее, нет. Пока не поехали. Нужно понять в какую сторону ехать и кого мы будем ловить. Желательно, недалеко от города, ибо ехать далеко лень.

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

Читаем спортивную интернет-прессу. Много букофф... Ищем слова «соревнования» и «рыбалка». Глаза бегут по строчке, выхватывают буковку «с». Вторая не «о», тогда переходим к следующему слову. Стопэ, как говорил мой бывший коллега, указывая на остановку какого-либо процесса в памяти и передачу управления центральному процессору. Это же алгоритм линейного поиска. А как ускорить поиск?

Наденем очки. Теперь мы сможем периферийным зрением охватывать большую часть строки. Мозг выполнит предварительный расчёт смещения, отправит фокус глаз на несколько слов вперёд, пропуская неподходящие. Так ведь это алгоритм Кнута-Морриса-Пратта или, может, Бойера-Мура. 

Тут алгоритм закончил свою работу, вернув индекс найденного вхождения искомой подстроки. В эти выходные соревнования в Парке Победы. «Ротан белых ночей». Ротан? Who is it? I`s Perccottus, рыба рода головешковых, его единственный оставшийся в живых представитель. И тут у меня в голове такой диалог:

– Если он единственный из ныне живущих — жалко его.

– А это соревнования по принципу “поймал-отпусти”.

– Отлично. Совесть пошла отдыхать дальше на диванчик в тёмном углу комнаты.

Есть ли ротан у вас в городе? Наверняка, если у вас есть старые заросшие пруды без течения. Ареал распространения рыбы очень большой. Хищник! Жрёт всё, что шевелится. Проблем с аппетитом нет, от слова “совсем”.

Сборы на рыбалку – это отдельная тема. Супруга никак не может понять, почему у меня на это уходит 2-3 часа, в то время как её сбор на концерт в лёгкой летней экипировке занимает не более полутора. Как мозг решает этот вопрос: какие приманки взять, а какие - оставить? Это сложный алгоритм со множеством неизвестных: ветер, освещение, мутность воды, атмосферное давление. Реализация алгоритма - это тайна, которую не каждый рыболов готов раскрыть даже своим друзьям. Известны только входные параметры — миллион приманок на входе и десяток приманок на выходе. Чёрный ящик какой-то. Алгоритм часто даёт сбои на тему “клёв был вчера и там, а не сегодня и здесь”. 

Ротан отлично отзывается на кусочки резиновых червячков, при этом цвет практически не важен. Кидаю в рюкзак дюжину разных пакетиков с искусственными червячками, в том числе, с разными запахами. А запахи - креветка, сыр, икра! Сам бы съел это чудо.

Вот и долгожданное утро. Погнали! Как поедем - по КАД, а потом по Московскому проспекту? Или по ЗСД (Западный скоростной диаметр), а потом по Бассейной? По ЗСД надо платить, но зато быстро, а по КАД бесплатно, но не быстро. Стопэ, это же задача о поиске кратчайшего. Ой, какой стопэ? Мы же уже на КАД. Автомагистраль. Остановка запрещена! Фух, пронесло.

Старт

Вот я и на месте. Собираю спин, регистрируюсь и стартую. Водоём, на котором проходят соревнования,  — это несколько небольших и разных по форме прудиков. Они разбросаны в Парке победы на Московском проспекте в Питере и соединены между собой сложной гидросистемой каналов и труб. Предсказать, где ротан будет лучше клевать, невозможно. По прудикам отдыхающие катаются на лодочках. Красота! Но у меня цель не отдохнуть, а опробовать максимально возможное количество мест и не устать.

Планирую свой путь: сначала к южному прудику, он самый дальний; затем к прудику у метро; потом к прудику с гранитной набережной. А, нет, последние два прудика посещаю в другом порядке. Так я пройду меньший путь и получу больше точек ловли. Стопэ, так ведь я только что применил алгоритм решения задачи коммивояжёра. Ай да я!

Прибегаю на очередную запланированную точку. Заброс в метре от берега, подыгрываю приманке, покачивая кончиком спиннинга. И раз, и два, и три. 

Ни тычка. Шаг в сторону, заброс и опять раз-два-три. Вроде процесс несложный. Или сложный? Мои действия складываются из двух циклов — смещения в сторону и цикла подёргивания вершинкой спиннинга. Ну это я знаю – сложность такого алгоритма равна O(n²).

То тут, то там потихонечку наполняю свою баклажку с водой ротанами. Пора двигать на финиш.

Турнир разбит на две части, в первой ловят на вес, во второй ловят на количество. Тут ещё и номинация на самого большого ротана. Пытаюсь опознать среди пойманных ротанов гиганта. Начинаю выкладывать своих из баклажки, по одному извлекая из горловины. Первый маленький, второй побольше — кладу справа, извлекаю третьего, он меньше второго, но больше первого. Вставляю его между двумя другими, повторяю эту процедуру, пока не отсортирую всех ротанов. Стопэ, так ведь это алгоритм сортировки вставками. Вот он где пригодился. Успешность применения алгоритма, однако, не позволяет победить в номинации на самую большую рыбу. Мой самый большой ротан даже визуально не дотягивает до полукилограммового красавца, пойманного победителем номинации. Вес пойманной мной рыбы далёк от первой десятки. Вся надежда на второй тур.

Стартую. Бегу, как и планировал раньше, на прудик с гранитным парапетом. Но там уже много моих коллег по увлечению. Где же встать - между этими двумя или между вторым и третьим? Или дальше - между третьим и четвёртым? Мозг лихорадочно прикидывает наиболее выигрышные с точки зрения рыбалки комбинации. Фух, аж вспотел!

Стопэ! Это ж какую трудную задачу я решил? Комбинаторика! Сложности задач комбинаторики могут доходить до O(n!), а это, как мы знаем, NP полные задачи, которые могут вообще не иметь решения! Какой мозг молодец - возьми с полки пирожок!

Долго статья пишется, да быстро время летит. Финиширую.

Итоги

Тур закончен, судьи подводят итоги. Вот финальные таблицы результатов. Каждый год всё больше спортсменов принимают участие в этом турнире. Итоговая таблица растягивается на несколько листов. Я, зная сумму мест по турам, пытаюсь определить, на каком листике может быть мой результат. Так, посмотрим. На первом листке последняя строчка с местом меньше моего. Смотрю на втором листке, последнее значение опять меньше моего... Эх как глубоко моё падение. Смотрю окончание третьего листка. О! У меня место меньше. Мой результат где-то на этом листе. Смотрю значения в середине листа, у меня снова значение меньше. Значит, я где-то вверху. Бью верхнюю половину ещё пополам и сравниваю со своим значением. Ага, опять выше. Ну вот, тут-то себя и нахожу.

Стопэ! Это чего же я сейчас сделал? Проверил граничные условия и применил алгоритм бинарного поиска! Вау! Такого я от себя не ожидал. Хотя, почему нет? Сложность у алгоритма небольшая, всего О(log n). Вся пойманная на турнире рыба отпущена обратно в свою родную среду обитания. Отличные призы!

А вот и победители в разных возрастных категориях.

Но как же так? Я проиграл даже детям. А ведь они будут учить алгоритмы только на втором курсе вуза.

Своё выступление не порадовало — пролетел мимо призов. Но встретил старых знакомых, получил кучу положительных эмоций и просто хорошо провёл время! Разве не этого мы ожидаем от рыбалки?

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

А отключу-ка я мозги и просто поеду домой по навигатору. Меньше думаешь — холоднее мозг. Без остановок! И никаких тебе алгоритмов! Увидимся на следующем PR.