Биоинформатика: от чашек Петри к биологии In silico

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

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

Мы начнём с разбора простейшего алгоритма вероятностного подсчёта, выделим его недостатки (раздел 2). Затем (раздел 3) опишем алгоритм, впервые преложенный Робертом Моррисом в 1978 году, укажем его важнейшие свойства и приемущества. Для большинства нетривиальных формул и утверждений в тексте присутствуют наши доказательства — интересующийся читатель сможет найти их во вкладышах. В трёх последующих разделах мы изложим полезные расширения классического алгоритма: вы узнаете, что общего у счётчиков Морриса и экспоненциального распада, как можно уменьшить ошибку, пожертвовав максимальным значением, и как эффективно обрабатывать взвешенные события.

В первой части статьи мы реализовали простой (и не очень эффективный) рендерер сетки ГУТ, и пообещали, что оптимизируем рендерер настолько, что он сможет отобразить заявленный в заголовке миллиард ячеек.

Для этого нам придётся значительно сократить объём потребляемой видеопамяти — в текущем виде даже на игровых видеокартах (если бы их можно было купить в наше время!) памяти может не хватить, не говоря уж о видеокартах в офисных компьютерах.

В курсовой работе потребовалось написать алгоритм с логарифмической сложностью, который будет находить N-е число из последовательности Фибоначчи.

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

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

Привет, меня зовут Геннадий, я работаю в 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-модели, которые дальше необходимо обрабатывать в зависимости от конечной цели их использования. Естественно, от шумов надо избавляться, чтобы применять виртуальную модель человека в кино/играх/рекламе. Нужно много чего еще делать, но об этом мы поговорим потом.