Какой самый сложный алгоритм вы использовали в своей работе — рассказывают эксперты

Наверняка каждому программисту помимо привычных задач приходилось столкнуться с настолько сложным алгоритмом, что он надолго отпечатался в памяти. Спросили у экспертов о таких алгоритмах в их работе.

Какой самый сложный алгоритм вы использовали в своей работе?

Анна Славенко

разработчик ПО Тверского технологического центра Accenture в России

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

На одном проекте по разработке процессов ETL был реализован специальный фреймворк, обеспечивающий автоматизацию процесса разработки, по сути, Data Continuous Integration.

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

В результате фреймворк формировал многомерный массив, в котором, условно, каждый элемент – это номер некоторой задачи. Каждая задача имеет определенный вес, по сути являющийся производной величиной от порядкового номера задачи в очереди на выполнение. Каждая задача может содержать массив связанных с ней подзадач, от которых она зависит. Задачи могли выполняться параллельно и иметь общие зависимости. На выходе мы должны получить многомерный массив, в котором удалены «лишние» промежуточные зависимости. Элементы и связи между ними выводились в виде схемы.

Честно говоря, массив был огромен, а в сети зависимостей можно было запутаться, но у нас был план. Для построения алгоритма был выбран принцип транзитивности. Что это означает? Простыми словами: если Задача A зависит от Задачи B, а Задача B зависит от Задачи C, то и Задача A зависит от Задачи C. Или, если представить в виде соотношений, то мы имели на входе следующее:

A → B → C
A → D → C
B → D

Соответственно, на выходе мы должны были получить следующее:

A → B → D → C

Где символ → можно воспринимать как «влечет»

Сложно, но реализуемо. Из подручных средств были PHP, используемый в консольном режиме, на котором было реализовано ядро фреймворка, море энтузиазма и куча идей реализации, начиная от рекурсии и заканчивая array_intersect_key. В результате выбор был остановлен на рекурсии, как наименее трудозатратной с точки зрения реализации. Основная идея – отсортировать задачи по весу, номеру, а дальше рекурсивно брать элементы зависимостей и пробегая поочередно по оставшимся элементам основного массива, брать их зависимости и сравнивать номера с искомым значением.

Другой возможный вариант решения заключался в построении и отпимизации графов, но под рукой был только «голый» PHP и жесткий дедлайн. Но кроме нетривиальной задачи и неоценимого опыта, главное, что я вынесла — всегда можно найти хорошее, работающее решение, несмотря на ограничения в выборе инструментов и по времени.

Василий Демченко

руководитель отдела разработки и тестирования в NGRSOFTLAB

На заре карьеры мне поручили разработать алгоритм автоматического составления графика работы машинистов метрополитена.

Суть задачи – составить график работы поездных бригад с учетом обязательного перерыва на отдых. Если смена длилась больше 4 часов, то машинистам полагался 30-минутный обед в интервале от 2,5 часов до 4 часов с момента выхода на линию. Если же смена превышала 7 часов, то машинистов ожидал дополнительный 15-минутный отдых в интервале от 6 до 7 часов работы.

Во все предыдущие попытки разработать соответствующий алгоритм получалось распределить только половину рабочего времени. Оставшиеся «хвосты» нужно было обрабатывать вручную, поскольку алгоритм «давал» лишние бригады либо делал «неправильную» смену, по которой невозможно было работать.

Казалось бы, задача была простой: через 30 минут с начала обеда машиниста нужно было вернуть на линию. Однако вскрылась особенность работы метро: машиниста можно было вернуть только в тот же поезд, с которого он начал смену. И вот тут появилась проблема.

Из-за графика движения поездов продолжительность обеденного перерыва «плавала» от 25 до 33 минут в зависимости от времени и дня недели (час пик, будни, выходной), а также от отдельных линий метро. Помимо этого, обедать машинисты могли только на определенных станциях линии. При этом количество одновременно обедающих бригад также было ограничено, так как, пока основная бригада была на перерыве, составом управляла так называемая подменная бригада. А их было немного.

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

Первая итерация алгоритма насчитывала 300 строк кода, с множеством вложенных подзапросов для определения «границ» выборки. По результатам работы первой итерации выяснилось, что по такому расписанию работать невозможно, поскольку в бригадах – люди, а не роботы.

Дальнейшая оптимизация привела к увеличению количества строк кода до 900. Появилась тройная вложенность запросов, вложенные циклы, двойные курсоры, временные таблицы и самописные SQL-функции.

В результате получилось оптимизировать автоматическое составление графика работы на 80%. Оставшиеся 20% составляли «хвосты» смен, которые не позволяли создать полноценную смену для бригады, и их надо было распределять вручную.

Ближе к концу данной работы мне дополнительно поручили задачу автоматического составления графика работ маневровых бригад (это те бригады, которые садятся на конечной или предпоследней станции метро, заводят состав в тупик и выгоняют его обратно). Проблема этих бригад, помимо обеденного перерыва, была еще в продолжительности их работы: всего 2-3 минуты. Из-за этого появлялись накладки в считанные секунды, которые при неправильной настройке выдавали лишнюю 3-5-минутную смену в утренний или вечерний час пик.

Итогом работы стал «монструозный» SQL-скрипт, который был разбит на основную процедуру из 1200 строк кода и в котором многократно вызывались три дополнительные самописные функции по 50-150 строк кода, а также скрипт маневровых бригад на 700 строк.

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

ПО для автоматизированного составления графика работы позволило сократить количество часов, требуемых на создание нового графика, с 20-30 до 5-6, поскольку ранее данную работу делали вручную с помощью карандаша и ластика на листах формата А1. ПО было полностью внедрено в трех депо и начало внедряться еще в трех. В 2011 году произошла смена директора метрополитена, и проект закрыли.

Дмитрий Гордеев

программист в компании «Биржа грузоперевозок ATI.SU»

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

Например, у нас есть сервис, который отправляет уведомления о подходящих грузах согласно фильтрам, которые установил пользователь. Изначально там использовался сложный алгоритм с изменением типов (время, дробные числа и т.д.) для более быстрой операции сравнения, построением дерева и еще несколькими приемами. Оказалось, что на сопутствующие расходы тратилось много ресурсов и больше половины времени, отведенного на подбор списка фильтров, подходящих к грузу. Мы заменили сложный алгоритм обычным перебором, и в результате сервис стал работать в разы быстрее.

Дмитрий Зайцев

эксперт по разработке ПО компании «Рексофт»

В рамках работы в компании самые сложные задачи, которые приходилось мне решать, и часто не в одиночку, были связаны с логистикой. Один из них запомнился мне больше всего.

Это был проект для крупной компании-экспедитора, который осуществляет перевозку грузов различными видами транспорта между РФ и 150 странами мира. Главная задача экспедиционной компании − составить маршрут доставки, который удовлетворит клиента по времени и цене. Для этого используют мультимодальную перевозку. В процессе применяют два или более типов транспорта: автомобильный, железнодорожный, морской или авиационный. Обычно коммуникация идет по телефону или почте.

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

Все это усложнялось большим количеством международных компаний-перевозчиков, разнообразием тарифов у каждого из них и дополнительных наценок по каждому из направлений. Поиск был параметризован, что еще больше усложнило проблему. Поиск кратчайшего пути, где каждая точка имеет некий вес, это первое, что пришло нам в голову. Однако представьте, что в каждой точке есть еще набор динамических условий, чтобы их проверить необходимо выгрузить чуть ли не всю информацию из БД.

Мне пришла идея − для каждого тарифа можно выставлять оценку по нескольким критериям. Эти оценки пересчитывались при изменениях тарифов или каких-то глобальных условий, например, изменение НДС или наценок. Такой подход к оценке избавил от дополнительных просчетов во время каждого запроса. У любого тарифа было с десяток различных оценок, по которым можно было, например, сортировать или высчитывать итоговый вес. В конечном итоге нам пришлось еще очень долго работать над этой задачей по ряду других более приземленных причин. Тарифы от разных перевозчиков сводились к примитивным описаниям и сильно отличались друг от друга по структуре, их было просто невозможно формализовать. Для того, чтобы доставить товар из А в Б, надо еще заехать в С на другом конце света, т.к. там налоги меньше и лучше условия. В общем, это была очень нетривиальная задача для всей команды. Мы серьезно погрузились в бизнес-тематику заказчика, но и результат был отличный – мы создали платформу для первого в России цифрового экспедитора Agorafreight.com.

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

Напоминаем, что вы можете задать свой вопрос экспертам, а мы соберём на него ответы, если он окажется интересным. Вопросы, которые уже задавались, можно найти в списке выпусков рубрики. Если вы хотите присоединиться к числу экспертов и прислать ответ от вашей компании или лично от вас, то пишите на experts@tproger.ru, мы расскажем, как это сделать.