Конкурс хеш-кодов Google – 2017

В этом году был четвертый выпуск конкурса Google Hashcode. Соревнования по кодированию стартовали во Франции в 2014 году и открыты для студентов и профессионалов. С тех пор он распространился на Европу, Африку и Ближний Восток, и в этом году зарегистрировалось более 24 000 участников.

Цель конкурса — оптимизировать некоторые проблемы, с которыми могут столкнуться инженеры Google. Есть 3 основных шага для вызова:

  • До 23 февраля онлайн-тренировка. Цель состояла в том, чтобы оптимизировать способ нарезки пиццы.
  • 23 февраля: 4-часовой квалификационный онлайн-раунд. Это тема данной статьи.
  • 1 апреля: финальный раунд в парижском офисе Google.

Я зарегистрировался с 3 друзьями из моей инженерной школы. Мы вместе провели несколько хакатонов, поэтому достаточно хорошо знаем, как друг друга кодируют и думают. Это был наш первый опыт работы с Google Hashcode.

Эта статья о нашем понимании проблемы.

Квалификационный онлайн-раунд очень конкурентный, с более чем 24000 участников, и только то, что мы можем предположить, менее 100, выбрано для финального раунда. Google не поделился, сколько будет выбрано для финального раунда.

Мы зарегистрировались, чтобы принять участие в хабе в Париже, чтобы мы могли встретиться с другими участниками (и друзьями), а также воспользоваться бесплатными 🍕 и напитками.

проблема этого года

Задача состояла в том, чтобы оптимизировать распределение видеофайлов кеша в серверной сети. Кэширование файлов ускоряет работу пользователей в конечных точках. Мы знаем, какое видео будет запрошено, и количество, связанное с каждой конечной точкой. У нас также есть задержки между всеми конечными точками, серверами и центрами обработки данных. Цель состоит в том, чтобы минимизировать среднее время ожидания для всех запросов.

Раунд длится всего 4 часа, и нужно проанализировать 4 набора данных. Нашим первым шагом было разобрать данные в объект на Python. Это заняло у нас около 20–30 минут, и мы были удивлены, увидев, что некоторые команды уже представили решения за это время.

Затем пришло время установить базовый уровень. Просто заполняйте серверы кеша случайным образом, пока их память не будет заполнена. Затем нажмите кнопку отправки. Мы представили наше первое решение, это очень простое базовое задание, через час после начала испытания. Тогда наш рейтинг был 18-м в мире и 2-м во Франции. Мы думали, что мы на правильном пути!

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

  • один из нас будет решать задачу с помощью линейного решателя (пакет PuLP на Python)
  • один из нас будет реализовывать первую эвристику
  • двое из нас попытались бы найти и реализовать новый алгоритм

Наши решения

Вот два алгоритма, которые мы придумали во время челленджа:

  • Первая идея заключалась в том, чтобы при просмотре одного кэш-сервера получить список всех релевантных запрошенных видео и оценить каждое видео в зависимости от его размера и количества запросов. Затем мы могли бы ранжировать видео на каждом кэш-сервере и заполнить его «лучшими» видео. Но у этой простой модели есть несколько проблем. Во-первых, он не учитывает сетевую часть проблемы. Возможно, какой-то соседний кеш-сервер уже передает одни и те же видео тем же конечным точкам. Во-вторых, эта модель не использует данные о задержке. Мы повторяли этот алгоритм, идея состояла в том, чтобы разработать итерационный алгоритм, который позволил бы получить стабильное решение. На первом этапе мы заполняем серверы кеша, как мы сказали ранее. Затем на следующих шагах мы обновляем оценку каждого видео на кэш-серверах, просматривая рейтинг всех серверов и их задержки. Для этого мы смотрим на конечные точки, а не на серверы.
  • Наша вторая идея заключалась в том, чтобы начать с заполнения серверов путем ранжирования видео, как было сказано ранее, и просмотра перекрывающихся видео между соседними серверами. Допустим, два соседних сервера обслуживают один и тот же большой файл и имеют 95% перекрытия на обслуживаемых конечных точках. Тогда, может быть, мы сможем удалить большой файл с одного из двух серверов и оставить довольными 95% пользователей. Порог был взят равным 95%, но мы пробовали другие значения.

Результаты и идеи

Мы заняли 175-е место в общем зачете, 23-е место во Франции и 1-е место в нашем центре. В то время как мы значительно улучшили наш базовый показатель, другие команды улучшили его еще больше. Первый из двух алгоритмов был нашим лучшим, и мы немного модифицировали его в зависимости от файла данных, который мы просматривали, потому что ситуации были немного разными. Наш второй алгоритм был слишком экстремальным и не приводил к хорошим результатам даже при изменении порога. Линейный решатель дал хорошее решение для одного из 4 файлов (остальные были слишком большими).

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

Мы довольны нашими результатами, но надеемся улучшить их в следующем издании. В следующий раз финальный тур ✊. А пока можно найти:

Спасибо Полу, Уго и Клементу за то, что они стали частью команды Minor Thing!