Главная » Хабрахабр » Как писать программы на стыке мобильной разработки и алгоритмов? Конкурс и истории Яндекса

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

С 10 по 22 сентября пройдет конкурс Яндекс.Блиц по мобильной разработке. Регистрация открыта. Блиц — это короткий путь в Яндекс: участникам топ-5 будет достаточно успешно пройти одну секцию собеседования вместо стандартных четырех.

Сегодня мы поделимся их историями с читателями Хабра. По случаю конкурса мы поговорили с коллегами об интересных задачах, относящихся сразу и к мобильным платформам, и к алгоритмам.

Но не всё так просто. Есть мнение, что разработка мобильных приложений — нечто особенное, далекое от программирования в общем смысле, и специалисты, которые пишут под Android и iOS, никогда не сталкиваются с решением алгоритмоемких задач, ограничиваясь подключением готовых библиотек, версткой экранов, написанием простейшей бизнес-логики и исследованием багов конкретной платформы.

Даже в топовых девайсах не такие мощные CPU и GPU и не так много памяти, как в современном компьютере. Создание софта для мобильных устройств всегда сопряжено с ограничениями. Их владельцы особенно сильно страдают от нехватки ресурсов. При этом основную часть рынка составляют бюджетные смартфоны с еще более слабым железом.

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

Блиц, который пройдет в сентябре, не станет исключением. Исторически Блиц — это конкурс на знание алгоритмов и умение воплотить идею решения в коде. Мы постарались отобрать задачи с алгоритмами, похожими на те, которые приходилось применять мобильным разработчикам Яндекса в реальных проектах для Android и iOS.

Ускорение работы саджеста Браузера

Михаил Ефимов, ведущий разработчик:

В ней работает автозаполнение — достаточно ввести начало слова, и мы предложим слово целиком. — Я занимался омнибоксом — поисковой строкой Браузера. Чтобы это сделать, мы берем все суффиксы слова — все подстроки, которыми оно заканчивается. Исходная задача может быть упрощена до следующей: получив на вход некоторую строку, найти все слова из заранее заданного множества, в которых введенная строка встречается в виде подстроки. Односимвольные суффиксы — здесь у нас были бы «ол» и «л» — не учитываем, потому что по ним в саджест попадает мусор. Например, для слова «стол» это будет «cтол» и «тол».

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

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

Можно хранить как простой массив — но в него тогда будут очень долго вставляться новые вхождения. Дальше возникает вопрос, как хранить уже отсортированный список. В качестве ключа каждый узел дерева содержит определенный суффикс определенного слова, а в качестве «дополнения» в узлах хранится информация по приоритетам. Поэтому я выбрал для хранения «дополненное» двоичное дерево поиска — augmented binary search tree. Дальше можно анализировать этот и соседние узлы, чтобы понять, какие из слов можно использовать для выдачи. Все, что нужно сделать, — найти узел дерева, соответствующий введенному префиксу.

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

Отображение камер видеонаблюдения на мобильных Яндекс.Картах

Сергей Кузнецов, ведущий разработчик:

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

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

Простейший алгоритм решения — когда мы выбирали какой-нибудь квадрат и пересекали его со всеми остальными — работал за n2. Если эту задачу формализовать, то она сводилась к следующей: на плоскости есть n одинаковых квадратов со сторонами, параллельными осям координат, и нужно из них выбрать такое множество квадратов, чтобы внутри него они не пересекались, а все остальные квадраты пересекались хотя бы с одним из квадратов исходного множества. Если не знать о таком подходе, то такую задачу, конечно, можно решить, но если знать — она решается гораздо проще. Но задачу можно решить и за n*log(n), используя некий класс алгоритмов, который в литературе называется «сканирующая прямая». Сразу знаешь, в каком направлении думать.

Камеры на мобильных Картах. Если уменьшить масштаб, остается только один значок

Получение данных от одного из источников саджеста Браузера

Александр Яшкин, руководитель группы бэкенда портала:

Один из таких источников — локальная история пользователя. — Существует несколько «тяжелых» источников подсказок, которые выводятся при наборе текста в омнибоксе Браузера. В чем особенность омнибокса? Подсказки из истории выгружает исторический провайдер — компонент приехал к нам из Chromium. При старте браузера провайдер строит быстрый индекс подсказок по истории за последнюю неделю. Он должен быть очень быстр, подсказывать сразу же, по мере набора текста, поэтому источники в основном синхронные. Для хранения данных внутри таких контейнеров обычно применяется красно-черное дерево. В Chromium индекс истории для омнибокса использовал ассоциативные контейнеры std::set и std::map из стандартной библиотеки C++.

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

Параллельно вносил изменения в наш код. Я сделал несколько подходов, оптимизаций, апстримов в Chromium. Он достаточно увлеченный разработчик — интересуется C++, STL, алгоритмами. Затем задача перешла к нашему разработчику Денису Ярошевскому. То есть просто поменять базовые структуры. Покопавшись, он предложил поступить кардинально: заменить std::set на flat_set, а std::map на flat_map. Flat-контейнеры — одни из самых популярных контейнеров, не входящих в стандартную библиотеку C++. std::set и std::map хранят свои элементы в узлах дерева, а flat_set и flat_map, по сути, являются обертками над сортированным вектором. Возможно, в следующем стандарте они все-таки в нее попадут.

Чтобы доказать эффективность, мы сделали perf test: взяли профиль одного из наших коллег, построили из него индекс истории и прогнали на нем популярные запросы. Вначале было некоторое недоверие: предлагаемый путь казался слишком простым, лежал на поверхности. Денис показал мне результат, улучшения были очевидны, и я в его идею тоже поверил. Выбрали штук 10 запросов и посчитали времена.

Она сказывалась в любом Chromium-based-браузере, поэтому сначала мы, как участники проекта Chromium, решили сделать апстрим. Найденная проблема не была специфичной для Яндекс.Браузера. У разработчиков Chromium достаточно настороженное отношение ко всем, кто снаружи предлагает что-то поменять, тем более кардинально. Но в Chromium много кто коммитит, и часть предлагаемых идей — дикие. Предложили перед этим доказать эффективность и написать мини-design-doc, чтобы они могли понять идею, выгоду и покритиковать предложение. Наш патч сначала не хотели брать.

Не добавляйте к нам в проект никаких новых библиотек — реализации уже существуют в boost, eastl. Кроме того, они сказали: раз вам нужно, напишите и добавьте отдельные реализации flat-контейнеров. Это аналог стандартной библиотеки, и хромиумцы очень переживают, чтобы в нее не попало ничего лишнего. Flat-контейнеры предстояло добавить в base-компоненты Chromium.

Денис спорил с владельцами кода base и омнибокса, существенно переработал код по результатам ревью — и наконец поборол их и заапстримил код в Chromium. Денис Ярошевский всем этим занялся, потратил время на написание design-документа, написал на C++-шаблонах реализацию flat_set, применил массу шаблонной магии, написал тесты, покрывающие функциональность контейнеров, создал еще один синтетический perf test — мы же не могли отправлять perf test с настоящим профилем коллеги.

Хромиумцы затем написали: «Да, мы действительно увидели 10–20% улучшения на всех гистограммах. Вся эта эпопея длилась месяцев шесть. От них это уже через даунстрим пришло к нам в браузер, и потом хэппи-энд. Классно, спасибо!». В этом индексе преимущества flat-контейнеров проявились гораздо лучше, чем недостатки. Действительно, исторический индекс значительно ускорился на всех конфигурациях, на всех платформах.

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

См. левую часть графика. Резкое снижение времени загрузки результатов омнибокса в начале 2017 года связано именно с переходом на flat_set и flat_map

Ускорение работы одного из HashMap в Chromium

Олег Максименко, ведущий разработчик:

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

Это был внутренний HashMap, из Chromium. Я решил заменить имеющуюся реализацию. Затем я пошел немножко дальше и убедился, что это не ошибка ребят из Google, что дело не в реализации всего HashMap, а в хэш-функции. Я его заменил и получил выигрыш в несколько раз. И получилось, что у них в коде, который мы использовали, был тривиальный хеш, в качестве хеша использовался адрес в памяти. Это внешняя вещь. Может быть, у них HashMap и не был горячим местом, а у нас стал, когда мы применили эту структуру. Возможно, из-за каких-то особенностей, например небольшого объема, такое решение их устраивало. В результате это обращение к хеш-памяти пропало из списка горячих мест, стало занимать уже какой-то небольшой процент, как и ожидалось сначала. Простой заменой наивной и тривиальной хеш-функции на std::hash мы получили прирост скорости в 3–10 раз. Все стало хорошо и красиво.


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Конференция «Контентинг» — теперь с поддержкой hyper-threading

Друзья, на связи контент-студия Хабра. 29 ноября мы проводим собственную конференцию про контент и авторов. Будем учить, вдохновлять и рассказывать, как лучше, — в два синхронных потока докладов и дискуссий. Спикеры — эксперты в области контент-маркетинга, которые годами нарабатывали и тестировали ...

J2CL — Лучше поздно, чем никогда

Ещё никому не удалось опоздать на свои похороны.Валентин Домиль Идея трансляции Java в JavaScript далеко не нова, и все уже давно набили шишек с Google Web Toolkit, однако этот продукт сообщество ждало как ни один другой — о нем говорили ...