Алгоритмы *

Привет, меня зовут Геннадий, я работаю в Ozon, занимаюсь разработкой backend-сервисов.

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

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

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

Тайловость в играх – очень распространенное явление, особенно в играх инди сегмента. Чаще всего используют квадратные тайлы – в них проще всего задать необходимые данные, будь то карта уровня или инвентарь. Однако на квадратных и прямоугольных формах возможности подобной системы не ограничиваются.

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

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

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

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

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

В открытых источниках можно встретить множество работ, статей и книг по тому, как работает этот загадочный фильтр, будь то линейный, расширенный (extended), сигма-точечный (unscented) или любой другой фильтр Калмана. Однако намного реже освещается вопрос корректности работы фильтра.

В это же время фильтр Калмана применяется в системах с особыми требованиями по функциональной безопасности, отказ или неисправность которых может привести к человеческим потерям, как это имеет место для автопилотируемых устройств. Таким образом, валидация результатов работы фильтра Калмана – это один из первых вопросов, который должен стоять перед инженером при разработке ПО для подобных систем.

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

Всем привет! Меня зовут Владислав Мосин, я учусь на 4-м курсе бакалаврской программы “Прикладная математика и информатика” в Питерской Вышке. Прошлым летом вместе с Алиной Плешковой, магистранткой нашего факультета, я проходил стажировку в JetBrains Research. Мы работали над проектом Music2Dance, цель которого — научиться генерировать танцевальные движения, подходящие под заданную музыку. Это может быть использовано, например, при самостоятельном обучении танцам: услышал музыку, запустил приложение, и оно показало движения, которые гармонично с этой музыкой сочетаются.

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

Большинство статей про алгоритмы, используемые для решения задачи многорукого бандита, очень академичны. Они пестрят формулами, графиками и статистическими таблицами. При этом как будто подразумевается, что у нас есть неизменяемый набор ручек для дёргания и n→∞ попыток. В этой статье я постараюсь рассказать об этих алгоритмах с колокольни обычного разработчика применительно к реальным условиям, в которых работает наш продукт (но графики будут — с ними красивее).

Дисклеймер: эта статья написана обычным разработчиком, не дата-саентистом или аналитиком. Не стоит рассматривать её в качестве серьёзного научного труда и искать неточности, неполноту и крайности. Она не про это.

Так как это статья про конкретное практическое применение, то и термины буду использовать из нашего домена:

• просмотр(n) = попытка;
• смайл(s) = победа;
• смайлрейт(w, от worth) = количество смайлов/количество просмотров;
• контент = то, у чего есть эти самые просмотры и смайлы.

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

Недавно разбирался в старых своих наработках/скриптах и наткнулся на скрипт где решалась задача о ферзях. Собственно это послужило написанию статьи о том как проходили этапы написания его алгоритма. Возможно пригодится начинающим программистам для решения похожих задач (код в примерах написан на java).

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

Изученные правильные практики и шаблоны проектирования - лишь вектор, который вдохновляет на новые красивые и уникальные решения.

Здесь нет примеров хорошей архитектуры, советов как должно быть и как правильно. Я просто хочу зафиксировать мысли, которые надо не забывать воспроизводить при решении очередной задачи.

2021 год. IoT окружил нас с Вами со всех сторон. GPS/GLONASS трэкерами и всевозможными облачными платформами слежения нас зазывают со всех сторон. Казалось бы, с чего вдруг я решил, что данный пост имеет актуальность?! Но не все так однозначно - давайте разбираться!

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

Автопроизводители бесконечно совершенствуют свои модели автомобилей, предлагая все более производительные, безопасные и экономичные седельные тягачи. Развитые страны строят более экономичные автомагистрали. Логистические компании выстраивают более оптимальные логистические маршруты и казалось бы все движется только вверх и вперед и с каждым годом расходы транспортной компании на топливо должны уменьшаться! Но в жизни получается не так. Несомненно, если сравнивать 1990,2000 и 2010 года, то по мере обновления моделей грузовых автомобилей, расход топлива стремительно сокращался. К примеру для грузовиков 1990 года выпуска при перевозке 20 тонн груза расход топлива 45л/100км считался нормальным. Моделям 2000-х годов удавалось выйти из 40л/100км расхода топлива, а грузовики 2010 годов выпуска уже могли хвастаться расходом 30-35 л/100км пути. Но что происходит сейчас, в 2021году?

Современные модели грузовиков заявляют о паспортных расходах в 21....23...25л/100км, но в реальных условиях транспортные компании получают средний расход автомобилей в районе 30-31л/100км. Встает резонный вопрос? Получается что автопроизводители лгут и их автомобили не стали более экономичными и это всего лишь маркетинговые ходы? На самом деле нет - проблема кроется в другом. Автопроизводители, как и производители электроники, очень сильно шагнули вперед и автомобили обогнали в своем развитии людей, которые их эксплуатируют. Ситуация стала такова, что люди, управляющие современными грузовыми автомобилями, не могут раскрыть полный потенциал автомобиля с точки зрения расхода топлива.

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

В этой обзорной статье вы узнаете, что такое mesh denoising, какие методы использовались и используются для устранения шума на полигональных сетках (от классических фильтров до передовых графовых нейронных сетей), и получите общее представление о развитии направления.

С помощью технологии трехмерного сканирования можно получить 3D-модель реального объекта. Но знаете ли вы, что почти всегда такие объекты содержат шумы и неточности? В Twin3d мы сканируем людей (и не только) и с помощью фотограмметрии получаем 3D-модели, которые дальше необходимо обрабатывать в зависимости от конечной цели их использования. Естественно, от шумов надо избавляться, чтобы применять виртуальную модель человека в кино/играх/рекламе. Нужно много чего еще делать, но об этом мы поговорим потом.

• как работать с Neo4j и объемными датасетами на примере YELP;
• чем может быть полезен YELP dataset;
• частично: какие особенности в новых версиях Neo4j и почему книга «Графовые алгоритмы» 2019 года от O'REILLY уже устарела.

Это пилотная статья. Будем благодарны за обратную связь. Если тема вызовет интерес, мы возможно примем решение выложить на GitHub наши исходники(python) и входные данные.

Случилось мне поучаствовать в марте 2021 г. в хакатоне с задачей на комбинаторику и оптимизацию. Команду решил собрать свежую, из одиночек, дрейфующих в пуле самого хака. Довольно быстро нашлись front и back, и втроем мы принялись старательно размышлять, как потратим деньги, когда выиграем. Надо сказать, что в хаках я не так давно, но уже успел поучаствовать и в ЛЦТ(Лидеры Цифровой Трансформации), и в Цифровом Прорыве. В последнем даже нам удалось занять бронзу в финале. Роль всегда у меня была project+product+ppt. Так вот этот мартовский хакатон меня заинтересовал живостью и насущностью бизнес проблем, которые там решались. Так как часто в хакатонских кейсах проблемы немного надуманы, решения этих проблем немного фееричны и не несут практического смысла, а побеждает профессиональная преза и поставленный питч. Опытные хакантощики, читающие эти строки, поймут. Но полно про хакатоны и про то, какие они бывают, а то собьемся с курса.

В этам хаке преза и даже front мало интересовали кейсодержателей. Это был натуральный бизнес хакатон с абсолютно живыми дата сетами и с натуральной бизнес болью. К слову сказать, наша команда не выиграла, а заняла третье место (всего до защиты дошло 5 команд). Теперь наконец к условию:

Есть 204 ТТ (торговые точки). Каждую из них нужно посетить минимум раз в неделю, а некоторые больше одного раза. Длительности посещения каждой ТТ известны и не изменяются внутри недели.

Язык кибернетики

Прямых доказательств, связывающих рождение технологии Motion Amplification с силовыми ведомствами США, у нас нет, но косвенных достаточно. Неслучайно среди примеров использования есть немало кейсов из аэрокосмической и оборонной отраслей. Измерение уровня вибрации вертолета во время полета – важная, но очень непростая задача. С Motion Amplification она решается довольно быстро и просто.

Не менее важно знать и состояние инфраструктурных объектов и промышленных активов - оборудования, резервуаров, трубопроводов и т.д. Как можно оперативно оценить состояние моста, чтобы гарантировать безопасное перемещение техники по нему? Оказалось, что без инноваций решить эту задачу проблематично.

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